Stack overflow on recursive grammar

[Nadrieril]

Hi it's me again, let me know if my issues are too many!

Here's the bug I'm encountering:

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Ast {
    True,
    And(Box<Ast>, Box<Ast>),
}

%%

%glr;
%tokentype char;
%start Expr;

Expr(Ast)
    : 't' { Ast::True }
    | '!'? left=Expr '&' right=Expr {
        Ast::And(Box::new(left), Box::new(right))
    }
    ;

Code:

mod parser {
    include!(concat!(env!("OUT_DIR"), "/parser.rs"));
}

fn main() {
    let mut context = parser::ExprContext::with_default_userdata();
    context.feed('t').unwrap();

    let parses: Vec<_> = context.accept_all().unwrap().collect();
    println!("accepted {parses:#?}");
}

I get: thread 'main' (30735) has overflowed its stack. It seems the mix of left recursion and an optional production trips up whatever magic that makes the GLR parser handle left-recursion normally.

(In case you're curious, what I'm trying to do is adapt the grammar from the Rust Reference into something that can parse rust code for real. I'm trying to have a grammar as close as possible to the original, which is why I don't want to add workarounds that change the grammar shape. You can see the WIP result here)

[ehwan]

Again, thank you for the report.
The optional operator ? itself is just creating new NonTerminal of the operand.
So '!'? will be

ExOpt: '!' { Some('!') }
     |     { None }
     ;

Finally every occurences of '!'? will be replaced by ExOpt.

This bug seems like the limitation of LR(1) grammar, when nullable NonTerminal is placed in front of left-recursive pattern. So expanding

Expr(Ast)
    : '!'? left=Expr '&' right=Expr {
        Ast::And(Box::new(left), Box::new(right))
    }

to

Expr(Ast)
    : '!' left=Expr '&' right=Expr {
        Ast::And(Box::new(left), Box::new(right))
    }
    | left=Expr '&' right=Expr {
        Ast::And(Box::new(left), Box::new(right))
    }

like this will work.

I added some automatic expansion logic in very limited condition,
otherwise at least the parser will print the error to the user to fix it manually.

Thank you.