I have promised you an all-powerful weapon: you have it! Now you have a skill to parse absolutely any string!
Well, any string that is described by a context-free grammar. You can’t use Earley’s algorithm to parse Python without a context-sensitive preprocessing pass, for example. I’d call this hyperbole but I’m not actually sure the author, nor the blog post they cite
But Earley parsers are awesome, because they will parse anything you give them.
This is a long article. Therefore, I have used the He Man meme to keep you entertained throughout the journey. I promise you an all-powerful weapon at the end of the article.
I look forward to the day that compiler textbooks are filled with animated GIFs of retro cartoons.
I wrote an Earley parser in Common Lisp back in grad school and realized that it’s fun, but boy was it slow when you threw huge inputs at it. (And yeah, it may not have been the greatest parser implementation ever, but when I realized it didn’t really pay off all that well, I didn’t pursue it further.)
This is why I advocate GLR parsers instead. :) It’s the same worst-case performance, but in practice most interesting grammars (other than natural-language ones) are nearly-deterministic, and GLR approaches O(n) for those cases.
Well, any string that is described by a context-free grammar. You can’t use Earley’s algorithm to parse Python without a context-sensitive preprocessing pass, for example. I’d call this hyperbole but I’m not actually sure the author, nor the blog post they cite
are aware of this distinction.
I look forward to the day that compiler textbooks are filled with animated GIFs of retro cartoons.
I wrote an Earley parser in Common Lisp back in grad school and realized that it’s fun, but boy was it slow when you threw huge inputs at it. (And yeah, it may not have been the greatest parser implementation ever, but when I realized it didn’t really pay off all that well, I didn’t pursue it further.)
This is why I advocate GLR parsers instead. :) It’s the same worst-case performance, but in practice most interesting grammars (other than natural-language ones) are nearly-deterministic, and GLR approaches O(n) for those cases.