Function precedence

pub fn precedence<I, O, E, E2, F, G, H1, H3, H2, P1, P2, P3, Q>(
    prefix: H1,
    postfix: H2,
    binary: H3,
    operand: F,
    fold: G,
) -> impl FnMut(I) -> IResult<I, O, E>
where
    I: Clone + PartialEq,
    E: ParseError<I> + FromExternalError<I, E2>,
    F: Parser<I, Output = O, Error = E>,
    G: FnMut(Operation<P1, P2, P3, O>) -> Result<O, E2>,
    H1: Parser<I, Output = Unary<P1, Q>, Error = E>,
    H2: Parser<I, Output = Unary<P2, Q>, Error = E>,
    H3: Parser<I, Output = Binary<P3, Q>, Error = E>,
    Q: Ord + Copy,

Parses an expression with operator precedence.

Supports prefix, postfix and binary operators. Operators are applied in ascending precedence.

The parser will track its current position inside the expression and call the respective operand/operator parsers. The prefix and postfix parsers are called repeatedly until they fail before execution moves on to the operand or binary parser.

Expressions are folded as soon as possible. The result will be reused as another operand. After the expression has been read completely any remaining operations are folded and the resulting, single operand is returned as the result.

It will return Err(Err:Error((_, ErrorKind::Precedence))) if:

• the fold function returns an Err.
• more than one or no operands remain after the expression has been evaluated completely.
• the input does not match the pattern: prefix* operand postfix* (binary prefix* operand postfix*)*

Arguments

• prefix Parser for prefix unary operators.
• postfix Parser for postfix unary operators.
• binary Parser for binary operators.
• operand Parser for operands.
• fold Function that evaluates a single operation and returns the result.

Example

use nom_language::precedence::{precedence, unary_op, binary_op, Assoc, Operation};
use nom::character::complete::digit1;
use nom::combinator::{map_res, fail};
use nom::sequence::delimited;
use nom::bytes::complete::tag;
use nom::branch::alt;

fn parser(i: &str) -> IResult<&str, i64> {
  precedence(
    unary_op(1, tag("-")),
    fail(),
    alt((
      binary_op(2, Assoc::Left, tag("*")),
      binary_op(2, Assoc::Left, tag("/")),
      binary_op(3, Assoc::Left, tag("+")),
      binary_op(3, Assoc::Left, tag("-")),
    )),
    alt((
      map_res(digit1, |s: &str| s.parse::<i64>()),
      delimited(tag("("), parser, tag(")")),
    )),
    |op: Operation<&str, &str, &str, i64>| {
      use nom_language::precedence::Operation::*;
      match op {
        Prefix("-", o) => Ok(-o),
        Binary(lhs, "*", rhs) => Ok(lhs * rhs),
        Binary(lhs, "/", rhs) => Ok(lhs / rhs),
        Binary(lhs, "+", rhs) => Ok(lhs + rhs),
        Binary(lhs, "-", rhs) => Ok(lhs - rhs),
        _ => Err("Invalid combination"),
      }
    }
  )(i)
}

assert_eq!(parser("8-2*2"), Ok(("", 4)));
assert_eq!(parser("4-(2+2)"), Ok(("", 0)));
assert_eq!(parser("3-(2*3)+7+2*2-(2*(2+4))"), Ok(("", -4)));

Evaluation order

This parser reads expressions from left to right and folds operations as soon as possible. This behaviour is only important when using an operator grammar that allows for ambigious expressions.

For example, the expression -a++**b is ambigious with the following precedence.

Operator	Position	Precedence	Associativity
**	Binary	1	Right
-	Prefix	2	N/A
++	Postfix	3	N/A

The expression can be parsed in two ways: -((a++)**b) or ((-a)++)**b. This parser will always parse it as the latter because of how it evaluates expressions:

• It reads, left-to-right, the first two operators -a++.
• Because the minus takes precedence over the increment it is evaluated immediately (-a)++.
• It then reads the remaining input and evaluates the increment next in order to preserve its position in the expression
  ((-a)++)**b.