Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html
https://github.com/bourguet/operator_precedence_parsing
It seems like there are 2 common algorithms for expressions: the shunting yard algorithm and Pratt parsing [1]. As best as I can tell, which one you use is a coin toss. I haven't been able to figure out any real difference.
They're both nicer than grammar-based approaches when you have many levels of precedence, like C.
But it doesn't seem like there is any strict relationship between the two algorithms, which is interesting. I guess there are other places where that happens, like there being at least two unrelated algorithms for topological sort.
Trivia: The original C compilers used the shunting yard algorithm. IIRC the source made reference to Dijikstra.
The biggest difference is that Pratt/precedence climbing does not require manipulating an extra stack, but instead uses the normal procedure stack in the same manner as recursive descent. This leads to somewhat simpler code. I've seen far more uses of recursive descent/Pratt than shunting-yard.
I can't imagine any case where a user will care -- it's an internal detail. Whereas there are places where a user would notice if you used a CFG vs. a PEG.
A long time ago, people might have been concerned about the recursive calls of Pratt parsing, but it seems like a non-issue now.
I do think Pratt parsing is easier to understand, but that might be because I encountered it first.
I was working on a new metric alert evaluation system and built an expression parser for things like:
system.disk.free{*} / 1024 by {host}
x + y * z => (x + y) * z
x + (y * z)
After implementing it I noticed my results were different than the reference system... and that's when I discovered we did arithmetic wrong in the main app and had for years.
So I had to hard code a toggle for whether to do math properly :(. It's a sort of Hippocratic oath when it comes to these things... first do no harm, and even if it was wrong, people were relying on the existing functionality, and changing it would likely result in sudden alerts for folks.
In the end we did fix it in the main app, but you always feel kind of dirty writing code like that.
I vaguely recall hearing about some fancy C++ template based techniques for accomplishing this, actually, but haven't looked into it.
How much other stuff, apart of math, could be impacted?
As part of something else I was trying. As I was just learning Go at that point, the code is not that clean :D But AFAIK it did work. My memory is a bit hazy on that :)
Understand... perhaps; it is a fascinating algorithm. It's also not complicated at all.
Memorize? Perhaps for code challenges, interviews and special occasions like that... but I haven't found it to be useful enough to commit to memory because in order to parse truly arbitrary expressions, you need to remember much more than just the the shunting yard rules.
I say this as someone who authored a mathematical modeling DSL in grad school and had implement this algorithm to correctly parse arbitrarily complicated math expressions. I was deep in the weeds of this. But I don't think I would have been able to reproduce it from memory even during that time. (also, I had to implement a more general version of the algorithm that dealt with function composition, multi-argument functions, unary operators, special keywords like sum/product over sets, etc.)
Of course nowadays I'm so lazy that I just do "import asteval" in Python. The reason is that once you get beyond the simple operators, arbitrary math expression parsing can be quite hard to get right, and I prefer using something that's heavily tested with no unhandled corner cases.
I guess you'd get to the shunting yard from there by turning the remaining recursion into an explicit stack, but I haven't worked that out to check.
I wonder what real railway yards do.