Constructing a Parse Tree

Constructing a Parse Tree
It is often useful to construct a parse tree explicitly. This can be done quite simply as we perform shift reduce parsing. The strategy is to maintain a forest of partially-completed derivation trees as we parse bottom-up. With each symbol on the stack we associate a pointer to a tree whose root is that symbol and whose yield is the string of terminal, which have been reduced to that symbol, perhaps by a long serious of reductions. At the end of the shift-reduce parsing, the start symbol remaining on the stack will have the entire parse tree associated with it. The bottom-up tree construction process has two aspects.
1- When we shift an input symbol a onto the stack we create a one-node tree labelled a. Both the root and the yield of this tree are at, and the yield truly represents the string of the terminals "reduced" (by zero reduction) to symbol a.
2- When we reduce X1, X2, … Xn to A, we create a new node labelled A. It s children, from the left to right, are the roots of the trees for X1, X2, … Xn. If for all I the tree for Xi has yielded Xi, then the yield for the new tree is X1, X2, … Xn. This string has in fact been reduced to A by a series of reductions culminating in the present one. As a special case, if we reduced E to A we create a node labelled A with one child labelled E.
Stack : $id1 Stack:$E

(a) After shifting id1 (b) After reducing id1to E
Stack :$E + E

E . + . E .
id1
E * E
id2 id3
(c)After reducing id1, id2, id3 to E +E

Stack: $ E
E .
E + E
id1
E * E
id1 id3
(d) At completion
Fig.6: parse tree construction
Ex: consider the sequence of steps depicted in Fig.5. Line (2) the stacks and sequence of trees-one tree consisting of node- is shown in Fig.6 (a). On line (3) the id at the top id reduced to E. A node labelled E is created and its one child is the node pointed to by the id removed from the stack. The result is shown in the Fig.6 (b). After s sequence of shifts and reductions we arrive at the situation shown in Fig.6 (c), which corresponds to the line (10). At that point, E+E is reduced to E. We create a new node labelled E, and this node receives three children, the nodes pointed to by the top positions on the stack. The result is shown in Fig.6 (d) and corresponds to a line (11) of Fig.5.