WebBS VS expr

A few years back I had to implement a new parser for a custom expression language to replace an old parser that didn’t giving very good errors and was hard to extend. I never did the traditional CS track so parsers were kind of mysterious black magic so naturally first thing I did was search HN.

I stumbled on an older parsing thread [1] with a link to a toy Prayt implementation [2] made by an HNer… and shamelessly ripped it off to write my own Pratt parser implementation.

Great success! Writing a Pratt parser by hand is a lot easier than I thought and like the comment says, adding type information was trivial.

[1] https://news.ycombinator.com/item?id=24480504

[2] https://github.com/mx-scissortail/WebBS

I had to write an expression parser recently and found the number of names for essentially the same algorithm very confusing. There's Pratt parsing, precedence climbing, and shunting yard. But really they're all the same algorithm.

Pratt parsing and precedence climbing are the same except one merges left/right associativity precedence into a single precedence table (which makes way more sense). Shunting yard is the same as the others except it's iterative instead of recursive, and it seems like common implementations omit some syntax checking (but there's no reason you have to omit it).

Here's what I ended up with:

https://github.com/Timmmm/expr

I had to write that because somewhat surprisingly I couldn't find an expression parser library that supports 64-bit integers and bools. Almost all of them only do floats. Also I needed it in C++ - that library was a prototype that I later translated into C++ (easier to write in Rust and then translate).