How to handle cyclic recursion, i.e. two parsers that depend on each other?

[Asha20]

Hi! I'm trying to implement a grammar that looks something like this:

<lval> -> <ident>
<lval> -> <lval> [ <expr> ]

<expr> -> <int>
<expr> -> <lval>
<expr> -> <expr> + <expr>

Basically, I want to implement array indexing using an expression. The problem I'm running into is that an lval is itself a valid expr. When I try writing the parsers, I end up with a stack overflow because they keep alternating calls between each other. I've marked the cyclic function calls with comments below to make it more obvious.

Here's roughly what my code looks like (it's probably not 100% correct, I'm just simplifying it for demonstration's sake):

enum Lval {
    Ident(Ident),
    Index(Box<Lval>, Box<Expr>)
}

enum Expr {
    Int(u32),
    Add(Box<Expr>, Box<Expr>),
    Lval(Lval),
}

fn lval_parser() -> impl Parser<Lval> {
    recursive(|lval| {
        choice((
            ident_parser().map(Lval::Ident),
            lval.then(expr_parser().delimited_by(just('['), just(']'))) // expr_parser() called here
                .map(|(lval, expr)| Lval::Index(lval, expr)),
        ))
    })
}

fn expr_parser() -> impl Parser<Expr> {
    recursive(|expr| {
        let atom = choice((
            int_parser().map(Expr::Int),
            lval_parser().map(Expr::Lval), // lval_parser() called here
        ));

        todo!()
    })
}

My guess is that I have to forward-declare the parsers somehow, but I'm unsure how to do it. Any help would be greatly appreciated.

Thank you for the awesome library by the way! I'm having lots of fun tinkering with it and learning about compilers.

[CraftSpider]

There's a method on Recursive, Recursive::declare. It can be used to define as many parsers as you need in advance, then define them all later with Recursive::define

Example

let first = Recursive::declare();
let second = Recursive::declare();

first.define(
    just('A').then(second.clone().or_not())
);

second.define(
   just('B').then(first.clone().or_not())
};

[Asha20]

Thank you for the help! Originally I thought I'd run into trouble when cloning a parser that's been declared but hasn't been defined yet. After some poking around I noticed that the parsers are stored inside an Rc, so things work fine. Calling define will define the clones as well.

Here's what I ended up going with, in case anyone else might find it useful:

fn lval_and_expr_parser() -> (impl Parser<ast::Lval>, impl Parser<ast::Expr>) {
  let lval = Recursive::declare();
  let expr = Recursive::declare();

  lval.define(todo!());
  expr.define(todo!());

  (lval, expr)
}

pub fn lval_parser() -> impl Parser<ast::Lval> {
  lval_and_expr_parser().0
}

pub fn expr_parser() -> impl Parser<ast::Expr> {
  lval_and_expr_parser().1
}