3 ms·

Earley parsers give no guarantee that the grammar is not ambiguous. This is very important, since you don't want your parser return some arbitrary parse tree, b

by wolfgke 12y ago

Earley parsers give no guarantee that the grammar is not ambiguous. This is very important, since you don't want your parser return some arbitrary parse tree, but you want guarantees that the parse tree that you intended is returned. yacc does this IMHO in the correct way: give warnings (shift/reduce or reduce/reduce conflict in case of a possible ambiguity) and let the user resolve these manually. Since these conflicts are a strong sign of a bad specification of the language, the parser generator should be very cautious in resolving these ambiguities - doing this automatically probably leads to strange consequences the user did not intend.

bmn_ 12y ago
> you don't want your parser return some arbitrary parse tree You have a mistake in your assessment of Earley parsers. For ambiguous grammars and input, they do not return an arbitrary tree, but all possible trees. In this regard they are no worse than yacc: "the user resolve[s] these manually" by picking the correct result(s). To a human, it's visible at a glance which is the correct result(s), entirely without needing to learn how to decipher these bizarre warning messages you mentioned. > conflicts are a strong sign of a bad specification of the language So what? That's not pragmatic thinking. We cannot go back in time and influence the design of ambiguous computer languages so they are not ambiguous. Natural languages never are without ambiguities! The parsing job needs to be done, no matter the complexity of the language. Instead of wishing it weren't so, just use a tool that can deal with it. Earley parsers can, yacc cannot.
- wolfgke 12y ago
  > You have a mistake in your assessment of Earley parsers. For ambiguous grammars and input, they do not return an arbitrary tree, but all possible trees. There can easily be an exponential number of parse trees for an ambiguous grammar, which is a contradiction to the runtime guarantee of the Earley algorithm. > To a human, it's visible at a glance which is the correct result(s), entirely without needing to learn how to decipher these bizarre warning messages you mentioned. The bad warning messages are a problem of yacc and not of the LALR(1) algorithm that yacc uses by default. > So what? That's not pragmatic thinking. We cannot go back in time and influence the design of ambiguous computer languages so they are not ambiguous. The languages are typically not ambiguous, but their reference grammar is (most famous problem is the dangling else (http://en.wikipedia.org/wiki/Dangling_else) http://en.wikipedia.org/wiki/Dangling_else)).
- ufo 12y ago
  The problem is that the ambiguity only gets detected at runtime, when the parser returns 2 trees instead of a single one. Its very useful to be able to identify ambiguities statically, during the language design stage.

by wolfgke 12y ago

bmn_ 12y ago

> you don't want your parser return some arbitrary parse tree You have a mistake in your assessment of Earley parsers. For ambiguous grammars and input, they do not return an arbitrary tree, but all possible trees. In this regard they are no worse than yacc: "the user resolve[s] these manually" by picking the correct result(s). To a human, it's visible at a glance which is the correct result(s), entirely without needing to learn how to decipher these bizarre warning messages you mentioned. > conflicts are a strong sign of a bad specification of the language So what? That's not pragmatic thinking. We cannot go back in time and influence the design of ambiguous computer languages so they are not ambiguous. Natural languages never are without ambiguities! The parsing job needs to be done, no matter the complexity of the language. Instead of wishing it weren't so, just use a tool that can deal with it. Earley parsers can, yacc cannot.

wolfgke 12y ago
> You have a mistake in your assessment of Earley parsers. For ambiguous grammars and input, they do not return an arbitrary tree, but all possible trees. There can easily be an exponential number of parse trees for an ambiguous grammar, which is a contradiction to the runtime guarantee of the Earley algorithm. > To a human, it's visible at a glance which is the correct result(s), entirely without needing to learn how to decipher these bizarre warning messages you mentioned. The bad warning messages are a problem of yacc and not of the LALR(1) algorithm that yacc uses by default. > So what? That's not pragmatic thinking. We cannot go back in time and influence the design of ambiguous computer languages so they are not ambiguous. The languages are typically not ambiguous, but their reference grammar is (most famous problem is the dangling else (http://en.wikipedia.org/wiki/Dangling_else) http://en.wikipedia.org/wiki/Dangling_else)).
ufo 12y ago
The problem is that the ambiguity only gets detected at runtime, when the parser returns 2 trees instead of a single one. Its very useful to be able to identify ambiguities statically, during the language design stage.