Wormhole Parser Generator 0.5.5 is now available under downloads.
Features include:
* Revamped conditional inclusion mechanism (much better now)
* Use the xp/vista scheme, looks better
* Added the ability to Cancel, which was needed badly for long ambiguity searches.
* Other less noteworthy fixes
Here comes the wormhole parser generator release of the week, 0.5.4. Mainly a consequence of working with the C++ grammar, I fixed the broken %rank disambiguation, and added %short/%long disambiguation as well. Finally, I got tired of the long non-interactive stalls, and now ambiguity searches and grammar loading takes place in background threads. 0.5.4 also includes a fix to lexercommon.cpp, which was incorrectly using delete on memory it obtained with malloc/realloc. As usual, the installer is available in the downloads section.
I’ve been trying to get my C++ parser in shape, so I’ll do an ambiguity search, correct the grammar, and then another search. I just finished a monster C++ ambiguity search. Depth: 6. The first couple of these turned out to need syntactic disambiguation.
Just uploaded wh parser generator 0.5.3.3, which includes the “final” version of the ambiguity checker, a depth first search that is quite stable on enormous search spaces. Of course, don’t expect deep searches to finish in a human lifetime. Available in the downloads.
Just cut wormhole 0.5.3.2, which improves the ambiguity checking sufficiently to filter out ambiguities due to “resolved” conflicts.
The ambiguity checker can reach a bit further into the C99 search space, going 6 deep before it runs out of memory. All conflicts in C99 are resolved, but C++ awaits. It needs more work before it can truly do a depth first search or at least iteratively deepening. Once that is taken care of, the only real issue will be the massive search space.
Happy New Years!
The 0.5.3 installer has been readied. The latest includes fixes to the ambiguity search, as well as a new symbol string ambiguity checker, and miscellaneous fixes. Here’s the symbol string ambiguity checker in action:
Available in the next release of the wormhole grammar analyzer, the string ambiguity checker. Pick a symbol off the list, add to the string, repeat. Click OK and it will check if the string is ambiguous in the currently loaded grammar.
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.
I am in the process of revamping some old code, part of which contains the GLR algorithm. The GLR algorithm is rather involved, so I figured this was the perfect opportunity to explain it once and for all, if for no other reason than to have a copy of this on hand.
Like many parsers, the GLR algorithm is an LR based parser will build a parse tree from a series of tokens. Unlike most though, it is able to handle ambiguous grammars. Of practical interest, this means that a GLR parser can handle the ambiguous grammar of C++. It accomplishes this, in concept, keeping a multitude of stacks, each representing one of the many possible parses of the input. Naturally, the more ambiguous any particular input, the greater the performance hit for using this approach.
To explain what goes on inside a GLR parser. We’ll consider what happens when processing a single input token. As a prerequisite, you need an LR table, produced from a suitable grammar, such as the wormhole parser generator.