Parse Trees

You can also prove that some text conforms to a grammar 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

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.

Parse trees look a bit like the abstract syntax trees we saw last chapter, but there are differences. An abstract syntax tree is much more compact, as it's sole purpose is to show to semantic meaning of a program. A parse tree shows how the grammar's rules are applied step-by-step to produce the program.