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 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
- 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:
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