next up previous
Next: Elimination of ambiguity. Up: Context-free grammars Previous: Context-free grammars

Parse trees

PARSE TREES. Let G = (VT, VN, S, P) be a context-free grammar. A parse tree for G is a tree constructed as follows:

Let $ \cal {T}$ be a parse tree. The string obtained by concatenating the labels of the leaves of $ \cal {T}$ from left to right id called the YIELD of the parse tree.

Let w be a word of the language generated by G. Clearly there exists at least one parse tree for G whose yield is w. Such a tree is called a parse tree for w w.r.t. G.


LEFTMOST/RIGHTMOST DERIVATIONS. Let G = (VT, VN, S, P) be a context-free grammar. The derivation ($ \alpha_{{1}}^{{}}$,$ \alpha_{{2}}^{{}}$,...,$ \alpha_{{n}}^{{}}$) is LEFTMOST if for each $ \alpha_{{i}}^{{}}$ (with i = 1 ... n - 1) the leftmost non-terminal is rewritten. Analogously we define rightmost derivations.

Remark 3   A parse tree does not specify the order in which productions are used to rewrite non-terminal symbols by strings of grammar symbols: a given parse tree usually represents several different derivations.

However, to any parse tree we can associate a unique leftmost (or a unique rightmost) derivation. Top-down parsing attempts to find a leftmost derivation for the input. In bottom-up parsing, we construct a rightmost derivation (in reverse order).


next up previous
Next: Elimination of ambiguity. Up: Context-free grammars Previous: Context-free grammars
Marc Moreno Maza
2004-12-02