Role of parse tree in CFG

A parse tree (derivation tree) of a CFG G = (V, T, P, S) is an ordered tree in which the root is labelled S, each interior node is a variable A with children X1 … Xk whenever A → X1…Xk is a production, and the leaves are terminals or ε. The yield (the leaves read left to right) is the derived string.

Roles of the parse tree

1. Shows the structure of a string. It displays how the string is derived from the start symbol, grouping the symbols into phrases. Example: for E → E+E | E*E | id the tree shows which operator is applied first.
2. Proves membership. A string is in L(G) if and only if it has a parse tree with root S and that yield. Derivations, recursive inference and parse trees are equivalent.
3. Hides the order of derivation. Many derivations (leftmost, rightmost, mixed) can correspond to one parse tree. The tree fixes the structure and ignores the order in which variables are replaced.
4. Detects ambiguity. A grammar is ambiguous if a string has two different parse trees. Comparing trees is the standard test.
5. Basis of compilers. In the syntax analysis phase of a compiler, the parser builds a parse tree for the source program. Meaning (semantics) and code generation follow the tree. Operator precedence and associativity are encoded by the tree shape.
6. Used in proofs. The pumping lemma for CFLs is proved by considering long paths in a parse tree: a variable repeats on the path, giving the pumpable substrings v and y.