Pratt parsing is a black box

# Introduction It caught my attention that most of Pratt parsing tutorials that I've stumbled on spend almost all of their time explaining Pratt's algorithm and none explaining the properties behind Pratt that actually matter. Pratt fits into just 9 lines of code if you're programming in a high-level language such as Rhombus: fun expression(rbp = 0): let mutable t = token advance() let mutable left = t.nud() while rbp < token.lbp: t := token advance() left := t.led(left) left fun expression(rbp = 0): let mutable t = token advance() let mutable left = t.nud() while rbp < token.lbp: t := token advance() left := t.led(left) left fun expression(rbp = 0): let mutable t = token advance() let mutable left = t.nud() while rbp < token.lbp: t := token advance() left := t.led(left) left fun expression(rbp = 0): let mutable t = token advance() let mutable left = t.nud() while rbp < token.lbp: t := token advance() left := t.led(left) left And here's a secret: that's the least important thing you need to understand about Pratt's. In fact, you don't need to understand this piece at all! Imagine if you were only able to use quicksort if you understood its implementation. Imagine if you were only able to use files if you knew how to implement a filesystem from scratch. It's the same logic here. If you lack the power to abstract, you'll arrive nowhere in computer science because that's how the whole field works. In fact, I wrote the backbone of a heavily Pratt-based parsing machinery for a compiler that I've been writing since last year w/o even bothering to understand the above snippet in any detail. Not convinced? Think for a second on how they do in traditional parsing techniques: compiler compilers! They use code generators to spit the parsing algorithm because just a minuscule crowd bothers to learn what the parsing engine is actually doing. It's no different with Pratt. However Pratt is so small that you can just copy'n'paste these 9 lines of code in your project and call it a day instead of adding a new complex dependency to your project. The algorithm hasn't changed since 1973 and it's not gonna change now. In this article I'll go over what you actually need to keep in mind for Pratt parsing. The point won't be about memorizing any of it though. The point is about acquiring a mindset. As long as you acquire the mindset you don't need to even bother to remember even a single word of what I say here. # Nuds & leds The only tutorial on Pratt parsing that I can firmly recommend to someone who has never been exposed to the topic is actually a talk that Douglas Crockford gave in the conference GOTO 2013¹. Douglas Crockford nailed it when he stated: Pratt takes parsing which is a really complicated thing and reduces it to one simple question: What do we expect to see to the left of a token? — Douglas Crockford, GOTO 2013 At first glance it may look like a mystical statement devoid of meaning, but that's the question that becomes the framework on how you face parsing problems and it'll rewire your brain to internalize the Pratt parsing mindset. That's the most important thing you need to understand. You register semantic actions for two categories: nuds and leds. A nud is a token that expects nothing to its left (nud stands for null denotation) while a led expects something (led stands for left denotation). Traditional parsing techniques register semantic actions to production rules. Here's an example I took straight from GNU Bison's manual: expr: expr '+' expr { $$ = $1 + $3; } ; expr: expr '+' expr { $$ = $1 + $3; } ; expr: expr '+' expr { $$ = $1 + $3; } ; expr: expr '+' expr { $$ = $1 + $3; } ; The text between the braces is code that executes when the BNF-like grammar on the left matches. I'm gonna repeat myself because that's really important: traditional parsing techniques register semantic actions to production rules (which by definition are non-terminal symbols). In contrast Pratt parsing registers semantic actions to the terminals themselves instead. That's a fundamental shift on how you face parsing problems. Here's a stripped down version of the code for the tables that I have in my compiler right now: static constinit const auto nud_table = make_dispatch_table( rule_c<token::lparen, token::nud::parse_lparen>, rule_c<token::lbrace, token::nud::parse_lbrace>, rule_c<token::code::exclamation_mark, token::nud::parse_negation>, rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>, rule_c<token::code::plus_sign, token::nud::parse_unary_plus>, rule_c<token::code::minus_sign, token::nud::parse_unary_minus>, rule_c<token::code::dplus_sign, token::nud::parse_preincrement>, // ... rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>, rule_c<token::code::identifier, token::nud::parse_identifier> ); static constinit const auto led_table = make_dispatch_table( rule_c<token::lparen, token::led::parse_function_call>, rule_c<token::lbrack, token::led::parse_array_indexing>, rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>, rule_c<token::code::dampersand, token::led::parse_logical_conjunction>, rule_c<token::code::dequals_sign, token::led::parse_equality>, // ... rule_c<token::code::dminus_sign, token::led::parse_postdecrement>, rule_c<token::code::asterisk, token::led::parse_multiplication> ); enum : unsigned { parse_until_end = 0, prefix_operator_binding_power = 120, }; static constexpr auto binding_power = make_dispatch_table( rule_c<token::code::dvertical_bar, 10>, rule_c<token::code::dampersand, 20>, rule_c<token::code::dequals_sign, 30>, // ... rule_c<token::code::lparen, 130>, rule_c<token::code::lbrack, 130>, rule_c<token::code::dplus_sign, 130>, rule_c<token::code::dminus_sign, 130>, rule_c<token::code::dot_asterisk, 130>, rule_c<token::code::rarrow, 130>, rule_c<token::code::dot, 130> ); static constinit const auto nud_table = make_dispatch_table( rule_c<token::lparen, token::nud::parse_lparen>, rule_c<token::lbrace, token::nud::parse_lbrace>, rule_c<token::code::exclamation_mark, token::nud::parse_negation>, rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>, rule_c<token::code::plus_sign, token::nud::parse_unary_plus>, rule_c<token::code::minus_sign, token::nud::parse_unary_minus>, rule_c<token::code::dplus_sign, token::nud::parse_preincrement>, // ... rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>, rule_c<token::code::identifier, token::nud::parse_identifier> ); static constinit const auto led_table = make_dispatch_table( rule_c<token::lparen, token::led::parse_function_call>, rule_c<token::lbrack, token::led::parse_array_indexing>, rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>, rule_c<token::code::dampersand, token::led::parse_logical_conjunction>, rule_c<token::code::dequals_sign, token::led::parse_equality>, // ... rule_c<token::code::dminus_sign, token::led::parse_postdecrement>, rule_c<token::code::asterisk, token::led::parse_multiplication> ); enum : unsigned { parse_until_end = 0, prefix_operator_binding_power = 120, }; static constexpr auto binding_power = make_dispatch_table( rule_c<token::code::dvertical_bar, 10>, rule_c<token::code::dampersand, 20>, rule_c<token::code::dequals_sign, 30>, // ... rule_c<token::code::lparen, 130>, rule_c<token::code::lbrack, 130>, rule_c<token::code::dplus_sign, 130>, rule_c<token::code::dminus_sign, 130>, rule_c<token::code::dot_asterisk, 130>, rule_c<token::code::rarrow, 130>, rule_c<token::code::dot, 130> ); static constinit const auto nud_table = make_dispatch_table( rule_c<token::lparen, token::nud::parse_lparen>, rule_c<token::lbrace, token::nud::parse_lbrace>, rule_c<token::code::exclamation_mark, token::nud::parse_negation>, rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>, rule_c<token::code::plus_sign, token::nud::parse_unary_plus>, rule_c<token::code::minus_sign, token::nud::parse_unary_minus>, rule_c<token::code::dplus_sign, token::nud::parse_preincrement>, // ... rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>, rule_c<token::code::identifier, token::nud::parse_identifier> ); static constinit const auto led_table = make_dispatch_table( rule_c<token::lparen, token::led::parse_function_call>, rule_c<token::lbrack, token::led::parse_array_indexing>, rule_c<token::code::dvertical_bar, token::led::parse_logical_disjunction>, rule_c<token::code::dampersand, token::led::parse_logical_conjunction>, rule_c<token::code::dequals_sign, token::led::parse_equality>, // ... rule_c<token::code::dminus_sign, token::led::parse_postdecrement>, rule_c<token::code::asterisk, token::led::parse_multiplication> ); enum : unsigned { parse_until_end = 0, prefix_operator_binding_power = 120, }; static constexpr auto binding_power = make_dispatch_table( rule_c<token::code::dvertical_bar, 10>, rule_c<token::code::dampersand, 20>, rule_c<token::code::dequals_sign, 30>, // ... rule_c<token::code::lparen, 130>, rule_c<token::code::lbrack, 130>, rule_c<token::code::dplus_sign, 130>, rule_c<token::code::dminus_sign, 130>, rule_c<token::code::dot_asterisk, 130>, rule_c<token::code::rarrow, 130>, rule_c<token::code::dot, 130> ); static constinit const auto nud_table = make_dispatch_table( rule_c<token::lparen, token::nud::parse_lparen>, rule_c<token::lbrace, token::nud::parse_lbrace>, rule_c<token::code::exclamation_mark, token::nud::parse_negation>, rule_c<token::code::less_than_sign, token::nud::parse_enter_type_scope>, rule_c<token::code::plus_sign, token::nud::parse_unary_plus>, rule_c<token::code::minus_sign, token::nud::parse_unary_minus>, rule_c<token::code::dplus_sign, token::nud::parse_preincrement>, // ... rule_c<token::code::user_macro, token::nud::parse_user_macro_expansion>, rule_c<token::code::identifier, token::nud::parse_identifier> ); static constinit const auto led_table = make_dispatch_table( rule_c<token::lparen, token::led::parse_function_call>, rule_c<token::lbrack,