Pratt parsing support

[epage]

Please complete the following tasks

• I have searched the discussions
• I have searched the open and rejected issues

winnow version

0.2.0

Describe your use case

This would be a performant way of handling precedence in parsing

See zesterer/chumsky#51

Describe the solution you'd like

See

• Implement Pratt parsing for binary infix operators. zesterer/chumsky#144
• Precedence parsing rust-bakery/nom#1362
• https://gist.github.com/ilonachan/3d92577265846e5327a3011f7aa30770

Alternatives, if applicable

No response

Additional Context

No response

[epage]

For more technical details, see

• https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html
• https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html

[Zij-IT]

Heyyo! I was the one to handle a significant portion of the Pratt parser implementation that is available in chumsky :)

I would have to familiarize myself with how y'all do things here at Winnow, but I would be happy to take a crack at getting a Pratt parsing implementation going for Winnow.

Do you have an idea already for an API that you would prefer, or guidelines on how to keep the API winnow-style :D I'd love to contribute to getting some cross-pollination going between two great parsing crates!

[epage]

That would be greatly appreciated!

I have no formal background in parsing and only know of Pratt Parsing from matklad's posts and then your work with chumksy. I'm not even sure where or if I would use it in my own work. So its hard for me to give too specific of guidance on the API.

Overall, the philosophical divergence between chumsky and winnow is that chumsky is a framrwork while winnow is a toolbox. Chumsky owns the process and users plug into that (e.g. users are expected to not implement the Parser trait). Winnow provides common primitives and allows users to build up their parser out of that, as needed. We freely encourage mixing of imperative and functional / declarative parsers. Unsure how that might apply but thought I'd point that out.

One challenge I repeatedly run into is that when we give too high level of a helper, it also constrains the user. A trivial example of this is Parser::try_map which doesn't let you cut-to-top the error from try_map separate from the error from the parser it wraps (#180).

[Zij-IT]

No worries! I'll do what I can to explain what the plan is before jumping on the solution so that we can get at one that you feel both fits into winnow, matches it's approach and is performant!

Okay, so before getting into the implementation itself, would something like the following be acceptable? Below I have different variations of about the same concept listed. Which ones do you find more "winnow-ish"

Operator Parsers

---

For Pratt parsing there are three important pieces of information that are required in order to properly parse an operator:

1. Its associativity (right or left)
2. Its strength (how tightly it binds. e.g. + binds weaker than *)
3. Whether its prefix, postfix or infix

To this end, its important to discuss how an operator parser should look like. Here are a couple ideas that I have:

1. So, the first idea would be to take the implementation from Chumsky, and adapt the implementation for winnow. That would look like this:

   // Pretend that `unary` and `binary` create expressions of one type `Expr`
   prefix(Right(1), '-', |r| unary(r, Op::Neg));
   infix(Left(0), '+', |l, r| binary(l, r, Op::Add));
   postfix(Right(3), '!', |r| unary(r, Op::Fact));

2. Another idea would be to add infix, prefix and postfix methods onto Parser instead of free-standing functions:

   '-'.prefix(Right(1), |r| unary(r, Op::Neg));
   '+'.infix(Left(0), |l, r| binary(l, r, Op::Add));
   '!'.prefix(Right(3), |r| unary(r, Op::Fact));

Pratt Parser

---

Assuming that you prefer the second option, here is an idea for how it would look like with a pratt method provided by the Parser trait. pratt could also be free-standing function which accepts two parsers: One for the "atom" expression and one for the operators.

// Allowing all the operators to be grouped in one tuple
let atom = digits1.map(Expr::Int);
let calc = atom.pratt((
    '-'.prefix(Right(1), |r| unary(r, Op::Neg));
    '+'.infix(Left(0), |l, r| binary(l, r, Op::Add));
    '!'.prefix(Right(3), |r| unary(r, Op::Fact));
));

General things

---

Would I be correct in assuming that this would be best put behind a feature "pratt", or would you want this to be included by default?

[epage]

Its strength (how tightly it binds. e.g. + binds weaker than *)

So this is "precedence", right?

Right(1),

I assume this is associativity and strength combined. Why have them together?

pratt could also be free-standing function which accepts two parsers:

This reminds me that I forgot to list one of the design principles. Grammar-level functionality (ie things you'd see in BNF like literals, repetition, alternatives) are free functions and Parser trait methods are reserved for adapting to the application domain (along with some grammar-level error reporting like Parser::try_map).

So I assume we'd go with

let calc = pratt(
    digits1.map(Expr::Int),
    (
        '-'.prefix(Right(1), |r| unary(r, Op::Neg));
        '+'.infix(Left(0), |l, r| binary(l, r, Op::Add));
        '!'.prefix(Right(3), |r| unary(r, Op::Fact));
    )
);

• Looking at chumsky, prefix/postfix don't use an associativity, only strength. Thoughts on that?
• I find their functions wrapping the Associativity enum odd. I guess just to force everything to be lower case?
• Looks like chumsky accepts multiple function signatures for fold expressions. Is the assumption that this would do the same?

Naming is hard. I'm finding that I prefer names that works at the grammar-level like with #440. I've also had bad experiences looking at graph libraries and not being able to find what I want because they are named after their algorithm and not their purpose. Of course, there is the challenge of multiple algorithms that can meet the same purpose with different criteria, so I'm not too sure how to balance the two.

Some tools we have to help are

• #[doc(alias = "pratt")] (if we don't name it pratt)
• #[doc(alias = "separated")]
• Cross-linking separated to pratt
• Ensuring the doc-comment summary focuses on the intent

As an aside, when it comes to the combinator summary, feel free to leave all the entries blank because this won't fit into such a simple summary.

Would I be correct in assuming that this would be best put behind a feature "pratt", or would you want this to be included by default?

You could start it under unstable-pratt which gives us time to answer questions like that and lowers the bar for what the initial API looks like.

For when we get there, is there a reason to have this be a separate feature?

[Zij-IT]

So this is "precedence", right?

Yup!

I assume this is associativity and strength combined. Why have them together?

That's just how it was done with Chumsky. It would be totally fine to have another parameter for the strength.

Looking at chumsky, prefix/postfix don't use an associativity, only strength. Thoughts on that?

I just totally spaced that, and should have removed it from prefix and postfix.

I find their functions wrapping the Associativity enum odd. I guess just to force everything to be lower case?

This choice is largely just keystrokes I believe. It is indeed a bit odd in hindsight 😅

Looks like chumsky accepts multiple function signatures for fold expressions. Is the assumption that this would do the same?

It can be if that would be desired. It would just require an intermediate trait as in the Chumsky impl. It would also be possible to just restrict it to something in the form Fn(O, Op) -> O for pre- or postfix and Fn(O, Op, O) -> O for infix. I don't know if winnow has an equivalent to MapExtra that would be meaningful to pass in.

For when we get there, is there a reason to have this be a separate feature?

Not any that I can think of. It should be a rather small addition, but I wanted to check :) Chumsky has it under a flag, so I wanted to check.

[epage]

It can be if that would be desired. It would just require an intermediate trait as in the Chumsky impl. It would also be possible to just restrict it to something in the form Fn(O, Op) -> O for pre- or postfix and Fn(O, Op, O) -> O for infix. I don't know if winnow has an equivalent to MapExtra that would be meaningful to pass in.

We don't have MapExtra at this time.

I'm fine with a trait being used for this. I'm considering doing similar in other places.

This has been a great conversation however if we start with it under unstable-pratt, we can move forward with whatever and iterate on it over time without affecting semver.

[epage]

https://gist.github.com/ilonachan/3d92577265846e5327a3011f7aa30770 is interesting to consider which I came across via rust-bakery/nom#1362

[epage]

Trying to collect all styles of "pratt" parsers for easier comparison of their API

chumksy::pratt

let atom = text::int::<_, _, extra::Err<Simple<char>>>(10)
    .from_str()
    .unwrapped()
    .map(Expr::Literal)
    .padded();

let op = |c| just(c).padded();

let expr = atom.pratt((
    // We want factorial to happen before any negation, so we need its precedence to be higher than `Expr::Neg`.
    postfix(4, op('!'), |lhs| Expr::Factorial(Box::new(lhs))),
    // Just like in math, we want that if we write -x^2, our parser parses that as -(x^2), so we need it to have
    // exponents bind tighter than our prefix operators.
    infix(right(3), op('^'), |l, r| Expr::Pow(Box::new(l), Box::new(r))),
    // Notice the conflict with our `Expr::Sub`. This will still parse correctly. We want negation to happen before
    // `+` and `-`, so we set its precedence higher.
    prefix(2, op('-'), |rhs| Expr::Neg(Box::new(rhs))),
    prefix(2, op('*'), |rhs| Expr::Deref(Box::new(rhs))),
    // Our `-` and `+` bind the weakest, meaning that even if they occur first in an expression, they will be the
    // last executed.
    infix(left(1), op('+'), |l, r| Expr::Add(Box::new(l), Box::new(r))),
    infix(left(1), op('-'), |l, r| Expr::Sub(Box::new(l), Box::new(r))),
))
    .map(|x| x.to_string());

combine-language::expression_parser

fn op(l: Expr, o: &'static str, r: Expr) -> Expr {
    Op(Box::new(l), o, Box::new(r))
}

let op_parser = string("+").or(string("*"))
    .map(|op| {
        let prec = match op {
            "+" => 6,
            "*" => 7,
            _ => unreachable!()
        };
        (op, Assoc { precedence: prec, fixity: Fixity::Left })
    })
    .skip(spaces());
let term = many(letter())
    .map(Id)
    .skip(spaces());
let mut parser = expression_parser(term, op_parser, op);

proposed nom::precedence (rust-bakery/nom#1362)

  precedence(
    unary_op(1, tag("-")), //prefix operators
    fail, //postfix operators
    alt(( //binary operators
      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(( //operands
      map_res(digit1, |s: &str| s.parse::<i64>()),
      delimited(tag("("), parser, tag(")")), //subexpression handled via recursion
    )),
    |op: Operation<&str, &str, &str, i64>| { //evaluating the expression step by step
      use nom::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)

https://gist.github.com/ilonachan/3d92577265846e5327a3011f7aa30770

            pratt(
                atom,
                alt((
                    binary_op(tag("="), 2, 1, map_infix),
                    ternary_op,
                    binary_op(tag("+").or(tag("-")), 5, 6, map_infix),
                    binary_op(tag("*").or(tag("/")), 7, 8, map_infix),
                    binary_op(tag("."), 14, 13, map_infix),
                )),
                alt((
                    unary_op(tag::<&str, &str, E>("+").or(tag("-")), 9, map_prefix),
                    group_op,
                )),
                alt((unary_op(tag("!"), 11, map_postfix), index_op)),
                start_bp,
            )
            .parse(i)

Initial #614

precedence(
    digit1.try_map(|d: &str| d.parse::<i32>()),
    (
        "-".value(2).prefix(|x| -1 * x),
        "+".value(2).prefix(|x| x),
        "!".value(2).postfix(|x| factorial(x)),
        "+".value(0).infix(|a, b| a + b),
        "-".value(0).infix(|a, b| a + b),
        "*".value(1).infix(|a, b| a * b),
        "/".value(1).infix(|a, b| a / b),
    ),
)
.parse_next(i)

[39555]

Found another nice interface https://docs.rs/pest/latest/pest/pratt_parser/struct.PrattParser.html. Unfortunately all map closures are boxed.

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

    
pratt
        .map_primary(|primary| match primary.as_rule() {
            Rule::int  => primary.as_str().parse().unwrap(),
            Rule::expr => parse_expr(primary.into_inner(), pratt), // from "(" ~ expr ~ ")"
            _          => 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)
}

[epage]

For anyone subscribed to this but not following along, @39555 has been doing a lot of exploration for implementation and API.

In particular, we've been looking at recursive vs iterative. Recursion is generally faster but hides the recursive nature and prevents people from doing stack overflow prevention.

See

• feat: implement Pratt parsing #614
• PoC: Pratt parsing with shunting yard algorithm #618
• fix(dispatch): handle #[...] attributes #619
• perf: bench for pratt and shunting yard parsers #620
• Pratt example #622

[epage]

In #614 (comment), @39555 called out a missing feature in most of the above pratt parsing APIs: the ability to parse within an operator.. https://gist.github.com/ilonachan/3d92577265846e5327a3011f7aa30770 is the only one I saw that handles this and uses it for ternary opeator, indexing, and parenthesis.

@39555 couldn't that be handled by changing

            delimited(multispace0, alt((
                dispatch! {any;
                    '!' => empty.value((20, (|_: &mut _, a| Ok(Expr::Fac(Box::new(a)))) as _)),
                    '?' => empty.value((3, (|i: &mut &str, cond| {

to

            delimited(multispace0, alt((
                dispatch! {any;
                    '!' => empty.value((20, (|_: &mut _, a| Ok(Expr::Fac(Box::new(a)))) as _)),
                    '?' => cut_err(seq!(
                        _: multispace0,
                        pratt_parser,
                        _: multispace0,
                        _: ':',
                        _: multispace0, 
                        pratt_parser,
                        _: multispace0,
                    )).value((3, (|i: &mut &str, cond| {

[39555]

@epage There are 2 Problems. We can't capture results from the left and right parsers. It is unusual for the operator to produce additional operands.

'?' => cut_err(seq!(
                        _: multispace0,
                        pratt_parser,
                        _: multispace0,
                        _: ':',
                        _: multispace0, 
                        pratt_parser,
                        _: multispace0,
                    )).map(|(left, right)| (3, &(move |cond| {Expr::Ternary(Box::new(cond), Box::new(left), Box::new(right))})

• The closure becomes FnOnce here, and since all closures are &dyn, I can't call it because calling a function moves FnOnce, and moving is not possible from the reference &dyn.

• If it were something like |(left, right)| (3, &(move |cond| { Expr::Ternary(Box::new(cond), Box::new(left.clone()), Box::new(right.clone())) }), then the closure would be locally created, and we would return a reference to the local value."

[epage]

Wouldn't the "fold map" get

• left: condition
• right: (true_expr, false_expr)

So no state is needed and we can use Fn?

[39555]

If I understand correctly you propose to implement ternary operator as infix one so it would be (cond) ? (left : right)? Than the right operand would be actually unconstrained from ? and would allow incorrect syntax 1 + 3 : 2.
Or if we can return whatever the parser produced back to the closure? Than this whatever should be the same type. But maybe it is possible and the good idea.

If I understand correctly, you propose implementing the ternary operator as an infix operator, so it would be (cond) ? (left : right)? In that case, the right operand would actually be unconstrained from ?, allowing incorrect syntax like 1 + 3 : 2.

Or do you mean if we could return whatever the parser produced back to the closure? This whatever would need to be the same type. But maybe it’s possible and a good idea!