4 ms·
That's a great error message, but is it generally possible to take an arbitrary CFG and say whether or not the language it generates contains one or more string
by qntm 16y ago
That's a great error message, but is it generally possible to take an arbitrary CFG and say whether or not the language it generates contains one or more strings with ambiguous interpretations? Even if it's possible, and such strings could be demonstrated, is it computationally practical to find them?
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?
- haberman 16y ago> is it generally possible to take an arbitrary CFG and say whether or not the language it generates contains one or more strings with ambiguous interpretations? 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.