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

Question

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

Interim

Perhaps this is relevant: cstheory.stackexchange.com/questions/4352/… – Czechoslovakia

Answer 1

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.

Halfwitted

More specifically, you can check whether a grammar is ambiguous if it is, but you cannot prove that it is not. – Puff

@OrangeDog: Well, in general you can't prove it, but is it possible for some grammars (Here's one small grammar for which you can easily prove it: "goal = a;"). – Lithium

Answer 2

In general, no.

But as a practical approach, what you can do, is given a grammar, is for each rule, to enumerate possible strings of valid terminals/nonterminals, to see if any rule has two or more equivalent derivations (which would be an ambiguity).

Our DMS Software Reengineering Toolkit is a program transformation system for arbitrary computer langauges, driven by explicit grammar descriptions. DMS uses a parser generator to drive its GLR parsing engine.

DMS's parser generator will optionally the ambiguity check sketched above, by running an iterative deepening search across all grammar rules. This is practical because it has the parse tables to efficiently guide the enumeration of choices. You can tell it to run this check up to some chosen depth. It can take a long time if you choose a depth of any interesting size, but in fact a depth of 3 or 4 is sufficient to find many stupid ambiguities introduced in a large grammar. We generally do this during our initial grammar debugging, and at the point where we think we have it pretty much right.

Lithium

Note: the linked DMS software costs money. The website does not list the price; you must call for a quote. – Eckblad