Ambiguous grammar

From Free net encyclopedia

In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i.e., the string has 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:

Image:Leftmostderivations jaredwf.png

The language that it generates, however, is not inherently ambiguous; the following is a non-ambiguous grammar generating the same language:

A → A + a | A − a | a

References

Compilers: Principles, Techniques and Tools

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