3 ms·

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 w

by 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.

dalke 12y ago
Unnecessarily hostile? I even used "Perhaps" where you used "apparently", and quoted a block of third-party text like you did. Cox wrote "These tools and many others all have the guarantee that if they tell you the grammar is unambiguous, they'll give you a linear-time parser, and if not, they'll give you at worst a cubic-time parser. Computer science theory doesn't know a better way. But any of these is better than an exponential time parser." It's more generous to believe that Earley is simply one of the "many others" that were unenumerated, but equal in power to GLR. You can certainly argue that there are pluses and minus to all of them, but they are irrelevant for the context of the essay. That section is very short and can't be seen as being a complete summary of alternatives, but rather observation that "newer tools that provide compelling alternatives still embody [the spirit of yacc]", including bison. The lack of a reference to Earley is not indicative that the author does not know it. Consider that ANLR uses adaptive LL( * ) because: > The biggest problem for the average practitioner is that most parser generators do not produce code you can load into a debugger and step through. This immediately removes bottom-up parser generators and the really powerful GLR parser generators from consideration by the average programmer. There are a few other tools that generate source code like ANTLR does, but they don't have v4's adaptive LL( * ) parsers. You will be stuck with contorting your grammar to fit the needs of the tool's weaker, say, LL(k) parsing strategy. PEG-based tools have a number of weaknesses, but to mention one, they have essentially no error recovery because they cannot report an error and until they have parsed the entire input. That's from https://theantlrguy.atlassian.net/wiki/pages/viewpage.action?pageId=1900547 https://theantlrguy.atlassian.net/wiki/pages/viewpage.action... . The page doesn't mention Earley parsers either. I don't think that Terence Parr, author of ANTL and that quote, is ignorant of Earley parsers in 2013. (Especially as Parr mentions Earley in 2007 in http://blog.athico.com/2007/06/interview-with-antlr-30-author-terrence.html http://blog.athico.com/2007/06/interview-with-antlr-30-autho... . Note also the issues with GLR in https://qconsf.com/system/files/presentation-slides/quest-for-the-one-true-parser.pdf https://qconsf.com/system/files/presentation-slides/quest-fo... and compare to the lone reference in that presentation to Earley). FWIW, I was using an Earley-based parser for Python as part of the SPARK package back in 2000, and I'm by far an expert in the field, so I think it's unreasonable to assume, as you did, that a practitioner in the field wouldn't know about it and have other reasons for not enumerating it specifically. "Reject" is my word, not Cox's. Nor did I mean to imply that the reasons on Wikipedia were the same as the ones the Cox used when deciding to not mention Earley, only that there could be reasons. Quoting Parr at http://blog.athico.com/2007/06/interview-with-antlr-30-author-terrence.html http://blog.athico.com/2007/06/interview-with-antlr-30-autho... " GLR and Earley and CYK can deal with the same class of grammars (all context-free grammars), but GLR is more efficient." That one reason alone might be enough for Cox to have decided to mention GLR and leave Earley in the category "and many other[ tools]".
rollypollybear 12y ago
Write your own article then, moron.

by bmn_ 12y ago

dalke 12y ago

Unnecessarily hostile? I even used "Perhaps" where you used "apparently", and quoted a block of third-party text like you did. Cox wrote "These tools and many others all have the guarantee that if they tell you the grammar is unambiguous, they'll give you a linear-time parser, and if not, they'll give you at worst a cubic-time parser. Computer science theory doesn't know a better way. But any of these is better than an exponential time parser." It's more generous to believe that Earley is simply one of the "many others" that were unenumerated, but equal in power to GLR. You can certainly argue that there are pluses and minus to all of them, but they are irrelevant for the context of the essay. That section is very short and can't be seen as being a complete summary of alternatives, but rather observation that "newer tools that provide compelling alternatives still embody [the spirit of yacc]", including bison. The lack of a reference to Earley is not indicative that the author does not know it. Consider that ANLR uses adaptive LL( * ) because: > The biggest problem for the average practitioner is that most parser generators do not produce code you can load into a debugger and step through. This immediately removes bottom-up parser generators and the really powerful GLR parser generators from consideration by the average programmer. There are a few other tools that generate source code like ANTLR does, but they don't have v4's adaptive LL( * ) parsers. You will be stuck with contorting your grammar to fit the needs of the tool's weaker, say, LL(k) parsing strategy. PEG-based tools have a number of weaknesses, but to mention one, they have essentially no error recovery because they cannot report an error and until they have parsed the entire input. That's from https://theantlrguy.atlassian.net/wiki/pages/viewpage.action?pageId=1900547 https://theantlrguy.atlassian.net/wiki/pages/viewpage.action... . The page doesn't mention Earley parsers either. I don't think that Terence Parr, author of ANTL and that quote, is ignorant of Earley parsers in 2013. (Especially as Parr mentions Earley in 2007 in http://blog.athico.com/2007/06/interview-with-antlr-30-author-terrence.html http://blog.athico.com/2007/06/interview-with-antlr-30-autho... . Note also the issues with GLR in https://qconsf.com/system/files/presentation-slides/quest-for-the-one-true-parser.pdf https://qconsf.com/system/files/presentation-slides/quest-fo... and compare to the lone reference in that presentation to Earley). FWIW, I was using an Earley-based parser for Python as part of the SPARK package back in 2000, and I'm by far an expert in the field, so I think it's unreasonable to assume, as you did, that a practitioner in the field wouldn't know about it and have other reasons for not enumerating it specifically. "Reject" is my word, not Cox's. Nor did I mean to imply that the reasons on Wikipedia were the same as the ones the Cox used when deciding to not mention Earley, only that there could be reasons. Quoting Parr at http://blog.athico.com/2007/06/interview-with-antlr-30-author-terrence.html http://blog.athico.com/2007/06/interview-with-antlr-30-autho... " GLR and Earley and CYK can deal with the same class of grammars (all context-free grammars), but GLR is more efficient." That one reason alone might be enough for Cox to have decided to mention GLR and leave Earley in the category "and many other[ tools]".

rollypollybear 12y ago

Write your own article then, moron.