Post #2029203
2026-05-04 17:27 UTC
@bal4e Earley parsers can be optimized to run in linear time, but there seems to be only one person in the world who fully understands how to do it, and his implementation (https://savage.net.au/Marpa.html) is in Perl (with a C core library), so nobody outside the Perl community uses it.
Replies (3)
-
@pmmeurcatpics@ieji.de 2026-05-04 18:45
@Changaco @bal4e @jonhoo impl Rust when 👀
-
@Changaco@diaspodon.fr 2026-05-06 11:11
@bal4e@tech.lgbt Since your post links to it, I've edited the Wikipedia article on Earley parsing to clarify the time and space costs of the algorithms. https://en.wikipedia.org/wiki/Earley_parser
-
@bal4e@tech.lgbt 2026-05-06 12:44
@Changaco@diaspodon.fr That's really cool! Though the Marpa homepage mentions that it can't parse all ambiguous grammars in linear time. I think rustc's macro arm language would fall outside its scope, but I don't have the time to test the implementation myself. I see there's a paper published to arXiv; I skimmed through it but couldn't fully grasp it. I've saved it for later, thank you :D