Killing Yacc: 1, 2 & 3
blogs.perl.org
blogs.perl.org
Pain point: debugging shift/reduce conflicts in Yacc can make a person want to pull out their own toenails.
Irrational conclusion: whatever replaces Yacc should accept any CFG. No annoying errors, yippee!
But there are two major problems with accepting arbitrary CFG's, as Russ Cox pointed out in his essay: you give up linear-time parsing, and you don't know if your grammar has ambiguities.
For ambiguities, Russ used the example of 1+1+1. I think a much better example would have been 1-1-1, because (1-1)-1 and 1-(1-1) give you different answers! You don't want to be flying blind about whether your language has ambiguities or not. It would be like having a regular programming language guess what you meant instead of giving you a syntax error.
What if instead, the tool was actually good at helping you understand why your grammar isn't being accepted? Imagine if the error message was something like:
"The string 1+1+1 could be interpreted as either <foo> or <bar>"
...where "foo" and "bar" are convenient ASCII representations of the parse trees (better than what I could demonstrate with HN formatting limitations).
I'm just asking, I seriously don't know.
EDIT: Ah, I guess yacc does this already.
EDIT2: Okay, so since we're talking about building faster parsers, not building parsers faster, and that shift/reduce conflict is something that comes up at parser build time rather than parse time, is there any reason why you can't perform that ambiguity check with yacc and then build your parser the new way?
No, unfortunately it is undecideable, as are many interesting questions you wish you could ask about grammars.
However it is often possible. Even when it is not possible to definitively say that the grammar is ambiguous, it should be possible to say:
"When I see the string <foobar> I can't decide between <x> and <y>."
That's (sort of) what yacc is doing with its shift/reduce conflict errors. I think this it's generally easier to understand why this is with top-down (LL) parsers than bottom-up ones like yacc though. Top-down parsers are closer to the way people actually think. That's why I favor an ANTLR-like approach.