Josh Grams
2015-09-15 11:54:00 UTC
Loup's Earley Parsing Explained[1] is great, but I still wanted to
understand Elizabeth Scott's[2] technique to build the shared packed
parse forest (SPPF) as you go, because it seemed like that would be more
straightforward than searching though all the sets afterward. I finally
worked through all the details of the paper, and here's a tiny parser
(about 200 lines of JavaScript) that demonstrates the technique, along
with an annotated pseudocode version which should hopefully be enough to
explain it to others...?
http://joshuagrams.github.io/pep/
Feedback welcome, of course.
--Josh
[1]: http://loup-vaillant.fr/tutorials/earley-parsing/
[2]: http://www.sciencedirect.com/science/article/pii/S1571066108001497
understand Elizabeth Scott's[2] technique to build the shared packed
parse forest (SPPF) as you go, because it seemed like that would be more
straightforward than searching though all the sets afterward. I finally
worked through all the details of the paper, and here's a tiny parser
(about 200 lines of JavaScript) that demonstrates the technique, along
with an annotated pseudocode version which should hopefully be enough to
explain it to others...?
http://joshuagrams.github.io/pep/
Feedback welcome, of course.
--Josh
[1]: http://loup-vaillant.fr/tutorials/earley-parsing/
[2]: http://www.sciencedirect.com/science/article/pii/S1571066108001497