rust-bakery/nom

makeExprParser + precedence climbing

sshine opened this issue · 3 comments

sshine commented

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 commented

Related: #1362
A combinator to parse tokens with operator precedence. Based on the shunting yard algorithm.

stefnotch commented

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

ilonachan commented

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!

  • 🚀1