Pratt parsing is a black box
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.
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.

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.
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:
— 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, 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>
);
All values on the left of each table are the lexer codes for terminal symbols. The values on the right depend on the table kind:
Nud tablesFunctions matching the signature ExprPtr(Context&,reader,reader&)ExprPtr(Context&,reader,reader&).
Functions matching the signature ExprPtr(Context&,reader,reader&,ExprPtr)ExprPtr(Context&,reader,reader&,ExprPtr).
Positive integers.
Most of the semantic actions in these tables have code whose implementation amount to one semicolon in their body at most. Here's the code for parse_unary_plus()parse_unary_plus():
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader 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, reader 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, reader 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, reader tok, reader& r)
{
return ast::make_expr<ast::UnaryPlus>(
tok.line(), tok.column(),
parse_expr(context, r, prefix_operator_binding_power));
}
On the surface it may seem just like a different but still very similar way to organize your code, but the impact is in fact huge. Here are a few differences from traditional parsing techniques that stem from this single departure alone:
You may even find a few of these properties in the traditional school as well, but only to certain extents, or with a huge complexity toll.
Nonetheless I mentioned earlier that this organization is a mindset shift, but so far I've only mentioned properties that you can use from adopting Pratt, so where's the shift really? Consider the usual EBNF rule 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 approach this problem when instead of production rules your toolbox contains only nuds & leds? The key observation is that the opening parentheses always expect something to its left, so it's a led. There you go: register a led for lparen and parse the function call from there. It's not immediately obvious, specially when you've only been exposed to the traditional parsing school. Hence why Douglas Crockford nailed it when he stated:
— Douglas Crockford, GOTO 2013
The led for array indexing is very similar to the led for function call. Here's the variation that I use in my own parser:
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader 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);
r.next_on_expr_scope();
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader 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);
r.next_on_expr_scope();
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader 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);
r.next_on_expr_scope();
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
std::shared_ptr<ast::Expr> parse_array_indexing(
ParsingContext& context, reader 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);
r.next_on_expr_scope();
return ast::make_expr<ast::ArrayIndexing>(
tok.line(), tok.column(), left, std::move(indexes));
}
Pratt is not just precedence climbing. Pratt is a way to organize your code. First learning Pratt as a black box actually helps to understand this difference. If you don't have access to the black box, you won't be tempted to reduce Pratt to precedence climbing. Hopefully by the time you want to take away the abstraction and see what's inside you won't make the mistake of treating Pratt just like a mere variation of precedence climbing because by then you'll have already been exposed to all the power unlocked by Pratt parsing. Andy Chu's blog post on Pratt parsing without prototypal inheritance is worth reading as it contrasts two opposing styles of writing Pratt parsers². Here's a minimal calculator written in Rhombus that is (stylistically) closer to a version that'd use prototypal inheritance than the style that Andy Chu shows:
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
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
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
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
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
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
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
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
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
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
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
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
println(expression())
#lang rhombus
import:
parser/lex open
class Token(~nud: nud_impl = #false,
~led: led_impl = #false,
~lbp = 0):
nonfinal
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
def lex:
lexer
| "+": Token(
~nud: (_.prefix()),
~led: fun(tok, lhs): lhs + tok.rhs(),
~lbp: 10)
| "-": Token(
~nud: (-_.prefix()),
~led: fun(tok, lhs): lhs - tok.rhs(),
~lbp: 10)
| "*": Token(
~led: fun(tok, lhs): lhs * tok.rhs(),
~lbp: 20)
| "/": Token(
~led: fun(tok, lhs): lhs / tok.rhs(),
~lbp: 20)
| digit+: Token(~nud: fun(_): String.to_int(lexeme))
| " "+: lex(input_port)
| "(": Token(
~nud: fun(_):
let ret = expression()
guard token is_a RParen
| error("expected closing parens")
advance()
ret)
| ")": RParen()
| ~eof: Token()
def input = Port.Input.open_string("4 * (3 - 3) / 2 + -10")
def mutable token = lex(input)
fun advance(): token := lex(input)
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
println(expression())
The previous section might have been the densest in this whole blog post so I want to tune it down while you incubate the Pratt mindset and go on trivial things for now:
My whole argument today is that Pratt is a black box abstraction, so let's go with this argument and lay down what contracts you need to respect to use Pratt:
So how do we implement right-to-left associative operators with Pratt? First let's look at a common 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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = 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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = 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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = 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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(context, r, bp);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
If we wanted to make the operator right-to-left associative, we'd just need to use bp - 1bp - 1 instead of bpbp:
std::shared_ptr<ast::Expr> parse_additionr(
ParsingContext& context, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
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, reader tok, reader& r,
std::shared_ptr<ast::Expr> left)
{
auto right = parse_expr(
context,
r,
bp /* HERE'S THE DIFFERENCE: */ - 1
);
return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}
That's a standard trick in the field of Pratt parsing. A trick of the trade so to speak. A trick you ought to know. Why does it work? It doesn't matter. It's a black box for today. Tomorrow it might matter, but today you should only be focusing on how to use Pratt, not why it works.
Why even write a section for macros when most language designers won't add them? Pratt macros are just nuds/leds implemented in the language that your code is parsing and interpreting. Therefore anything that your own nuds/leds can do is something that ought to be possible in a macro and vice-versa. Lessons learned from Pratt macros are lessons learned on Pratt parsing itself.
That's just a principle, and not a hard-truth. It's definitely not a truth in the Pratt macros of my own language, for instance, but the principle remains my guide (and hopefully yours as well).
The implementation of macros outside Lisp are traditionally very limited in many fronts. In languages such as C you have macros that are just textual substitution templates that work in the environment of a preprocessor doing textual expansion (therefore working on the lexing layer). It's also possible to design macros that work in the AST/parsing layer such as done in Lisp. However Pratt macros unify these two previously severed worlds. If you're implementing procedural Pratt macros then it's possible for the macro to use APIs that alternately invoke either the lexer or the parser. My own macro system doesn't yet have enough APIs so I can't showcase a real example, but here's how envision that it's gonna work:
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
macro passthrough(ctx) {
// functions whose name start with "read"
// drive the lexer (i.e. they just consume
// tokens)
ctx.read("(");
// functions whose name start with "parse"
// drive the parser (i.e. they consume and
// return parsed expressions)
let expr = ctx.parse_expr();
ctx.read(")");
return expr;
}
// just like Rust, my own macro system requires a
// macro invocation to end with an exclamation mark
// to act as a friendly visual hint that something
// funny might be going on
passthrough!(std.puts("hello world"));
These APIs are pretty much what's already used in the core nuds of many parsers using Pratt. A macro system only needs to expose them to the macros as well to get this far. This part is actually easy. Tasks actually challenging in macro systems reside elsewhere, not here. The hardest part of a macro system is hygiene³⁴, not parsing (well… parsing is gonna be easy if you use Pratt parsing at least). However this blog post is about (Pratt) parsing, not macro systems, so I'm not gonna delve on hygiene or other macro system challenges (problems which I've already battled with and ultimately won).
The takeaway here is that Pratt parsing enables languages with powerful macros that can implement beautiful unconstrained eDSLs. Pratt macros are just an interpreter for your language that has access to the lexer and the parser at the point where the macro is being expanded. Patterns that you use in your nuds & leds are patterns that you'd likely see in Pratt macros. The code being parsed is teaching the very parser that is parsing it on how to do so (tell me about meta!).
Usually the lexer is the most neglected part of a compiler. It's a solved problem. There's no reason to waste time on its design. You use a lexer generator to implement an efficient lexer, and move on to never look back again. However Pratt – the algorithm – is just 9 lines of Rhombus code. Your lexer is most likely bigger than the parser already. Just on the face of this your lexer is already playing a bigger part on your project by at least some metric (even if an unimportant one).
However it goes further 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 even more classes of languages. The lexer becomes the single point in common that trespass the walls between all subparsers. A good lexer design improves parser composability.
As a practitioner of the Pratt school, the single most important lexing technique you should learn is modal lexing. The technique is already useful on its own even if you're not using Pratt, but it's even more so for us. As Andy Chu succinctly explains⁵, modal lexing is enabled by adding an extra parameter to your lexer:
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
// traditional lexer
Token Read();
// modal lexer
// each mode triggers different lexing rules
Token Read(lex_mode_t mode);
There are other ways to express the same pattern. For my own project, I prefer to use separate functions instead of an enum. As a C++ programmer I've been trained well to discern between cases of static versus dynamic polymorphism, and here's a case where clearly the dispatching information is fully known statically at compile time. Hence it doesn't make sense to even use an enum. The story could be different in highly dynamic macro-enabled languages though.
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
void next_on_class_scope();
void next_on_type_scope();
void next_on_expr_scope();
void next_on_skim_scope();
// ...
};
class reader
{
public:
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 single defining trait of modal lexing unlocks the ability to parse many more complex classes of languages by providing a way for the lexer to receive feedback from the parser. Lexers never know grammatical structure, but the parser always does. By feeding this information from the parser back to the lexer you enable forms of language composition where each sublanguage might have conflicting token definitions (e.g. C++11's right-shift operator spawns different tokens in template contexts) or just tokens with different meanings altogether. Andy Chu already gave comprehensive examples on where this might be useful⁶ so here I'll only bother to contribute a single example to the corpus.
In Rust you have a different sublanguage just to express types. This type annotation happens in neatly delimited places inside the "main" language. It usually happens after the colon and ends on the equals-sign or delimiters such as commas or the closing parentheses:
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
let my_variable: type annotation goes here;
let another_variable: the type = a_value;
fn a_function(arg1: a_type, arg2: another_type) {}
My language syntax is heavily inspired by Rust's. Naturally I rely on modal lexing to parse these structures. The function reader::next_on_type_scope()reader::next_on_type_scope() shown earlier is used for the type annotation sublanguage. Then I have a Pratt parser for each – parse_expr()parse_expr() and parse_type()parse_type(). It's a simple trick that doesn't demand much explanation really, but gets you very far. The code almost writes itself after you get the idea.
The only caveat is that your lexer must adhere to a pull design instead of lexing all tokens upfront. For some reason people like to only design push APIs that fully steal execution flow, and these people are addicted to implement lexers that do all the work upfront. It's a popular arrangement, but not one that will work for modal lexing. Pratt itself is a push design so in the end you'd have a mix of designs.
Moving on to the next topic, there are more lexer tricks that I have to share, but for today I just have one suggestion: don't design 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 original object. Copies should be cheap and encouraged. Working on a copy of the lexer enables arbitrary lookahead which might be required by some subparser. Even if you only requires a fixed amount of lookahead (e.g. 3 tokens) this design fits the hole all the same.
Fulfilling this design is easy: just read the whole file at once (or use mmap) and make the lexer point to this shared region to do its job. Your AST alone is likely gonna use more memory than the whole input file anyway so memory shouldn't be a concern here.
Now let's revisit my nud for ++:
std::shared_ptr<ast::Expr> parse_unary_plus(
ParsingContext& context, reader 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, reader 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, reader 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, reader 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 wild has a custom type for tokens, and that's get used as argument for the nuds & leds, but I just store/pass the lexer itself instead. My lexer is cheap to copy so there's no need to create a class to pass tokens around. The layer expecting a token can decode from the matched lexeme directly anyway so the lexer only needs to store a few pointers to the original 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*/, reader 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*/, reader 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*/, reader 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*/, reader 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 design allows me to rollback 1 token which is something 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, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = 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, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = 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, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = 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, reader tok, reader& r)
{
assert(tok.code() == code::less_than_sign);
r = tok; //< 1-token rollback happens here
// here we re-lex the next token (after the rollback
// just above) using the rules for type-scope (a
// different sublanguage with different tokens)
r.next_on_type_scope();
// then we we call parse_type() (instead of parse_expr())
auto& type = parse_type(context, r, parse_until_end);
// ...
}
This trick also requires a lexer that represents error as a dedicated token code instead of raising exceptions when they happen. You may still use exceptions if you want when an error is fatal for all sublanguages (e.g. non-ASCII character found on the stream).
Now what's this nud even parsing might be a valid question, so let's go over exactly what it's doing. Rust (which inspired my language's syntax heavily) allows one to access fields from a type. Field access here is done using the operator ::::. 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 when referring to your type requires access to the type annotation language such as in the case for generics? Then you need an "escape hatch" in the main language to access the type annotation language explicitly, and that's done through the nud for <<:
// Inside the outer <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
// Inside the outer <>, we don't interpret
// `Vec < u32` as `Vec less-than u32`.
// Inner angle brackets must be balanced.
let my_vec = <Vec<u32>>::new();
So now you know how to parse this type of grammars with Pratt. Simon Ochsenreither once argued that using <><> for generics is bad design⁷, so maybe it's no coincidence that that's the only time that I actually had to use the rollback trick (which I consider a hack) in my project. Nevertheless it was the best compromise I could find so I went with it anyway. Language design is hard.
I have a lot more of lexer tricks to share, but I'm feeling that I should postpone them to later articles. Some of them are already used in my project. Ironically perhaps, but I acquired the mindset that enabled me to come up with these lexer tricks from past experience parsing HTTP and JSON which has nothing to do with the techniques that one uses to parse programming languages.
Pratt is a shift in parsing mindset. You must get comfortable on breaking grammatical structures into nuds & leds. It's totally okay to write shortcuts that remove the boilerplate by factoring the common 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 same mistake myself once) to make accommodations because you refuse to reason in terms of nuds & leds (or any other reason), you're missing out and should start over. Using Pratt parsing as a black box abstraction will remove your ability to change Pratt's algorithm, and it may help in adapting your mindset. That's my advice to get you started.
I have a lot more of parsing tricks to share (e.g. Pratt-walk interpreters, REPLs with perfect auto-completion), but they're more advanced, and I'll postpone them to later articles.
Texto de vinipsmaker.github.io tal como lo publicó, leído de su página y mostrado aquí con el formato de El Autómata. El original, en vinipsmaker.github.io · Volver a la noticia de El Autómata