3 ms·
Pratt parsing and precedence climbing are the same algorithm (2016)
- sph 2y agoI might be dumber than average, but I had a hard time understanding Pratt parsing, with its usage of 'nud' and 'led', and this article links to a much clearer explanation of precedence climbing, without the arcane and obtuse names: https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions... Took me an hour from reading this article to adding precedence to my hand-written parser. There's a lot of other articles that try to demystify Pratt parsing, but then they choose Rust or Java and hide what is basically a 10-line long algorithm into signal noise such as multiple classes and five functions. Simplified: expression(int min_precedence) { parse_atom(); while ((tok = peek()) != TOKEN_EOF) { if (operator_precedence(tok) < min_precedence) { break; } int next_min_precedence = is_left_associative(tok) ? precedence + 1 : precedence; // process binary operator. Recurse using `expression(next_min_precedence)` } } That's all there is to it. I'm happy I don't have any mention of 'nud' and 'led' in my code.