Combinator for Eliminating Left Recursion about chumsky HOT 4 CLOSED

Hello!

This pattern is actually even easier to achieve in chumsky with repeated and foldr. You can see this in the nano_rust example or in the tutorial. The basic pattern is as follows:

let sum = expr
    .then(just('+').ignore_then(expr).repeated())
    .foldl(|(lhs, rhs)| Expr::Add(lhs, rhs));

You can also define it recursively as per your original example, although in practice there's no real need to (iteratively is both faster and won't potentially result in stack overflows):

let sum = recursive(|sum| {
    expr.then(just('+').ignore_then(sum))
        .map(|(lhs, rhs)| Expr::add(lhs, rhs))
        .or(expr)
});

from chumsky.

Closing this in lieu of a response, tell me if it's not solved and I can reopen it.

from chumsky.

Is it possible to not use recursive for LL or LR grammars? It will blow the stack very easily, for example in the Foo example I can get a stack overflow with "(".repeat(500). I wonder if a tail_recursive or something like that is possible or make sense.

And sorry if it is off-topic of this issue.

from chumsky.

Yes, it is possible to blow the stack by using recursive patterns in this way. On master, there is now a spill-stack feature, enabled by default, that will spill the stack on to the heap if very deep recursion occurs rather than resulting in a stack overflow. I've found that it has almost no impact on performance in practice.

from chumsky.