Menu
I was recently thinking of the following BNF
A -> x | yA | yAzA
where x,y,z are terminals.
I'm pretty sure this grammar is ambiguous, but how would one make it unambiguous?
797
Ambiguity must be removed either syntactically or semantically. It is reasonably certain that any BNF rule that has double recursion (the non-terminal being defined is mentioned twice in the expansion) leads to ambiguity. Sometimes it doesn't matter, as in this grammar:
It is important to note that there are no direct algorithms to find whether grammar is ambiguous or not. We need to build the parse tree for a given input string that belongs to the language produced by the grammar and then decide whether the grammar is ambiguous or unambiguous based on the number of parse trees obtained as discussed above.
An inherently ambiguous language would be absolutely unsuitable as a programming language, because we would not have any way of fixing a unique structure for all its programs. Disambiguate the grammar i.e., rewriting the grammar such that there is only one derivation or parse tree possible for a string of the language which the grammar represents.
If every Context-Free Grammar G with Language L = L (G) is ambiguous, then L is said to be inherently ambiguous Language. Ambiguity is a property of grammar not languages.
A grammar is ambiguous if a particular string can have more than one parse tree. In your language the string yyxzx can have either of these two parse trees:
A A
/ \ /|\`\
y A y A z A
/|\`\ / \ \
y A z A y A x
| | |
x x x
Therefore the grammar is ambiguous.
This actually is equivalent to the notorious "if/then/else" ambiguity in C-like languages, where y=if, z=else, and x=statement. http://en.wikipedia.org/wiki/Dangling_else. I would recommend checking out that page for ideas on how to get around this problem.
66
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
