Add support for left-recursive rules

[fgasperij]

Hey, I'd like to start working on adding support for left-recursive rules, which are of the form:

rule sum() -> Expression = sum() + number()

What do you guys think? Would you be interested in a PR?

The main motivation behind this is to parse the new syntax introduced by CPython 3.9/3.10. Guido has already described an approach that looks promising, following that would be my first go.

[kevinmehall]

Have you looked at rust-peg's existing support for operator precedence via precedence climbing? Or are you hoping to be able to translate the python grammar directly?

I've only skimmed the linked post, but it looks like a better explanation or simpler version of the approach used by OMeta. The drawback is that it's tied to packrat parsing / memoization, which rust-peg has some support for with #[cache], but I've not found it to be a performance win in practice, and is not often enabled. I tend to write peg grammars as a shorthand for how I'd hand-code a recursive descent parser, and avoid code that needs to repeatedly re-parse the same input.

But if you can make straightforward extension to #[cache] (#[cache_left_rec]?), to enable left recursion, I'd accept that PR. The code that implements #[cache] is pretty gross, though...

[zsol]

Or are you hoping to be able to translate the python grammar directly?

We're trying to keep as much of the original grammar intact as possible to reduce maintenance burden further down the line.

I think the extension of cache -> cache_left_rec would be the path of least resistance here for us. Thanks for this awesome crate btw!