How to deal with left recursion

[ambroisie]

Let's say I have rule like the following:

lvalue
: ID
| lvalue DOT ID
| lvalue LBRACKET expr RBRACKET
;

How can I write this with chumsky so that I do not have an infinite loop due to the left recursion?

I understand that my grammar should be rewritten like so:

lvalue: ID lvalue_prime;

lvalue_prime
: <empty>
| DOT ID lvalue_prime
| LBRACKET expr RBRACKET
;

However I am not sure how to write the full lvalue_prime parser. I have this partially working without array subscripts like so:

let var = parse_id().map(ast::Lvalue::Var).labelled("variable");

let field = just(Token::Dot).ignore_then(parse_id()).labelled("field");

var.then(field.repeated())
    .foldl(|var, field| ast::Lvalue::Field(Box::new(var), field))
    .labelled("lvalue")

[zesterer]

The typical way to solve left recursion is to rewrite the pattern as a right-recursive one and then reverse the output.

A technique I've used in my own lang is to use a helper enum to allow me to restate patterns like yours in an iterative manner, as if it were a chain of 'tails' following the original expression.

let var = parse_id().map(ast::Lvalue::Var).labelled("variable");

enum Tail {
    Field(...),
    Call(...),
}

let tail =
    // Field access
    DOT.then(FIELD).map(Tail::Field)
    // Call
    .or(EXPR.separated_by(LBRACKET, RBRACKET)).map(Tail::Call);

let chain = var.then(tail.repeated()).foldl(|lhs, tail| {
    match tail {
        Tail::Field(field) => ast::LValue::Field(lhs, field),
        Tail::Call(arg) => ast::LValue::Call(lhs, arg),
    }
});

Here's how such a pattern would look for the syntax I presume you're going for. Additionally, the similar implementation I use for my own language is here.