January 2, 2017
Recently I was working on a parser, and I thought the grammar might be ambiguous. I looked around for a tool to help me detect ambiguities in context-free grammars, but I couldn’t find anything that worked. So I built CFG Checker!
It is only semi-decidable to determine whether an arbitrary context-free grammar is ambiguous. The best we can do is generate all derivations in a breadth-first fashion and look for two which produce the same sentential form. So that’s exactly what CFG Checker does. If the input grammar is ambiguous, CFG Checker will eventually find a minimal ambiguous sequence. If the grammar is unambiguous, CFG Checker may loop forever.
Here’s how it works. You specify the grammar as a series of production rules:
expression = number | sum sum = expression + expression
Then you run CFG Checker on it:
$ cfg-checker example.cfg .... Found a sequence with two different derivations: expression + expression + expression Derivation 1: 0: expression 1: sum 2: expression + expression 3: expression + sum 4: expression + expression + expression Derivation 2: 0: expression 1: sum 2: expression + expression 3: sum + expression 4: expression + expression + expression
If it doesn’t finish within a few seconds, the grammar is probably unambiguous unless you gave it some pathological input.
CFG Checker is written in C++ and has no dependencies. For more details, see the GitHub project.