writing about pratt parsing so I remember it
14 points by FedericoSchonborn
14 points by FedericoSchonborn
My current favorite version of this family of parsing algorithms is the one where you parse infix expressions into a scratch array by pretending they all have the same precedence, like x + y * -z / q becomes a 7-element array, where every other item is an infix operation, and then you run the pure precedence climbing algorithm on that array.
Having the array as a scratch state instead of as an emergent behavior of the algorithm saves you from the headache of having to think about how non-infix operators interact with precedence or making sure that you're tying them into the pratt parser correctly, but the end result and behavior of the algorithm is the same. In fact IMO it's secretly the same algorithm as pratt's, just organized differently. As a bonus, you have the option of implementing it as a CST->AST conversion step after a parser generator, instead of being forced to handwrite almost all of the expression-related stuff in your parser (this bonus is also a reminder of where to put the equal-precedence scratch array parse when you're handwriting it).
I didn't find the Shunting Yard Algorithm all that difficult to use when parsing expressions. I handle unary operators and parenthesis at a lower level than binary operators, and the Shunting Yard Algorithm can easily handle right-associative binary operators.