#1625·nom

makeExprParser + precedence climbing

Author: sshineCreated Jan 17, 2023Updated Apr 1, 2026

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.