4 ms·

> 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 d

by 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 bmn_ 12y ago

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.