Ambiguity Checker, new with 0.5.2
It’s a tad early for mainstream use, but I was so excited to get it working, I couldn’t wait. Wormhole parser generator 0.5.2 includes an ambiguity checker. It works, but the probabilistic functionality does nothing.
This of course, would be much more useful if the GLR generator subsystem of the wormhole parser generator weren’t currently broken, but nobody’s perfect.
If you didn’t already know, checking for grammar ambiguities in the general case is a fool’s errand, because it has been proven undecidable (the algorithm to decide if a grammar is ambiguous will run forever on some grammars, and we can’t even decide if it will run forever or not). Despite the exponential growth of our search, this doesn’t mean we are stuck with nothing. The exact length of what can be checked depends on the available system resources, and effective branching factor of the language, but by using the GLR algorithm and turning it into a next symbol generator, we are able to check billions of permutations resulting is finding ambiguities up to dozens of symbols long, sufficient for many modern languages.