6.3. Parse Trees

A parse tree is a graphical way to show a derivation.

If rule N → α is used at some point in the derivation, then there is a node labeled N that has a subtree for each token or nonterminal in α.

For example, let's again use the expression grammar from the previous page. There, we did derivation

A corresponding parse tree is

               E
              /|\
             / | \
            E  +  E
            |    /|\
            n   / | \
               E  *  E
              /|\    |
             / | \   n
            (  E  )
               |
               n

Here are some noteworthy things to notice about parse trees.

1. All of the nonleaves are labeled by nonterminals.

2. All of the leaves of the parse trees are tokens. If you read off the leaves from left to right you get exactly the expression n + ( n ) * n that was derived.

3. The parse tree clearly shows structure. For example, the above parse tree shows that the product expression is computed and its result is passed up to the sum expression.

4. The parse tree does not show the order in which the derivation was done. If you do a leftmost derivation or a rightmost derivation of the same expression (in the same way) then you get exactly the same parse tree.

Parse trees are useful because they have some similarities to abstract syntax trees. The difference between the two is that a parse tree must be very closely tied to the grammar, while you have more flexibility in creating an abstract syntax tree.