Marpa looks interesting. But I am not sure about this claim in the paper:

> Despite the promise of general context-free parsing, and the strong academic literature behind it, it has never been incorporated into a highly available tool like those that exist for LALR[6] or regular expressions.

I think this leaves out several such tools (and there are probably more):

    1. Bison (supports GLR since at least 2009)
    2. Elkhound (GLR parser generator, since 2002)
    3. ANTLR (its top-down ALL(*) algorithm is general)

But let’s step back a second. Is generalized context-free parsing really the holy grail that some people think it is?

For non-parser-geeks, “generalized” means “can handle all grammars.” That sure seems like a feature, especially for people suffering PTSD from unhelpful Bison error messages like “shift-reduce conflict.” The idea of never having to see a message like that again can sure make generalized parsing seem pretty damn attractive (btw: this is the same selling point for PEGs).

But the dark side of generalized parsing is ambiguity. It is undecidable whether a given grammar is ambiguous or not.

Here’s what this means, in practical terms. Generalized tools might save you from “shift-reduce conflict,” but they cannot save you from “this grammar might be ambiguous, and it’s impossible to say.”

So what? Well this means ambiguities can be hiding in your grammar that you don’t know about. Ambiguities mean that certain syntactical constructs could have two possible meanings, and which one the parser chooses is totally arbitrary.

The best real-life example of this is the “dangling else” ambiguity: http://en.wikipedia.org/wiki/Dangling_else Everybody knows about it now, but when it was originally introduced into ALGOL 60, it went totally unnoticed. The language had even been published in a technical report before anyone was aware that the ambiguity existed.

Now I agree that “shift-reduce conflict” sucks, but to me “parser tools should accept any grammar” is an overreaction. That’s like saying “syntax errors in JavaScript suck, we should make the parser accept anything and try to do something reasonable.” If that idea gives you the heebie jeebies, you’ll know how I feel about generalized parsing.

To me the answer isn’t generalized parsing, it’s a parsing formalism and tool that, when it gives you an error, gives you enough information to know exactly what the issue is. The tool can be your helper as you develop your grammar/language, helping you understand whether your language is ambiguous or not and how to fix your ambiguities. When it accepts your grammar, you can have confidence that your language and grammar are unambiguous.

Now at least generalized CFG algorithms (like GLR and Marpa) can tell you at runtime that the input is ambiguous. PEGs can’t even do that: they just define the ambiguity away by saying “in cases of ambiguity, the first alternative wins by definition.” Sure it makes the formalism unambiguous, but the language as your users experience it is still just as ambiguous.

I wrote about this all in more detail here: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...