gearley
gearley copied to clipboard
Parse right-recursive rules in linear time
Rewrite right-recursive rules into left-recursive ones. Rotate the parse forest to undo that rewrite.
It remains to be seen if all right-recursive rules can be rewritten in a simple way.
I'm sure Joop Leo's optimization is no longer possible. The recognizer went too far from a certain kind of approach. That is, it takes an integrated approach, instead of a Buildtree approach with linked items as described in Elizabeth Scott's paper[1]. Anyway, here are descriptions of Leo's optimization:
- http://loup-vaillant.fr/tutorials/earley-parsing/right-recursion
- https://github.com/jeffreykegler/kollos/blob/master/notes/misc/leo2.md
This complexity improvement is currently the most important one possible.
[1]: Elizabeth Scott. SPPF-Style Parsing From Earley Recognizers