Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the easiest way of telling whether a BNF grammar is ambiguous or not?

Namely, is there a tool out there that will automatically show the full language for a given grammar, including highlighting ambiguities (if any)?

like image 700
user456584 Avatar asked Jan 24 '11 22:01

user456584


1 Answers

There might be some peculiarity about BNF-style grammars, but in general, deciding whether a given context-free grammar (such as BNF) is ambiguous is not possible.

In short, there does not exist a tool because in general, that tool is mathematically impossible. There might be some special cases that could work for you, though.

like image 154
Austin A. Avatar answered Oct 07 '22 16:10

Austin A.