I got bored and wanted to make a parser of C expressions. this will probably become a compiler at some point. previously, I’ve made a calculator using shunting yard, but with an itch to perhaps make a compiler of some kind, I looked at pratt parsing. you won’t find much information about pratt parsing in a conventional learning path of computer science. the dragon book, for all it talks about parsing, doesn’t mention it. as far as I’m aware, most programming language courses will probably teach either LR or recursive descent depending on how academic it is (mine taught recursive descent). pratt parsing specifically appears to be relegated mostly to compiler development and PLT circles. the most mainstream mention I know of it is in crafting interpreters; wikipedia also links a few other posts. I used the crafting interpreters text to get my bearings, but I also wanted to practice reading formal papers more, so I tried using Pratt’s original paper text as much as possible. it did take a bit more time than I’d have liked to wrap my mind around how the recursion fits into the operator precedence, but it did just click all at once, namely once I related it back to the shunting yard algorithm. so now I’m writing the observations down so I don’t forget. maybe it’s useful to you. shunting yard the shunting yard algorithm is, comparatively, much simpler than pratt. you have an output stream and an operator stack. operators are defined with their binding powers, where higher binding power means it binds tighter to its arguments (e.g. * has higher binding power in arithmetic than +). in the simplest description of shunting yard, for every token in the input stream: if it’s a standalone token (i.e. identifier/number), just push it to the output if it’s an operator token: if it’s of higher binding power than the top of the operator stack, push it to the stack if it’s of equal of lower binding power than the top of the operator stack, then pop all operator tokens of higher or equal binding power to the output stream before pushing the operator token to the operator stack popping all higher or equal binding power operators assumes that all operators are left-associative at the end of the token stream, pop all remaining operators to the output. a very primitive shunting yard in C, where expressions are converted to postfix notation, could be: [code example]. the problem with shunting yard is that it’s not very extensible to new behavior. for example, the algorithm has no concept of subexpressions in the recursive sense; adding parentheses means attaching special functionality to the ) token for popping off the stack until reaching the matching (. that’s not hard in its own right, but more complex behavior like unary operators, right-associative expressions, functions with variable arguments, etc. will get messy. this is where the transformation to pratt parsing comes in. from shunting to pratt the main transformation that turns the shunting yard algorithm into a pratt parser is...
Source: Hacker News · Summarized by HeadlinesBriefing