I have implemented a LL1 parser in a non recursive approach with a explicit stack.

The following algorithm is from the Dragon Book:

set zp to point to the first symbol of w;
set X to the top stack symbol;
while ( X != $ ) { /* stack is not empty */
    if ( X is a ) 
       pop the stack and advance zp;
    else if ( X is a terminal )
    else if ( M[X, a] is an error entry )
    else if ( M[X,a] = X -+ Y1Y2 Yk ) {
       output the production X -+ YlY2 - . Yk;
       pop the stack;
       push Yk, Yk-1,. . . , Yl onto the stack, with Yl on top;

    set X to the top stack symbol;

The book says:

The parser is controlled by a program that considers X, the symbol on top of the stack, and a, the current input symbol. If X is a nonterminal, the parser chooses an X-production by consulting entry M[X, a] of the parsing table IM. (Additional code could be executed here, for example, code to construct a node in a parse tree.) Otherwise, it checks for a match between the terminal X and current input symbol a.

However i need more info on how to construct the expression tree nodes under this approach. I have a node hierarchy of UnaryOperator, BinaryOperator, etc but dont know where to instanciate it.

Yet i havent found any simple example of this (with for example the arithmetic language).

1 Answer 1


It happens just as the cited text from the book explains: when you expand a nonterminal via its grammar rule (given by M[X, a]), then you can create a corresponding node.

Say you have rules of the following form:

Term -> Factor Term'
Term' -> * Term | / Term | ε

Factor -> x | y | ... (simplified for individual numbers, letters, what-have-you)

Then, once you expand Term -> Factor Term' you can create a Term node with two child nodes. When you successfully parse the first number via the Factor -> ... rule (this is the first if in your example code now) you can attribute this number to the already created Factor node.

Next, you expand for example Term' -> * Term via M[Term',*] and create a new Term node.

Continuing, you will parse the * and annotate it at your Term' node, expand Term -> Factor Term' once more, thus creating two more nodes, successfully parse a Factor and annotate its number to the second Factor node and finally, on end of input you will parse Term' via the epsilon production (M[Term',$] = ε), which tells you that you can remove that Term' node (though that may be optional).

What you end up with for an input string like 3*4 is then a tree like this:

Term ( Factor(3), Term' (*, Term ( Factor(4) ) ) )

In a post-processing step, you could simplify the resulting tree, as nonterminals like Term' stem from making the grammar non-left-recursive, but are otherwise unsuitable for the resulting AST, so you would want to reverse the grammar transformation on your resulting tree to get something like this:

Mult (Number(3), Number(4))

  • Thanks for the reply. So, basically you are saying that first i need to create the "parse tree", and then convert it to the AST?. Since the parse tree and the AST of the expression are not the same thing.
    – Wyvern666
    Mar 5, 2014 at 0:17
  • In a sense they are the same thing, however, it is always possible to transform a tree into a more suitable representation. It is called abstract for a reason.
    – Frank
    Mar 5, 2014 at 6:01
  • The parse tree often contains symbols that can be omitted from the AST, things such as parentheses, separators, etc.
    – david.pfx
    Mar 22, 2014 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.