Function left_assoc

pub fn left_assoc<I, E, O, OP, G, F, B>(
    child: F,
    operator: G,
    builder: B,
) -> impl Parser<I, Output = O, Error = E>
where
    I: Clone + Input,
    E: ParseError<I>,
    F: Parser<I, Output = O, Error = E>,
    G: Parser<I, Output = OP, Error = E>,
    B: FnMut(O, OP, O) -> O,

Applies a parser multiple times separated by another parser.

It is similar to separated_list1 but instead of collecting into a vector, you have a callback to build the output.

In a LALR grammar a left recursive operator is usually built with a rule syntax such as:

• A := A op B | B

If you try to parse that wth alt it will fail with a stack overflow because the recusion is unlimited. This function solves this problem by converting the recusion into an iteration.

Compare with a right recursive operator, that in LALR would be:

• A := B op A | B Or equivalently:
• A := B (op A)?

That can be written in nom trivially.

This stops when either parser returns an error and returns the last built value. to instead chain an error up, see cut.

Arguments

• child The parser to apply.
• operator Parses the operator between argument.
• init A function returning the initial value.
• fold The function that combines a result of f with the current accumulator.

use nom_language::precedence::left_assoc;
use nom::branch::alt;
use nom::sequence::delimited;
use nom::character::complete::{char, digit1};

fn add(i: &str) -> IResult<&str, String> {
    left_assoc(mult, char('+'), |a, o, b| format!("{o}{a}{b}")).parse(i)
}
fn mult(i: &str) -> IResult<&str, String> {
    left_assoc(single, char('*'), |a, o, b| format!("{o}{a}{b}")).parse(i)
}
fn single(i: &str) -> IResult<&str, String> {
    alt((
        digit1.map(|x: &str| x.to_string()),
        delimited(char('('), add, char(')'))
    )).parse(i)
}

assert_eq!(single("(1+2*3)"), Ok(("", String::from("+1*23"))));
assert_eq!(single("((1+2)*3)"), Ok(("", String::from("*+123"))));
assert_eq!(single("(1*2+3)"), Ok(("", String::from("+*123"))));
assert_eq!(single("((1+2*3)+4)"), Ok(("", String::from("++1*234"))));
assert_eq!(single("(1+(2*3+4))"), Ok(("", String::from("+1+*234"))));