5.4 Pratt Parsing for Expressions

Recursive descent is excellent for declarations, statements, and delimiters. Expressions are the part that tends to grow teeth: prefix operators, postfix calls, member access, indexing, precedence, associativity, ternaries, and custom operators can turn a ladder of parseTerm, parseFactor, and parsePrimary functions into a fragile tower. A Pratt parser gives tokens small parsing behaviors and drives them with binding powers.

Pratt parsing is still top-down. It is not a parser generator, and it does not eliminate the need for a lexer or AST design. Its central question is: “given the expression parsed so far, does the next token bind tightly enough to extend it?”

Prefix and Infix Parselets

Each token can have two roles:

• A prefix parselet (often called nud, for null denotation) parses a token that begins an expression: a number, identifier, parenthesized expression, prefix -, or !.

• An infix or postfix parselet (often called led, for left denotation) parses a token that extends an already parsed left expression: +, *, ( for a call, [ for indexing, or . for member access.

The core routine is compact:

parseExpression(minBP = 0): Expr {
  const token = advance();
  let left = prefixParselet(token).parse(this, token);

  while (minBP < bindingPower(peek().kind)) {
    const operator = advance();
    left = infixParselet(operator).parse(this, left, operator);
  }
  return left;
}

The exact comparison convention can be minBP < nextBP or a related pair of left/right binding powers. Pick one convention and document it; mixing conventions is the quiet source of many associativity bugs. Tokens without a valid prefix parselet should produce a localized “expected expression” error. Tokens without an infix parselet simply end the current expression when their binding power is zero, which is why ), ], ,, ;, and EOF naturally act as delimiters.

Precedence and Associativity Are Data

Give operators binding powers in a table rather than scattering precedence knowledge across unrelated functions:

lowest:  assignment =
10:      conditional ?:
20:      equality == !=
30:      comparison < <= > >=
40:      sum + -
50:      product * /
60:      prefix - !
70:      call () , index [] , member .

For a left-associative operator, parse its right operand with a threshold that prevents another operator of the same strength from entering the right subtree. For a - b - c, that yields (a - b) - c. For a right-associative operator such as ** or assignment, let equal precedence enter the right operand, yielding a ** (b ** c) or a = (b = c).

One common formulation uses a pair:

left-associative +: leftBP = 40, rightBP = 41
right-associative **: leftBP = 60, rightBP = 60

When parsing the right side, call parseExpression(rightBP). The one-step difference for + prevents another + from becoming part of the right operand; equal powers for ** allow it. The numbers themselves are arbitrary. Their ordering and the equality rule encode language meaning.

Compose Pratt Parsing With the Rest of the Parser

A practical frontend commonly uses recursive descent for the program structure and delegates only expressions:

parseIfStatement() {
  expect(IF, "expected 'if'");
  const condition = parseExpression();
  const thenBranch = parseBlock();
  const elseBranch = match(ELSE) ? parseBlock() : null;
  return IfStmt(condition, thenBranch, elseBranch);
}

Calls and indexing demonstrate why Pratt scales well. After parsing f as an identifier, a following ( with high binding power can parse its arguments and produce Call(f, args). A second ( can then extend that result, allowing f()(x). A following [ can extend the same left expression into an index. This matches how programmers read postfix chains: they bind tighter than binary arithmetic and can repeat.

Error handling remains a design responsibility. When an infix operator lacks a right operand, say “expected expression after *” at the correct source range. Do not report only that the next delimiter is strange. Also decide which tokens terminate an expression in each context; a comma ends an argument expression, but it is not necessarily legal elsewhere.

Trace Binding Power on One Expression

For a + b * c, parsing starts with a. The next operator + is allowed to extend it, so its parselet asks for a right expression at the + threshold. Inside that right parse, * has higher power and therefore captures b and c first. The result is Add(a, Multiply(b, c)), not because of a special case for multiplication, but because the comparison is applied consistently.

Before adding an operator, decide its prefix/infix/postfix role, its left and right binding powers, the AST node it creates, and the tokens that terminate its right operand. A small table and two witness tests are safer than scattered precedence conditions.