Ambiguous grammar

In computer science, a grammar is an ambiguous grammar if some string in the language can be generated in more than one way (i.e., it has more more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars.

For programming languages, ambiguous grammars can lead to difficulties for some compilers.

Example

The context free grammar

A → A + A | A − A | a

is ambiguous since there are two leftmost derivations for the string a + a − a:

	A	→ A + A	|	A	→ A − A
		→ a + A	|		→ A + A − A
		→ a + A − A	|		→ a + A − A
		→ a + a − A	|		→ a + a − A
		→ a + a − a	|		→ a + a − a

Equivalently, it is ambiguous since there are two parse trees for the string a + a − a:

References

Compilers: Principles, Techniques and Tools

Programming Languages: Design and Implementation, T. Pratt, M. Zelkowitz. Prentice Hall, 2001