[Feature Request] Left recursion support

[sc07kvm]

Pigeon is not support left recursion

But in the python PEG parser this feature is implemented. Implementation details here:

• https://medium.com/@gvanrossum_83706/left-recursive-peg-grammars-65dab3c580e1
• https://www.youtube.com/watch?v=QppWTvh7_sI
• https://github.com/we-like-parsers/pegen_experiments/tree/master/pegen
• https://peps.python.org/pep-0617/#left-recursion

[breml]

@sc07kvm Thanks for your PR and sorry for not being responsive on the first PR. I will need dig deeper into the topic of left recursion handling first in order to form an opinion on the approach. Are you aware on some paper writing about this topic?

[sc07kvm]

Guido van Rossum refers to these works in https://peps.python.org/pep-0617:

• Medeiros et al. https://arxiv.org/pdf/1207.0443.pdf
• Warth et al. http://web.cs.ucla.edu/~todd/research/pepm08.pdf

PEG parsers normally do not support left recursion but we have implemented
a technique similar to the one described in Medeiros et al. [2] but using the
memoization cache instead of static variables. This approach is closer to the
one described in Warth et al. [3].
...
[2] Medeiros et al. https://arxiv.org/pdf/1207.0443.pdf
[3] Warth et al. http://web.cs.ucla.edu/~todd/research/pepm08.pdf

But they are difficult to understand. I looked at the implementation https://github.com/we-like-parsers/pegen_experiments/tree/master/pegen