Unary prefix/suffix operator support for PrecClimber

[segeljakt]

Adds a new PrattParser, which works similar to PrecClimber but extends it with unary (prefix and suffix) operator handling.

To try it out, checkout this PR and run cargo run --example=calc in the terminal.

Given a grammar:

WHITESPACE   =  _{ " " | "\t" | NEWLINE }

program      =   { SOI ~ expr ~ EOI }
  expr       =   { prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix* )* }
    infix    =  _{ add | sub | mul | div | pow }
      add    =   { "+" } // Addition
      sub    =   { "-" } // Subtraction
      mul    =   { "*" } // Multiplication
      div    =   { "/" } // Division
      pow    =   { "^" } // Exponentiation
    prefix   =  _{ neg }
      neg    =   { "-" } // Negation
    postfix  =  _{ fac }
      fac    =   { "!" } // Factorial
    primary  =  _{ int | "(" ~ expr ~ ")" }
      int    =  @{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT+ | ASCII_DIGIT) }

You can now define a PrattParser:

let pratt = PrattParser::new()
      .op(Op::infix(Rule::add, Left) | Op::infix(Rule::sub, Left))
      .op(Op::infix(Rule::mul, Left) | Op::infix(Rule::div, Left))
      .op(Op::infix(Rule::pow, Right))
      .op(Op::postfix(Rule::fac))
      .op(Op::prefix(Rule::neg));

And use it like:

fn parse_to_i32(pairs: Pairs<Rule>, pratt: &PrattParser<Rule>) -> i32 {
  pratt
      .map_primary(|primary| match primary.as_rule() {
          Rule::int  => primary.as_str().parse().unwrap(),
          Rule::expr => parse_to_i32(primary.into_inner(), pratt),
          _          => unreachable!(),
      })
      .map_prefix(|op, rhs| match op.as_rule() {
          Rule::neg  => -rhs,
          _          => unreachable!(),
      })
      .map_postfix(|lhs, op| match op.as_rule() {
          Rule::fac  => (1..lhs+1).product(),
          _          => unreachable!(),
      })
      .map_infix(|lhs, op, rhs| match op.as_rule() {
          Rule::add  => lhs + rhs,
          Rule::sub  => lhs - rhs,
          Rule::mul  => lhs * rhs,
          Rule::div  => lhs / rhs,
          Rule::pow  => (1..rhs+1).map(|_| lhs).product(),
          _          => unreachable!(),
      })
      .parse(pairs)
}

Some things to consider:

• Does not support ternary operators.
• Precedence climbing like before uses recursion, though I'm not sure how deep you need to go for this to become a problem.
• The current naming (prefix/suffix/infix) could be misinterpreted as binary operators with prefix/suffix/infix notation. Does it work, or should I name things more explicitly, e.g., unary_prefix/unary_suffix/binary_infix?

[agausmann]

This would be a great feature to have! Personally I think the right way to incorporate this is to keep the public APIs involving PrecClimber at least until next major release, but supplement them with newer APIs that use PrattParser instead. There's nothing wrong with keeping two different algorithms around for a little while.

[segeljakt]

I recently added this to the pest-ast crate, you can use it like this with a grammar like this.

[lberezy]

I understand that this is a little bit old now and would probably requite a bit of fixing up, but is there any movement on this?

I think it would be quite handy to enable prefix/suffix operators like this.

[dragostis]

@lberezy, there hasn't been that much work here ever since, but I'm happy to merge this if it gets push forward.

[segeljakt]

Hi again, I refactored this into its own crate https://crates.io/crates/pratt. Feel free to copy it, add it as a dependency, or just point to it from to pest. You may close this PR if you want.

[tomtau]

@segeljakt @lberezy @dragostis I opened a new PR based on this one: https://github.com/pest-parser/pest/pull/710 -- I had to make a few small changes in order to support no_std. I kept the original PrecClimber in order not to break the existing public API, but marked it with the #[deprecated] annotation.