[AceJohnny2]

What about Earley's algorithm?

Unfortunately, given the extremely limited hardware of 1960s computers (not helped by the lack of an efficient algorithm), the parsing of an arbitrary CFG was too slow to be practical. Parsing algorithms such as LL, LR, and LALR identified subsets of the full class of CFGs that could be efficiently parsed. Later, relatively practical algorithms for parsing any CFG appeared, most notably Earley's 1973 parsing algorithm. It is easy to overlook the relative difference in performance between then and now: the fastest computer in the world from 1964-1969 was the CDC6600 which executed at around 10 MIPS; my 2010 mobile phone has a processor which runs at over 2000 MIPS. By the time computers had become fast enough for Earley's algorithm, LL, LR, and friends had established a cultural dominance which is only now being seriously challenged - many of the most widely used tools still use those algorithms (or variants) for parsing. Nevertheless in tools such as ACCENT / ENTIRE and recent versions of bison, one has access to performant parsers which can parse any CFG, if that is needed.

from: http://tratt.net/laurie/blog/entries/parsing_the_solved_prob...

Featured here 6 years ago: https://news.ycombinator.com/item?id=2327313

[fernly]

Thanks for the reference. For those like me who'd not heard of it, see [1] for a description and links to many implementations.

[1] https://en.wikipedia.org/wiki/Earley_parser

[AceJohnny2]

I missed that haberman (author of this article) had also commented in that thread extensively:

https://news.ycombinator.com/item?id=2328627