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_ptrast::Expr parse_array_indexing(

ParsingContext& context, reader tok, reader& r,

std::shared_ptrast::Expr left)

{

std::vector<std::shared_ptrast::Expr> indexes;

if (r.code() != rbrack) {

indexes.emplace_back(parse_expr(context, r, parse_until_end));

while (r.code() != rbrack) {

if (!r.eatcode::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_exprast::ArrayIndexing(

tok.line(), tok.column(), left, std::move(indexes));

}

std::shared_ptrast::Expr parse_array_indexing(

ParsingContext& context, reader tok, reader& r,

std::shared_ptrast::Expr left)

{

std::vector<std::shared_ptrast::Expr> indexes;

if (r.code() != rbrack) {

indexes.emplace_back(parse_expr(context, r, parse_until_end));

while (r.code() != rbrack) {

if (!r.eatcode::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_exprast::ArrayIndexing(

tok.line(), tok.column(), left, std::move(indexes));

}

std::shared_ptrast::Expr parse_array_indexing(

ParsingContext& context, reader tok, reader& r,

std::shared_ptrast::Expr left)

{

std::vector<std::shared_ptrast::Expr> indexes;

if (r.code() != rbrack) {

indexes.emplace_back(parse_expr(context, r, parse_until_end));

while (r.code() != rbrack) {

if (!r.eatcode::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_exprast::ArrayIndexing(

tok.line(), tok.column(), left, std::move(indexes));

}

std::shared_ptrast::Expr parse_array_indexing(

ParsingContext& context, reader tok, reader& r,

std::shared_ptrast::Expr left)

{

std::vector<std::shared_ptrast::Expr> indexes;

if (r.code() != rbrack) {

indexes.emplace_back(parse_expr(context, r, parse_until_end));

while (r.code() != rbrack) {

if (!r.eatcode::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_exprast::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())

Algorithmic & grammar constraints

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:

Pratt requires a separate lexer. Some modern parsing engines can work in a scannerless manner (e.g. PEG) or even embed the lexer definition directly in the parser itself, but Pratt requires a separate lexer. That shouldn't be a big concern, but it's something to keep in mind.

Pratt is fast. The algorithm only compares numbers and iterate or recurse. It's only looking 1 token ahead, and not doing anything else really. It doesn't go back to test alternatives or to backtrack on failed production rules. It just doesn't go back at al