2 ms·
I recently had to write an expression parser. It turns out there are a few "different" algorithms that are common, but they're actually basically the same algor
by IshKebab 3y ago
I recently had to write an expression parser. It turns out there are a few "different" algorithms that are common, but they're actually basically the same algorithm: Pratt parsers, precedence climbing, and the shunting yard algorithm (there may be others, I only started looking into this a week ago). They have small differences but the basic idea is the same.
I went with the shunting yard algorithm because it's not recursive so you don't need to worry about stack overflows. It's basically the iterative version of the other two.
Also note that most implementations of the shunting yard algorithm don't actually check that the expression is valid (e.g. they accept "1 2 +") but it's trivial to fix that with a state machine to check which tokens are acceptable.
This was also the first thing I've tried writing using Copilot and it was a huge time saver. Conservatively I'd say it halved the time it took me to write it. Ok admittedly it's probably a best case - there are a gazillion parser examples out there for it to learn from, but it was still great. I'm going to pay for a subscription.
- sirwhinesalot 3y agoYup, they are all variations of the same idea. What makes the Pratt parser so much nicer is how naturally it fits with the rest of a recursive descent parser. The original paper is somewhat annoying to read due to very strange naming of things, but you can write a pratt parser in like 4 lines of code (not counting the mapping from operator to the next parser call), it's crazy simple.