[Overview] [Previous] [Next]

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

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.

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.

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.