Parse trees

With each derivation we also associate a derivation tree, which shows the structure of the derivation. As an example consider the tree associated with the derivation of $a+(a*a)$ given before:

The top of the tree (called its root) is labelled with start symbol, the other nodes are labelled with nonterminal symbols and the leaves are labelled by terminal symbols. The word which is derived can be read off from the leaves of the tree. The important property of a parse tree is that the ancestors of an internal node correspond to a production in the grammar.