Combinator for Eliminating Left Recursion

[HackerWithoutACause]

When writing parsers by hand and dealing with left recursion I generally use the following pattern:

fn parse_expr(s: Tokens) -> Option<Expr> {
    let left = parse_left_expr()?;

    parse_right_expr(s, left)
}

fn parse_left_expr(s: Tokens) -> Option<Expr> {
    match s.next()? {
        /* ... */
    }
}

fn parse_right_expr(s: Tokens, left: Expr) -> Option<Expr> {
    match s.next() {
        Some("+") => parse_right_expr(Expr::Add(left, parse_expr(s)?)),
        Some("(") => parse_right_expr(/* parse a call */),
        /* ... */
        _ => left,
    }
}

As I understand this is fairly common way of eliminating left recursion (I don't have an academic background so I don't know its name) but I was unable to find a good way of using this method with the provided what would be that best way of accomplishing this?

[zesterer]

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)
});

[zesterer]

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

[HKalbasi]

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.

[zesterer]

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.