Stack overflow with mutually recursive rules

[nrabulinski]

Hi! I'm creating a parser for a rust-like language and I'm a little bit stuck. This is roughly my simplified grammar which causes me the headache:

<expr> : <fcall>

<fcall> : <primary> "(" (<expr> ",")* ")"

<primary> : <literal> | <ident> | <expr with block>

<stmt> : <expr with block> | <expr> ";"+

<block> : "{" <stmt>* "}"

<expr with block> : <block>

I tried different approaches at simplifying it or implementing it with chumsky in different ways but I always end up panicking and I'm not sure how I can approach this problem

[zesterer]

That sounds like you're hitting left recursion. Chumsky is a recursive decent PEG parser, so you'll need to restate your left-recursive rules as right-recursive ones.

[nrabulinski]

Thank you! I did a bit of boxing so the rules can refer to each other and took some inspiration from your nano-rust example and so far it works :D

[nrabulinski]

If anyone else stumbles on a similar issue: other than boxing both parsers so they can refer to each other, I also made the stupid mistake of defining my expression parser as specifically a function call, instead of using foldl and spent too much time trying to figure out why my expressions weren't parsing 🤦‍♂️🤦

[zesterer]

As a point of interest, this boxing is not actually necessary! Recursive parsers actually have a way to allow declaration and definition to be separated such that parsers can refer to one-another in whatever arbitrary patterns you want: https://docs.rs/chumsky/latest/chumsky/recursive/struct.Recursive.html#method.declare