Implement Pratt parsing or precedence climbing

[stefnotch]

I believe that implementing pratt parsing (or precedence climbing, which is supposedly the same algorithm) could be useful. It makes parsing mathematical expressions much simpler, since one no longer has to bend their parsing rules to fit, and can instead simply 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

[Marwes]

Parsing precedence is done in the combine-language extension crate https://docs.rs/combine-language/latest/combine_language/fn.expression_parser.html (via shunting yard).

[stefnotch]

Thank you!

This does seem a bit less powerful than Pratt parsing, since it doesn't handle prefix or postfix operators.

For example, if I want lim to be a prefix operator, with a precedence between addition and multiplication, then I'd have to put in more work.
$\lim 3 \cdot x + 5$ is typically parsed as $(\lim (3 \cdot 5)) + 5$

[Marwes]

I think pratt and shunting yard are the same algorithm (https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html) the only difference is that pratt is generally presented by using the normal program stack whereas shunting yard uses an explicit stack.

In the case of https://docs.rs/combine-language/latest/combine_language/fn.expression_parser.html it may be closer to pratt parsing in that case since it uses the program stack. Thus it may just be a case of extending it to support pre and postfix operators.

[stefnotch]

Sounds good, I'll move this issue to the combine-language repository then.

I don't think I have an immediate need for it, so I'm fine with the issue over there remaining open. If I ever need it, I might contribute a PR. Otherwise I'll leave implementing it to other people who need it.