CODEWITHSUNDEEP
grammarbnf
Mark Kennedy
Mark Kennedy

Reputation: 1791

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?

Upvotes: 8

Views: 7364

Answers (1)

Josh Haberman
Josh Haberman

Reputation: 4220

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.

Upvotes: 10

Related Questions