Ambiguous Grammars, Ambiguous Languages
Because derivation trees, leftmost derivations,
and rightmost derivations are equivalent notations,
the following definitions are equivalent:
A grammar G is ambiguous if there exists some string w
L(G) for which
Grammars are used in compiler construction.
Ambiguous grammars are undesirable because the derivation
tree provides considerable information about
the semantics of a program;
conflicting derivation trees provide conflicting information.
- there are two or more distinct derivation trees, or
- there are two or more distinct leftmost derivations, or
- there are two or more distinct rightmost derivations.
Ambiguity is a property of a grammar,
and it is usually (but not always) possible
to find an equivalent unambiguous grammar.
An inherently ambiguous language is a language
for which no unambiguous grammar exists.
Copyright © 1996 by David Matuszek
Last modified Mar 3, 1996