• Parse tree is a hierarchical structure which represents the derivation of the grammar to yield input strings.
• Root node of parse tree has the start symbol of the given grammar from where the derivation proceeds.
• Leaves of parse tree represent terminals.
• Each interior node represents productions of grammar.
• If A -> xyz is a production, then the parse tree will have A as interior node whose children are x, y and z from its left to right.
Construct parse tree for E –> E + E I E * E I id
Construct parse tree for s –> SS* I ss+ I a
Yield of Parse Tree
Leaf nodes of parse tree are concatenated from left to right to form the input string derived from a grammar which is called yield of parse tree.
Figure represents the parse tree for the string id+ id* id.
The string id + id * id, is the yield of parse tree depicted in Fig.
Figure represents the parse tree for the string aa +a*.
The string aa + a*, is the yield of parse tree depicted in Fig.