Parse Trees

You can also prove that a grammar begets a program by drawing a parse tree, which is a tree diagram that shows how non-terminals are expanded. The root of the tree is the starting non-terminal. Its children are the terms of one of its productions. The tree recursively expands until no non-terminals remain, leaving terminals at the leaf nodes.

Recall this grammar for composing boolean expressions:

or   = or || and
     | and
and  = and && atom
     | atom
atom = TRUE
     | FALSE

Explore how a parse tree is built for expression TRUE && FALSE || TRUE using this grammar:

1. The root of the tree is the grammar's starting non-terminal.
2. The root's children are the elements of its || production.
3. The non-terminals are expanded by their productions. The || terminal has no children as it is a leaf node.
4. The non-terminal and is expanded to an && expression and atom expands to a terminal.
5. The non-terminals are again expanded by their productions.
6. The last non-terminal is expanded, leaving no non-terminals. The parse tree is complete.

⭠ ⭢

Derivations have leftmost and rightmost forms. Parse trees do not. A single tree effectively expands all non-terminals at a particular level in parallel.

The job of the lexer and parser is to turn a sequence of characters into a tree representation like this.