9 ms·
Practical Earley Parsing (2002) [pdf]
- Mathnerd314 7y agoA more useful paper which has a complete Earley algorithm in pseudocode: https://core.ac.uk/download/pdf/28889090.pdf https://core.ac.uk/download/pdf/28889090.pdf
- dfeojm-zlib 7y agoNeat. Has anyone seen Parsing with Derivatives (2011) ? https://youtu.be/WPde6DDLtXg https://youtu.be/WPde6DDLtXg http://matt.might.net/papers/might2011derivatives.pdf http://matt.might.net/papers/might2011derivatives.pdf https://blog.klipse.tech/clojure/2016/10/02/parsing-with-derivatives-regular.html https://blog.klipse.tech/clojure/2016/10/02/parsing-with-der... https://elfsternberg.com/2018/01/24/parsing-derivatives-naive-python-edition/ https://elfsternberg.com/2018/01/24/parsing-derivatives-naiv... https://news.ycombinator.com/item?id=11976769 https://news.ycombinator.com/item?id=11976769 (2016) https://arxiv.org/abs/1604.04695 https://arxiv.org/abs/1604.04695 (2016)
- taejo 7y agoA 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/ http://jeffreykegler.github.io/Marpa-web-site/ [2] http://jeffreykegler.github.io/Ocean-of-Awareness-blog/ http://jeffreykegler.github.io/Ocean-of-Awareness-blog/