makeExprParser + precedence climbing

[sshine]

The nom 7.0 roadmap (#1323) mentions, among many things,

handling precedence in expressions (something like Megaparsec's makeExprParser would be nice)

I am a big fan of Megaparsec's makeExprParser, and if I'm not mistaken, nom still does not have an equivalent, does it?

Here is another idea: Following this post, this comment suggested something more efficient: Parsing expressions using precedence climbing. While makeExprParser converts a nice, declarative table of operators into an LL parser, this parser is somewhat inefficient compared to precedence climbing.

It should be possible to convert a similar operator table into a precedence climbing parser.

The prerequisite for making precedence climbing on a &str is that it's fenced off; i.e. while a makeExprParser parser is still just an LL parser that will leave stuff after the expression unconsumed, a precedence climber will assume that the expression can be analysed from both sides of the &str, i.e. one needs to have fenced off a &str that contains an expression and then apply the precedence climber. That will feel slightly less natural in nom.

[cenodis]

Related: https://github.com/rust-bakery/nom/pull/1362 A combinator to parse tokens with operator precedence. Based on the shunting yard algorithm.

[stefnotch]

Copied from the duplicate pratt parsing issue

Implementing pratt parsing (or precedence climbing, which is supposedly the same algorithm) could be useful. I quite like it for parsing mathematical expressions with lots of different operators, since I no longer has to bend my parsing rules to fit, and can instead specify the binding power and associativity.

There are other libraries that have implemented this, for example

• https://github.com/kevinmehall/rust-peg#comparison-with-similar-parser-generators

• rust analyzer https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html

• chumsky has an experimental one

[ilonachan]

Very much not a parsing expert here, but I followed the tutorial linked by @stefnotch to implement a pratt parser in pure nom: https://gist.github.com/ilonachan/3d92577265846e5327a3011f7aa30770

As the first article linked by @stefnotch points out, this should also cover precedence climbing, since they are the same algorithm (with left-/right-associativity being modeled by whether a binary operator's right/left binding power is greater than the other).

There were some tricky edges, but I think the API turned out fairly nice; this is probably such a common use case that adding it to nom itself could be considered. I haven't published this as a crate or made a PR (yet) but feel free to use if it helps!