Lecture 3:Compiler II

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 treeConstructing 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 fos for X1, X2, … Xn. If for all I the tree for Xi has yielded Xi, then the yield fo