Parse right-recursive rules in linear time

[pczarn]

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

[pczarn]

Mr Jeffrey Kegler said that rewrite is basically impossible. I believe Leo's is still an option.

Leo remains to be prototyped.