Issues with left recursion

[stqcky]

Hi, I'm having some issues using the #[cache_left_rec] attribute.

Here's my code:

#[derive(Clone, PartialEq, Debug)]
pub enum TestExpression {
    FunctionCall {
        callee: Box<TestExpression>,
        arguments: Vec<TestExpression>
    },
    Identifier(String)
}

peg::parser! {
    grammar test() for str {
        pub rule identifier() -> TestExpression = i:$(['a'..='z']+) {
            TestExpression::Identifier(i.to_string())
        }

        #[cache_left_rec]
        pub rule expression() -> TestExpression = exp:(function_call() / identifier()) {
            exp
        }
         
        rule lparen() = "("
        rule rparen() = ")"

        #[cache_left_rec]
        pub rule function_call() -> TestExpression = callee:expression() lparen() arg:(expression() ** ",") rparen() {
            TestExpression::FunctionCall { callee: Box::new(callee), arguments: arg }
        }
    }
}


pub fn parse() {
    let input = "abc()";
    let a = test::expression(&input);
    println!("{:?}", a);
}

When I try to match the string abc() with the rule function_call it works fine, returning Ok(FunctionCall { callee: Identifier("abc"), arguments: [] }).
But when I try to match the same string with the expression rule it doesn't work.
Here's the trace:

[PEG_TRACE] Attempting to match rule `expression` at 1:1
[PEG_TRACE] Attempting to match rule `function_call` at 1:1
[PEG_TRACE] Cached fail of rule expression at 1:1
[PEG_TRACE] Failed to match rule `function_call` at 1:1
[PEG_TRACE] Attempting to match rule `identifier` at 1:1
[PEG_TRACE] Matched rule `identifier` at 1:1 to 1:4
[PEG_TRACE] Matched rule `expression` at 1:1 to 1:4
[PEG_TRACE] Attempting to match rule `expression` at 1:1
[PEG_TRACE] Cached fail of rule function_call at 1:1
[PEG_TRACE] Attempting to match rule `identifier` at 1:1
[PEG_TRACE] Matched rule `identifier` at 1:1 to 1:4
[PEG_TRACE] Matched rule `expression` at 1:1 to 1:4
[PEG_TRACE] Attempting to match rule `expression` at 1:1
[PEG_TRACE] Attempting to match rule `function_call` at 1:1
[PEG_TRACE] Cached fail of rule expression at 1:1
[PEG_TRACE] Failed to match rule `function_call` at 1:1
[PEG_TRACE] Attempting to match rule `identifier` at 1:1
[PEG_TRACE] Matched rule `identifier` at 1:1 to 1:4
[PEG_TRACE] Matched rule `expression` at 1:1 to 1:4
[PEG_TRACE] Attempting to match rule `expression` at 1:1
[PEG_TRACE] Cached fail of rule function_call at 1:1
[PEG_TRACE] Attempting to match rule `identifier` at 1:1
[PEG_TRACE] Matched rule `identifier` at 1:1 to 1:4
[PEG_TRACE] Matched rule `expression` at 1:1 to 1:4
Err(ParseError { location: LineCol { line: 1, column: 4, offset: 3 }, expected: ExpectedSet { expected: {"['a' ..= 'z']", "EOF"} } })

It looks as if it just discards the possibility of the expression being a function_call at the very beginning and just matches abc as an identifier, leaving () which then causes the error.
I would really appreciate some help, as I have banged my head against this for like 2 days.

[kevinmehall]

It works if you inline it into one rule:

#[cache_left_rec]
pub rule expression() -> TestExpression = 
    callee:expression() lparen() arg:(expression() ** ",") rparen() {
        TestExpression::FunctionCall { callee: Box::new(callee), arguments: arg }
    }
    / identifier()

I think the issue is the mutual recursion with #[cache_left_rec] on both rules. #[cache_left_rec] works by forcing the recursive call to fail on the first try such that it first tries non-recursive alternatives (identifier() in your case). Then it saves that result to the cache, and retries parsing until it can't get any further. See https://archive.is/U6UOG for a better explanation of the algorithm.

Here, that injected failure of expression() from expression()'s #[cache_left_rec] causes function_call() to fail, since it doesn't have any other alternative to try, and that failure is cached at the function_call() level, which prevents function_call() from being properly retried with the identifier result for expression. I think it would work with the #[cache_left_rec] logic on only one of the rules, but that's currently (incorrectly?) forbidden with error: left recursive rules create an infinite loop: function_call -> expression -> function_call.

[stqcky]

Thank you so much, you pointed me in the right direction. I managed to implement the thing I was trying to do.