Theorem 4.2.1: Let G be a context-free grammar, G = (V, _, P, S), A__V, and consider a derivation A _ _1_2 … _k _* x, where _i__V ____(1ŠiŠk), whose derivation tree is t. Then frontier(t) = x, and each instance of a variable v rewritten in the derivation is the label of the root node of a subtree of t for its sub-derivation, and all other symbols label leaf nodes of t.
Definition 4.2.2: A context-free grammar G is ambiguous if there exists x__L(G) with two distinct derivation trees (or equivalently, two distinct leftmost derivations). A language is inherently ambiguous if every grammar is ambiguous.
| Previous slide | Next slide | Back to first slide | View graphic version |