[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 is a member of 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.

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