It caught my notice that most of Pratt parsing tutorials that I've stumbled on expend nearly all of their period explaining Pratt's algorithm and none explaining the properties rearward Pratt that really matter. Pratt fits into fair 9 lines of code if you're programming in a high-level tongue specified as Rhombus:
let mutable remaining = t.nud() let mutable remaining = t.nud() let mutable remaining = t.nud() let mutable remaining = t.nud() And here's a secret: that's the smallest crucial item you need to comprehend concerning Pratt's. In fact, you don't need to comprehend this part at all! Imagine if you were lone capable to use quicksort if you understood its implementation. Imagine if you were lone capable to use records if you knew how to execute a filesystem from scratch. It's the identical logic here. If you deficiency the power to abstract, you'll attain nowhere in device discipline since that's how the entire site works. In fact, I wrote the backbone of a heavily Pratt-based parsing machinery for a compiler that I've been penning since final twelvemonth w/o equal bothering to comprehend the complete 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 since fair a minuscule assemblage bothers to study what the parsing motor is really doing. It's no distinct alongside Pratt. However Pratt is so small that you can fair copy'n'paste these 9 lines of code in your project and call it a day alternatively of adding a new complex dependency to your project. The algorithm hasn't changed since 1973 and it's not gonna alter now.
In this part I'll go complete what you really need to keep in intellect for Pratt parsing. The item won't be concerning memorizing any of it though. The item is concerning acquiring a mindset. As lengthy as you get the mindset you don't need to equal annoy to recall equal a sole term of what I say here.
The lone tutorial on Pratt parsing that I can firmly propose to person who has never been exposed to the topic is really a conversation that Douglas Crockford gave in the gathering GOTO 2013¹. Douglas Crockford nailed it whenever he stated:
Pratt takes parsing which is a really complex item and reduces it to one uncomplicated question: What do we anticipate to see to the remaining of a token?
— Douglas Crockford, GOTO 2013
At archetypal glance it may appearance akin a mystical declaration devoid of meaning, but that's the inquiry that becomes the example on how you visage parsing problems and it'll rewire your brain to internalize the Pratt parsing mindset. That's the most crucial item you need to understand. You enroll semantic actions for two categories: nuds and leds. A nud is a token that expects nothing to its remaining (nud stands for null denotation) during a led expects item (led stands for remaining denotation).
Traditional parsing techniques enroll semantic actions to manufacturing rules. Here's an example I took direct 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 content between the braces is code that executes whenever the BNF-like grammar on the remaining matches. I'm gonna reiterate myself since that's really important: traditional parsing techniques enroll semantic actions to production rules (which by definition are non-terminal symbols). In difference Pratt parsing registers semantic actions to the terminals themselves instead. That's a essential change on how you visage parsing problems.
Here's a stripped downward type of the code for the tables that I have in my compiler correct 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>
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>
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>
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>
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>
All values on the remaining of all array are the lexer codes for terminal symbols. The values on the correct depend on the array kind:
Nud tablesFunctions matching the signature ExprPtr(Context&,reader,reader&)ExprPtr(Context&,reader,reader&).
Led tablesFunctions matching the signature ExprPtr(Context&,reader,reader&,ExprPtr)ExprPtr(Context&,reader,reader&,ExprPtr).
Binding power tablesPositive integers.
Most of the semantic actions in these tables have code whose implementation amount to one semicolon in their build at most. Here's the code for parse_unary_plus()parse_unary_plus():
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
On the exterior it may appear fair akin a distinct but motionless extremely akin way to arrange your code, but the effect is in fact huge. Here are a few differences from traditional parsing techniques that stem from this sole departure alone:
-
You don't need to concern concerning left-recursion problems that happen in traditional parsing techniques specified as LL(k). Given the dispatch to a semantic act is done alongside its connected token already consumed from the stream, left-recursion fair doesn't happen. It's a non-issue.
-
The parsing motor doesn't need to test alternatives or backtrack. The customary dichotomy between speed versus recollection that is established in several parsers (e.g. PEG vs packrat) is gone. Pratt is fast, and it's not gonna starve for insane amounts of memoization. Pratt is fair going to difference numbers, and iterate or recurse.
-
Related to the former point, but value to regard on its own: semantic actions run exactly once! That method there's no need to rollback to a former province if a equivalent fails. In another words your actions may merge side-effects. In my parser I use this asset to do name reservation/release on lexical range through a shared environment entity juggled through all layer. Just observe out to not abuse side-effects and end up alongside spaghetti.
-
Also related: your semantic act continually knows it's the accurate match. Therefore it may appearance arbitrarily far onward if it wants to. In another words: you can additional use PEG parsers (or layered Pratt parsers) in the semantic actions. While Pratt itself lone eats 1 token at a time, the nuds & leds themselves may eat additional tokens per round. You fair unlocked the power of parser combinators.
-
Most of the grammar ambiguities rotate into array collisions so you discarded small period on the simpler ambiguity cases. If you merge multiple parsers afterward it's motionless imaginable to have grammar ambiguities. So you motionless have activity as a grammar designer, but in my cognition it's much small work. When you merge parsers you're really combining grammars. Pratt as the parsing algorithm won't act as the all-seeing oracle and detect all imaginable ambiguity in the complete grammar amalgamation. Pratt (just akin PEG) volition fair come back the archetypal imaginable equivalent in this case.
-
Unfilled gaps in your tables rotate into trivial expansion points in your grammar. You may inhabit these gaps in reply to the content parsed so far. In another words you can execute macros and equal parse a tongue that extends its own operators. In difference extending a pre-existing grammar according to manufacturing rules (the orthodox parsing school) is a job value the complexity of PhD researches.
You may equal discover a few of these properties in the traditional academy as well, but lone to certain extents, or alongside a huge complexity toll.
Nonetheless I mentioned before that this institution is a mindset shift, but so far I've lone mentioned properties that you can use from adopting Pratt, so where's the change really? Consider the customary EBNF regulation for parsing function calls:
function_call = identifier, "(", [ argument_list ], ")" ; argument_list = expression, { ",", expression } ; function_call = identifier, "(", [ argument_list ], ")" ; argument_list = expression, { ",", expression } ; function_call = identifier, "(", [ argument_list ], ")" ; argument_list = expression, { ",", expression } ; function_call = identifier, "(", [ argument_list ], ")" ; argument_list = expression, { ",", expression } ; How do you method this issue whenever alternatively of manufacturing rules your toolbox contains lone nuds & leds? The key study is that the beginning parentheses continually anticipate item to its left, so it's a led. There you go: enroll a led for lparen and parse the function call from there. It's not immediately obvious, specially whenever you've lone been exposed to the traditional parsing school. Hence why Douglas Crockford nailed it whenever he stated:
Pratt takes parsing which is a really complex item and reduces it to one uncomplicated question: What do we anticipate to see to the remaining of a token?
— Douglas Crockford, GOTO 2013
The led for gathering indexing is extremely akin to the led for function call. Here's the assortment that I use in my own parser:
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::comma>()) {
throw unexpected_token{r, /*expected=*/"]"};
indexes.emplace_back(parse_expr(context, r, parse_until_end));
assert(r.code() == rbrack);
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::comma>()) {
throw unexpected_token{r, /*expected=*/"]"};
indexes.emplace_back(parse_expr(context, r, parse_until_end));
assert(r.code() == rbrack);
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::comma>()) {
throw unexpected_token{r, /*expected=*/"]"};
indexes.emplace_back(parse_expr(context, r, parse_until_end));
assert(r.code() == rbrack);
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
std::vector<std::shared_ptr<ast::Expr>> indexes;
if (r.code() != rbrack) {
indexes.emplace_back(parse_expr(context, r, parse_until_end));
while (r.code() != rbrack) {
if (!r.eat<code::comma>()) {
throw unexpected_token{r, /*expected=*/"]"};
indexes.emplace_back(parse_expr(context, r, parse_until_end));
assert(r.code() == rbrack);
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
Pratt is not fair precedence climbing. Pratt is a way to arrange your code. First learning Pratt as a dreary box really helps to comprehend this difference. If you don't have admission to the dreary box, you won't be tempted to decrease Pratt to precedence climbing. Hopefully by the period you desire to obtain distant the idea and see what's inner you won't create the error of treating Pratt fair akin a uncomplicated assortment of precedence climbing since by afterward you'll have already been exposed to all the power unlocked by Pratt parsing. Andy Chu's blog article on Pratt parsing without prototypal bequest is value study as it contrasts two opposing styles of penning Pratt parsers². Here's a minimal calculator written in Rhombus that is (stylistically) nearer to a type that'd use prototypal bequest than the manner that Andy Chu shows:
class Token(~nud: nud_impl = #false, method nud(): nud_impl(this) method led(lhs): led_impl(this, lhs) method prefix(): expression(30) method rhs(): expression(this.lbp) class RParen(): extends Token ~led: fun(tok, lhs): lhs + tok.rhs(), ~led: fun(tok, lhs): lhs - tok.rhs(), ~led: fun(tok, lhs): lhs * tok.rhs(), ~led: fun(tok, lhs): lhs / tok.rhs(), | digit+: Token(~nud: fun(_): String.to_int(lexeme)) | error("expected decision parens") def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10") def mutable token = lex(input) fun advance(): token := lex(input) let mutable remaining = t.nud() class Token(~nud: nud_impl = #false, method nud(): nud_impl(this) method led(lhs): led_impl(this, lhs) method prefix(): expression(30) method rhs(): expression(this.lbp) class RParen(): extends Token ~led: fun(tok, lhs): lhs + tok.rhs(), ~led: fun(tok, lhs): lhs - tok.rhs(), ~led: fun(tok, lhs): lhs * tok.rhs(), ~led: fun(tok, lhs): lhs / tok.rhs(), | digit+: Token(~nud: fun(_): String.to_int(lexeme)) | error("expected decision parens") def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10") def mutable token = lex(input) fun advance(): token := lex(input) let mutable remaining = t.nud() class Token(~nud: nud_impl = #false, method nud(): nud_impl(this) method led(lhs): led_impl(this, lhs) method prefix(): expression(30) method rhs(): expression(this.lbp) class RParen(): extends Token ~led: fun(tok, lhs): lhs + tok.rhs(), ~led: fun(tok, lhs): lhs - tok.rhs(), ~led: fun(tok, lhs): lhs * tok.rhs(), ~led: fun(tok, lhs): lhs / tok.rhs(), | digit+: Token(~nud: fun(_): String.to_int(lexeme)) | error("expected decision parens") def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10") def mutable token = lex(input) fun advance(): token := lex(input) let mutable remaining = t.nud() class Token(~nud: nud_impl = #false, method nud(): nud_impl(this) method led(lhs): led_impl(this, lhs) method prefix(): expression(30) method rhs(): expression(this.lbp) class RParen(): extends Token ~led: fun(tok, lhs): lhs + tok.rhs(), ~led: fun(tok, lhs): lhs - tok.rhs(), ~led: fun(tok, lhs): lhs * tok.rhs(), ~led: fun(tok, lhs): lhs / tok.rhs(), | digit+: Token(~nud: fun(_): String.to_int(lexeme)) | error("expected decision parens") def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10") def mutable token = lex(input) fun advance(): token := lex(input) let mutable remaining = t.nud() Algorithmic & grammar constraints
The former division power have been the densest in this entire blog article so I desire to tune it downward during you incubate the Pratt mindset and go on trivial things for now:
-
Pratt requires a distinct lexer. Some contemporary parsing engines can activity in a scannerless manner (e.g. PEG) or equal embed the lexer definition immediately in the parser itself, but Pratt requires a distinct lexer. That shouldn't be a big concern, but it's item to keep in mind.
-
Pratt is fast. The algorithm lone compares numbers and iterate or recurse. It's lone looking 1 token ahead, and not doing item alternatively really. It doesn't go rear to test alternatives or to backtrack on unsuccessful manufacturing rules. It fair doesn't go rear at all. It's a full-speed locomotive lone looking onward dining 1 token at a time.
-
Given Pratt itself is already fast, if you desire to optimize anything, the lone item remaining is the dispatch code for nuds & leds. In my case I use earth read-only dispatch tables, but most of the tutorials I've seen in the untamed use energetic objects in extremely energetic scripting languages.
-
Pratt can't parse statements. You have to merge it alongside another techniques to parse languages alongside statements. I've already gone through this constraint in my final blog article anywhere you can discover solutions.
-
Pratt is a form of recursive decline parsing definition it's operating tradition person code (i.e. code in a Turing-complete language) for the semantic actions, but that's not the entire picture. The semantic actions additional run the parsing choices/direction which method that your code power appearance at the environment (e.g. former declarations) to decide how to parse the next part of the input text. In summary you can have several forms of context-sensitive parsing which opens the entrance for additional classes of languages.
-
You'll have to retreat to modal lexing to parse several complex languages established in the wild, but I'll reserve a afterward division of this blog article to contact on this topic.
-
Pratt can't be used for incremental parsing as done in GLR parsing. However that's not a power established in most parsing algorithms anyhow (I'm operating out of algorithmic properties to conversation about). Incremental parsing is used in tools specified as tree-sitter.
Right-to-left associative operators
My entire disagreement today is that Pratt is a dreary box abstraction, so let's go alongside this disagreement and lay downward what contracts you need to regard to use Pratt:
-
Only tokens alongside connected leds need a value in the binding power table. Tutorials in the untamed are normally written in a way anywhere this asset isn't obvious. It becomes additional apparent whenever you compose your parser using fixed tables fairly than extremely energetic objects in scripting languages.
-
Related to the former point: You motionless need a value for the binding power of prefix operators, but this value isn't used in the Pratt iteration at all. Therefore it's not a necessity to inflate the binding power array alongside a value for the prefix operators, but that's what most of the code I've seen in the untamed do anyway. If you think it's easier to fair material the binding power for prefix operators in the identical array be my visitant and go ahead. Just withstand in intellect that this famous institution isn't a difficult requirement. Only the nud implementing the prefix controller itself needs to cognize the binding power for prefix operators.
-
Never allocate a binding power of zero to a led.
-
Separators specified as comma and unknown/error/EOF tokens anywhere the parser must halt should have a binding power of zero. They don't need to be in the binding power table.
-
If you're penning in decimal akin all individual being, clasp increments of 10 in the binding power table. When study these values, you may fair disregard the final zero, but the additional area between operators enables several tricks.
So how do we execute right-to-left associative operators alongside Pratt? First let's appearance at a average left-to-right associative infix operator. Here's my code for the led ++:
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
auto correct = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
auto correct = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
auto correct = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
static constexpr auto bp =
binding_power[static_cast<unsigned>(code::plus_sign)];
std::shared_ptr<ast::Expr> parse_addition(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
auto correct = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
If we wanted to create the controller right-to-left associative, we'd fair need to use bp - 1bp - 1 alternatively of bpbp:
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
bp /* HERE'S THE DIFFERENCE: */ - 1
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
bp /* HERE'S THE DIFFERENCE: */ - 1
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
bp /* HERE'S THE DIFFERENCE: */ - 1
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, audience tok, reader& r,
std::shared_ptr<ast::Expr> left)
bp /* HERE'S THE DIFFERENCE: */ - 1
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
That's a norm trick in the site of Pratt parsing. A trick of the commerce so to speak. A trick you ought to know. Why does it work? It doesn't matter. It's a dreary box for today. Tomorrow it power matter, but today you should lone be focusing on how to use Pratt, not why it works.
Macros openly interleave between lexing & parsing
Why equal compose a division for macros whenever most tongue designers won't add them? Pratt macros are fair nuds/leds implemented in the tongue that your code is parsing and interpreting. Therefore item that your own nuds/leds can do is item that ought to be imaginable in a macro and vice-versa. Lessons learned from Pratt macros are lessons learned on Pratt parsing itself.
That's fair a principle, and not a hard-truth. It's certainly not a fact in the Pratt macros of my own language, for instance, but the regulation remains my guide (and hopefully yours as well).
The implementation of macros exterior Lisp are traditionally extremely constricted in many fronts. In languages specified as C you have macros that are fair textual substitution templates that activity in the surroundings of a preprocessor doing textual enlargement (therefore operating on the lexing layer). It's additionally imaginable to scheme macros that activity in the AST/parsing tier specified as done in Lisp. However Pratt macros unify these two earlier severed worlds. If you're implementing procedural Pratt macros afterward it's imaginable for the macro to use APIs that alternately invoke either the lexer or the parser. My own macro scheme doesn't yet have adequate APIs so I can't showcase a genuine example, but here's how envision that it's gonna work:
// functions whose name commencement alongside "read" // run the lexer (i.e. they fair consume // functions whose name commencement alongside "parse" // run the parser (i.e. they consume and // come back parsed expressions) let expr = ctx.parse_expr(); // fair akin Rust, my own macro scheme requires a // macro invocation to end alongside an exclamation mark // to act as a affable ocular clue that something // comic power be going on passthrough!(std.puts("hello world")); // functions whose name commencement alongside "read" // run the lexer (i.e. they fair consume // functions whose name commencement alongside "parse" // run the parser (i.e. they consume and // come back parsed expressions) let expr = ctx.parse_expr(); // fair akin Rust, my own macro scheme requires a // macro invocation to end alongside an exclamation mark // to act as a affable ocular clue that something // comic power be going on passthrough!(std.puts("hello world")); // functions whose name commencement alongside "read" // run the lexer (i.e. they fair consume // functions whose name commencement alongside "parse" // run the parser (i.e. they consume and // come back parsed expressions) let expr = ctx.parse_expr(); // fair akin Rust, my own macro scheme requires a // macro invocation to end alongside an exclamation mark // to act as a affable ocular clue that something // comic power be going on passthrough!(std.puts("hello world")); // functions whose name commencement alongside "read" // run the lexer (i.e. they fair consume // functions whose name commencement alongside "parse" // run the parser (i.e. they consume and // come back parsed expressions) let expr = ctx.parse_expr(); // fair akin Rust, my own macro scheme requires a // macro invocation to end alongside an exclamation mark // to act as a affable ocular clue that something // comic power be going on passthrough!(std.puts("hello world")); These APIs are beautiful much what's already used in the center nuds of many parsers using Pratt. A macro scheme lone needs to disclose them to the macros as fine to get this far. This part is really easy. Tasks really challenging in macro systems live elsewhere, not here. The hardest part of a macro scheme is hygiene³⁴, not parsing (well… parsing is gonna be uncomplicated if you use Pratt parsing at least). However this blog article is concerning (Pratt) parsing, not macro systems, so I'm not gonna delve on hygiene or another macro scheme challenges (problems which I've already battled alongside and ultimately won).
The takeaway current is that Pratt parsing enables languages alongside mighty macros that can execute beautiful unconstrained eDSLs. Pratt macros are fair an translator for your tongue that has admission to the lexer and the parser at the item anywhere the macro is being expanded. Patterns that you use in your nuds & leds are patterns that you'd apt see in Pratt macros. The code being parsed is instruction the extremely parser that is parsing it on how to do so (tell me concerning meta!).
Usually the lexer is the most neglected part of a compiler. It's a solved problem. There's no logic to discarded period on its design. You use a lexer generator to execute an productive lexer, and move on to never appearance rear again. However Pratt – the algorithm – is fair 9 lines of Rhombus code. Your lexer is most apt bigger than the parser already. Just on the visage of this your lexer is already playing a bigger part on your project by at smallest several metric (even if an unimportant one).
However it goes additional than this. Every nud and led in your code is a subparser of sorts. Combining (sub)parsers is key to unlocking the power to parse equal additional classes of languages. The lexer becomes the sole item in average that trespass the walls between all subparsers. A fine lexer scheme improves parser composability.
As a practitioner of the Pratt school, the sole most crucial lexing method you should study is modal lexing. The method is already helpful on its own equal if you're not using Pratt, but it's equal additional so for us. As Andy Chu succinctly explains⁵, modal lexing is enabled by adding an additional indicator to your lexer:
// all manner triggers distinct lexing rules
Token Read(lex_mode_t mode);
// all manner triggers distinct lexing rules
Token Read(lex_mode_t mode);
// all manner triggers distinct lexing rules
Token Read(lex_mode_t mode);
// all manner triggers distinct lexing rules
Token Read(lex_mode_t mode);
There are another ways to province the identical pattern. For my own project, I favor to use distinct functions alternatively of an enum. As a C++ programmer I've been trained fine to discern between cases of fixed versus energetic polymorphism, and here's a case anywhere plainly the dispatching data is completely known statically at compile time. Hence it doesn't create awareness to equal use an enum. The narrative could be distinct in extremely energetic macro-enabled languages though.
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
Simple as it is, this sole defining trait of modal lexing unlocks the capability to parse many additional complex classes of languages by providing a way for the lexer to obtain feedback from the parser. Lexers never cognize grammatical structure, but the parser continually does. By feeding this data from the parser rear to the lexer you allow forms of tongue construction anywhere all sublanguage power have conflicting token definitions (e.g. C++11's right-shift controller spawns distinct tokens in template contexts) or fair tokens alongside distinct meanings altogether. Andy Chu already gave thorough examples on anywhere this power be useful⁶ so current I'll lone annoy to contribute a sole example to the corpus.
In Rust you have a distinct sublanguage fair to province types. This category note happens in neatly delimited places inner the "main" language. It normally happens following the colon and ends on the equals-sign or delimiters specified as commas or the decision parentheses:
let my_variable: category note goes here; let another_variable: the category = a_value; fn a_function(arg1: a_type, arg2: another_type) {} let my_variable: category note goes here; let another_variable: the category = a_value; fn a_function(arg1: a_type, arg2: another_type) {} let my_variable: category note goes here; let another_variable: the category = a_value; fn a_function(arg1: a_type, arg2: another_type) {} let my_variable: category note goes here; let another_variable: the category = a_value; fn a_function(arg1: a_type, arg2: another_type) {} My tongue syntax is heavily inspired by Rust's. Naturally I depend on modal lexing to parse these structures. The function reader::next_on_type_scope()reader::next_on_type_scope() shown before is used for the category note sublanguage. Then I have a Pratt parser for all – parse_expr()parse_expr() and parse_type()parse_type(). It's a uncomplicated trick that doesn't petition much clarification really, but gets you extremely far. The code nearly writes itself following you get the idea.
The lone caveat is that your lexer must adhere to a drag scheme alternatively of lexing all tokens upfront. For several logic group akin to lone scheme shove APIs that completely pilfer implementation flow, and these group are addicted to execute lexers that do all the activity upfront. It's a famous arrangement, but not one that volition activity for modal lexing. Pratt itself is a shove scheme so in the end you'd have a mix of designs.
Moving on to the next topic, there are additional lexer tricks that I have to share, but for today I fair have one suggestion: don't scheme your lexers to do any IO (syscalls) nor to buffer anything. Working on a copy of your lexer shouldn't have observable side-effects on the first object. Copies have to be cheap and encouraged. Working on a copy of the lexer enables arbitrary lookahead which power be required by several subparser. Even if you lone requires a fixed amount of lookahead (e.g. 3 tokens) this scheme fits the gap all the same.
Fulfilling this scheme is easy: fair peruse the entire document at formerly (or use mmap) and create the lexer item to this shared area to do its job. Your AST solitary is apt gonna use additional recollection than the entire input document anyhow so recollection shouldn't be a involvement here.
Now let's revisit my nud for ++:
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, audience tok, reader& r)
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
Most of the code that I see on the untamed has a tradition category for tokens, and that's get used as disagreement for the nuds & leds, but I fair store/pass the lexer itself instead. My lexer is cheap to copy so there's no need to create a category to continue tokens around. The tier expecting a token can decode from the matched lexeme immediately anyhow so the lexer lone needs to shop a few pointers to the first input text. Here's the code parsing decimal literals in my project to showcase the decode-from-lexeme-directly trick:
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, audience tok, reader& /*r*/)
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, audience tok, reader& /*r*/)
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, audience tok, reader& /*r*/)
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
std::shared_ptr<ast::Expr> parse_declit(
ParsingContext& /*context*/, audience tok, reader& /*r*/)
auto apint = syntax::parse_declit(tok.literal());
return ast::make_expr<ast::IntegerValue>(
tok.line(), tok.column(),
llvm::DynamicAPInt{apint.zext(apint.getBitWidth() + 1)});
Furthermore this scheme allows me to rollback 1 token which is item that I use in the nud for <<:
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, audience tok, reader& r)
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// current we re-lex the next token (after the rollback
// fair above) using the rules for type-scope (a
// distinct sublanguage alongside distinct tokens)
// afterward we we call parse_type() (instead of parse_expr())
auto& category = parse_type(context, r, parse_until_end);
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, audience tok, reader& r)
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// current we re-lex the next token (after the rollback
// fair above) using the rules for type-scope (a
// distinct sublanguage alongside distinct tokens)
// afterward we we call parse_type() (instead of parse_expr())
auto& category = parse_type(context, r, parse_until_end);
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, audience tok, reader& r)
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// current we re-lex the next token (after the rollback
// fair above) using the rules for type-scope (a
// distinct sublanguage alongside distinct tokens)
// afterward we we call parse_type() (instead of parse_expr())
auto& category = parse_type(context, r, parse_until_end);
// this nud is called by parse_expr() (hence expr-scope)
std::shared_ptr<ast::Expr> parse_enter_type_scope(
ParsingContext& context, audience tok, reader& r)
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// current we re-lex the next token (after the rollback
// fair above) using the rules for type-scope (a
// distinct sublanguage alongside distinct tokens)
// afterward we we call parse_type() (instead of parse_expr())
auto& category = parse_type(context, r, parse_until_end);
This trick additionally requires a lexer that represents error as a dedicated token code alternatively of raising exceptions whenever they happen. You may motionless use exceptions if you desire whenever an error is fatal for all sublanguages (e.g. non-ASCII character established on the stream).
Now what's this nud equal parsing power be a valid question, so let's go complete exactly what it's doing. Rust (which inspired my language's syntax heavily) allows one to admission sectors from a type. Field admission current is done using the controller ::::. For instance:
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
use std::time::SystemTime;
let now = SystemTime::now();
However what happens whenever referring to your category requires admission to the category note tongue specified as in the case for generics? Then you need an "escape hatch" in the chief tongue to admission the category note tongue explicitly, and that's done through the nud for <<:
// Inside the external <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner viewpoint brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the external <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner viewpoint brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the external <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner viewpoint brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the external <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner viewpoint brackets must be balanced.
let my_vec = <Vec<u32>>::new();
So now you cognize how to parse this category of grammars alongside Pratt. Simon Ochsenreither formerly asserted that using <><> for generics is bad design⁷, so perchance it's no coincidence that that's the lone period that I really had to use the rollback trick (which I regard a hack) in my project. Nevertheless it was the finest colony I could discover so I went alongside it anyway. Language scheme is hard.
I have a lot additional of lexer tricks to share, but I'm emotion that I should postpone them to afterward articles. Some of them are already used in my project. Ironically perhaps, but I acquired the mindset that enabled me to arrive up alongside these lexer tricks from former cognition parsing HTTP and JSON which has nothing to do alongside the techniques that one uses to parse programming languages.
Pratt is a change in parsing mindset. You must get comfortable on breaking grammatical structures into nuds & leds. It's totally fine to compose shortcuts that eliminate the boilerplate by factoring the average parts of the implementation of prefix, infix and postfix operators as done by Douglas Crockford⁸, but if you're changing Pratt's algorithm itself as done by Alex Kladov in 2020⁹ (I've done the identical error myself once) to create accommodations since you refuse to logic in conditions of nuds & leds (or any another reason), you're missing out and should commencement over. Using Pratt parsing as a dreary box idea volition eliminate your capability to alter Pratt's algorithm, and it may assistance in adapting your mindset. That's my direction to get you started.
I have a lot additional of parsing tricks to portion (e.g. Pratt-walk interpreters, REPLs alongside ideal auto-completion), but they're additional advanced, and I'll postpone them to afterward articles.
