In the context of programming language design, an unambiguous syntax is important. However, parsing technology is not exclusively applied to programming languages. Marpa's support for ambiguity and abstract syntax forests can e.g. be used for natural language processing. 10 in 10 joke tellers concur: Ambiguity in the English language is a feature, not a bug.
Well, when I use Marpa, I don't actually use abstract syntax forests. But the ability to generate and compare multiple parses, plus especially the ability to inspect the parsing state at an arbitrary point during the parse, are great debugging tools to understand why a given grammar is ambiguous.
But since Marpa's documentation and papers compared it to tools like yacc, I analyzed it from the perspective of someone trying to parse programming languages or data formats -- the sort of thing yacc would be used for.
Most generalized algorithms (such as GLR) allow you to generate and compare multiple parses. Marpa is not new in this regard. And while I agree that this is useful, it's a "run-time error", so-to-speak. Given a specific input, it can tell you the multiple parses it generated.
The benefit of deterministic algorithms is that they can give you this kind of feedback at compile-time. They can generate sample input that would trigger the ambiguity, if they were seen in the wild.
I think a static vs. dynamic typing comparison is apt here. A statically typed language can prove that the types are always correct. Dynamic typing defers this checking to runtime, so you don't get the same static guarantees about your program. The same sort of thing can be said of ambiguity checking in deterministic vs. generalized parsing.
In the end, you have to wait for the input to see whether you triggered an ambiguity or not. And what if you did? Stopping the whole thing and giving an error message may not be acceptable in some cases. Sometimes, you do have to chose a parse tree no matter what.
Which is why prioritised choice is so appealing to me. It gives control to the user, should any ambiguity arise. It also allows the user to write deliberately ambiguous grammars, simply because they're simpler. Finally, I suspect some actual languages, like Markdown, are either impossible or very inconvenient to formalize without prioritised choice.
Yes, this was the entire point of my message.
> Which is why prioritised choice is so appealing to me. It gives control to the user, should any ambiguity arise.
I agree that prioritized choice is a nice tool for resolving ambiguities.
But I don't like PEGs, because everything has to be defined in terms of prioritized choice. That means you don't know if there are ambiguities are not.
> 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):
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...