Function left_rec

pub fn left_rec<'a, L: Lexer<'a>, T: Clone>(
    state: &ParserState<L>,
    memo: &Memo<L::Position, Option<T>>,
    parser: impl FnMut(&ParserState<L>) -> Result<T, Error>,
) -> Result<T, Error>

Left recursion support.

Wrapping a parser in left_rec allows it to be left-recursive. This is crucial for parsing left-recursive grammars, as recursive descent parsers often fail to handle them.

The left_rec function solves this problem by employing memoization. The algorithm used is based on this blog post.

fn parse(
    state: &ParserState<CharLexer>, 
    memo: &Memo<usize, Option<String>>,
) -> Result<String, Error> {
    left_rec(state, memo, |state| {
        let fork = state.fork();
        if let Ok(mut s) = parse(&fork, memo) {
            state.advance_to(&fork);
            s.push(state.parse('b')?);
            Ok(s)
        } else {
            state.parse('a').map(|_| String::from("a"))
        }
    })
}
 
let state = ParserState::new(CharLexer::new("abbbb"));
assert_eq!(parse(&state, &Memo::default()).unwrap(), "abbbb");