Hacker News new | past | comments | ask | show | jobs | submit login
Practical Earley Parsing (2002) [pdf] (uvic.ca)
14 points by bryanrasmussen 30 days ago | hide | past | web | favorite | 3 comments

A more useful paper which has a complete Earley algorithm in pseudocode: https://core.ac.uk/download/pdf/28889090.pdf

A practical implementation of Earley parsing, with some cool features, is Marpa [1]. In particular it is practical in that it parses in linear time

* all the grammar classes that recursive descent parses

* the grammar class that the yacc family parses

* most unambiguous grammars

* all ambiguous grammars that are unions of a finite set of any of the above grammars.

The author's blog [2] presents some interesting features of Marpa, as well as interesting discussion of parsing in general.

[1] http://jeffreykegler.github.io/Marpa-web-site/ [2] http://jeffreykegler.github.io/Ocean-of-Awareness-blog/

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact