Grammatical Ambiguity
Definition:
Let G = (N, T, P, S) be a CFG.
If there exists x Î L(G) with more
than one derivation tree, then G is ambiguous; otherwise, G is unambiguous.
Definition:
A CFL, L, is inherently
ambiguous if L is generated by no unambiguous grammar.
Example:
• Gexpr1 is unambiguous, because for every x Î L(Gexpr1) there exists only one derivation tree
• Gexpr2 is ambiguous, because for i+i*i Î L(Gexpr2) there exist two derivation trees
• Lexpr = L(Gexpr1) = L(Gexpr2) is not
inherently ambiguous because Gexpr1 is unambiguous
19/50