Search code examples
grammarbnf

BNF Grammar Ambiguity

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?

Solution

  • 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.