4 ms·

LR parsers like yacc are obsoleted by Earley parsers, which Cox apparently didn't know about in 2010. Quoting <http://loup-vaillant.fr/tutorials/earley-parsing/

by bmn_ 12y ago

LR parsers like yacc are obsoleted by Earley parsers, which Cox apparently didn't know about in 2010. Quoting <http://loup-vaillant.fr/tutorials/earley-parsing/what-and-why#Why> http://loup-vaillant.fr/tutorials/earley-parsing/what-and-wh...: The biggest advantage of Earley Parsing is its accessibility. Most other tools such as parser generators, parsing expression grammars, or combinator libraries feature restrictions that often make them hard to use. Use the wrong kind of grammar, and your PEG will enter an infinite loop. Use another wrong kind of grammar, and most parser generators will fail. To a beginner, these restrictions feel most arbitrary: it looks like it should work, but it doesn't. There are workarounds of course, but they make these tools more complex. Earley parsing Just Works™. On the flip side, to get this generality we must sacrifice some speed. Earley parsing cannot compete with speed demons such as Flex/Bison in terms of raw speed. It's not that bad, however: • Earley parsing is cubic in the worst cases, which is the state of the art (and possibly the best we can do). The speed demons often don't work at all for those worst cases. Other parsers are prone to exponential combinatorial explosion. • Most simple grammars can be parsed in linear time. • Even the worst unambiguous grammars can be parsed in quadratic time. My advice would be to use Earley parsing by default, and only revert to more specific methods if performance is an issue… In 2014, we now have Earley parsers in C, JavaScript, Lua, Perl and Python. Further discussion on killing yacc: http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2010/12/killing-yacc-1-2-3.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2010/12/why-the-bovicidal-rage-killing-yacc-4.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2011/04/bovicide-5-parse-time-error-reporting.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv... http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2011/05/bovicide-6-the-final-requirement.html http://jeffreykegler.github.io/Ocean-of-Awareness-blog/indiv...

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.
vidarh 12y ago
The problem is this is optimising entirely for the wrong thing. And "killing Yacc" is a pointless exercise if the point is to get traction. What it needs to compete with is hand-written recursive descent parsers.
- bmn_ 12y ago
  Please explain how you arrive at the conclusion that an Earley parser optimises entirely for the wrong thing. What is the wrong thing? Competing with a manually written parser is easy: Earley parsers are derived from a CFG in standard format, such as ISO EBNF or IETF ABNF. Such a grammar is much easier to reason about than parser in a general programming language such as C.
dalke 12y ago
"Earley parsers, which Cox apparently didn't know about in 2010" How do you draw that conclusion? I see nothing in the article which says that he did or didn't know about Earley parsers. A quick search finds this posting by Cox from 17 Apr 2006 at http://compilers.iecc.com/comparch/article/06-04-111 http://compilers.iecc.com/comparch/article/06-04-111 : > Although few people do use Earley and Tomita parsers in practice now, I think general approaches, especially GLR, are gaining ground. Furthermore, the Wikipedia page for GLR says: > Recognition using the GLR algorithm has the same worst-case time complexity as the CYK algorithm and Earley algorithm: O(n^3). However, GLR carries two additional advantages: > - The time required to run the algorithm is proportional to the degree of nondeterminism in the grammar: on deterministic grammars the GLR algorithm runs in O(n) time (this is not true of the Earley[citation needed] and CYK algorithms, but the original Earley algorithms can be modified to ensure it) > - The GLR algorithm is "online" – that is, it consumes the input tokens in a specific order and performs as much work as possible after consuming each token. > Compared to other algorithms capable of handling the full class of context-free grammars (such as Earley or CYK), the GLR algorithm gives better performance on these "nearly deterministic" grammars, because only a single stack will be active during the majority of the parsing process. Perhaps Cox knew about and rejected bringing up Earley in favor of GLR, for several sound reasons that you didn't know about in 2014?
- bmn_ 12y ago
  No need to get so agitated. Your reply comes across unnecessarily hostile for no good reason. > How do you draw that conclusion? I see nothing in the article which says that he did or didn't know about Earley parsers. Simple inference from it not being mentioned, even though I thought it deserved to be. Since that does not prove anything, I wrote "apparently" – I anticipated my assessment could be wrong, and indeed it was. > the Wikipedia page for GLR says I'm not happy with that article. It gives people the wrong ideas, it's not realistically useful to make comparisons with the decades-old original algorithm. Modern Earley parsers do contain optimisations that makes those distinctions mentioned there moot. And unless I completely misunderstand what the WP contributor aimed to express, the Earley algorithm is "online", too, and that is the case even for unmodified/unoptimised Earley parsing. See http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/07/Slides07.pdf http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/le... or just step through an implementation with a debugger. I think the reasons are not as "sound" as you concluded them to be. To me it appears after all that GLR and Earley are equal in power, so Cox shouldn't simply reject, and implementations compete in areas other than the algorithm, e.g. sensible error reporting, simple interface for simple use cases, ability to consume grammars in standard formats, coverage by number of programming languages and such like.

by bmn_ 12y ago

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.

vidarh 12y ago

The problem is this is optimising entirely for the wrong thing. And "killing Yacc" is a pointless exercise if the point is to get traction. What it needs to compete with is hand-written recursive descent parsers.

bmn_ 12y ago
Please explain how you arrive at the conclusion that an Earley parser optimises entirely for the wrong thing. What is the wrong thing? Competing with a manually written parser is easy: Earley parsers are derived from a CFG in standard format, such as ISO EBNF or IETF ABNF. Such a grammar is much easier to reason about than parser in a general programming language such as C.

dalke 12y ago

"Earley parsers, which Cox apparently didn't know about in 2010" How do you draw that conclusion? I see nothing in the article which says that he did or didn't know about Earley parsers. A quick search finds this posting by Cox from 17 Apr 2006 at http://compilers.iecc.com/comparch/article/06-04-111 http://compilers.iecc.com/comparch/article/06-04-111 : > Although few people do use Earley and Tomita parsers in practice now, I think general approaches, especially GLR, are gaining ground. Furthermore, the Wikipedia page for GLR says: > Recognition using the GLR algorithm has the same worst-case time complexity as the CYK algorithm and Earley algorithm: O(n^3). However, GLR carries two additional advantages: > - The time required to run the algorithm is proportional to the degree of nondeterminism in the grammar: on deterministic grammars the GLR algorithm runs in O(n) time (this is not true of the Earley[citation needed] and CYK algorithms, but the original Earley algorithms can be modified to ensure it) > - The GLR algorithm is "online" – that is, it consumes the input tokens in a specific order and performs as much work as possible after consuming each token. > Compared to other algorithms capable of handling the full class of context-free grammars (such as Earley or CYK), the GLR algorithm gives better performance on these "nearly deterministic" grammars, because only a single stack will be active during the majority of the parsing process. Perhaps Cox knew about and rejected bringing up Earley in favor of GLR, for several sound reasons that you didn't know about in 2014?

bmn_ 12y ago
No need to get so agitated. Your reply comes across unnecessarily hostile for no good reason. > How do you draw that conclusion? I see nothing in the article which says that he did or didn't know about Earley parsers. Simple inference from it not being mentioned, even though I thought it deserved to be. Since that does not prove anything, I wrote "apparently" – I anticipated my assessment could be wrong, and indeed it was. > the Wikipedia page for GLR says I'm not happy with that article. It gives people the wrong ideas, it's not realistically useful to make comparisons with the decades-old original algorithm. Modern Earley parsers do contain optimisations that makes those distinctions mentioned there moot. And unless I completely misunderstand what the WP contributor aimed to express, the Earley algorithm is "online", too, and that is the case even for unmodified/unoptimised Earley parsing. See http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/07/Slides07.pdf http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/le... or just step through an implementation with a debugger. I think the reasons are not as "sound" as you concluded them to be. To me it appears after all that GLR and Earley are equal in power, so Cox shouldn't simply reject, and implementations compete in areas other than the algorithm, e.g. sensible error reporting, simple interface for simple use cases, ability to consume grammars in standard formats, coverage by number of programming languages and such like.