Parsingimplementation

Pratt Parsing

Replace the tower of precedence functions with one loop and a table of binding powers. Prefix handlers, infix handlers, and a single comparison that decides whether to keep going — this is the parsing technique most worth actually knowing.

The question

How do I parse expressions with fifteen precedence levels without writing fifteen functions?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The grammar is no longer transliterated into control flow; it is *data*. Each token kind carries up to three facts: what it means in prefix position (a null denotation, nud), what it means when it follows an expression (a left denotation, led), and a pair of binding powers saying how tightly it grips the operand on each side. The parser is one function over that table, and its state is a token position plus a single integer — the minimum binding power it is currently willing to accept.

What this phase may assume or do

The loop is only correct if the binding powers are a total order consistent with the language's precedence table, and if left-associative operators have right = left + 1 while right-associative operators have right = left - 1. Under those conditions the parser produces exactly the tree the precedence-stratified grammar would have produced. Break the asymmetry — give both sides the same power — and the parser still terminates and still produces a tree, but associativity becomes whichever the loop condition happens to yield, with no diagnostic anywhere.

Key points

  • Precedence becomes data: a table of binding powers, not a tower of functions.
  • Every token has up to two denotations — what it means in prefix position (nud) and what it means after an expression (led) — which is how one - token serves as both negation and subtraction.
  • Two binding powers per infix operator encode precedence and associativity together: left-associative is right = left + 1, right-associative is right = left - 1.
  • The whole algorithm is one loop whose exit condition is bp.left < minBp, and one recursive call parseExpr(bp.right).
  • Adding an operator is a table row; adding a precedence level between two existing ones is why implementations space the numbers out.
  • Stack depth follows expression nesting, not the number of precedence levels — the fifteen frames of a stratified C parser become one.
  • It parses expressions only. Statements and declarations stay recursive descent, and the hybrid is what Clang, rustc and Go all ship.

The problem with one function per level

Recursive descent handles precedence by stratifying the grammar: expression calls term calls factor, and the nesting depth is the precedence. It works, and it does not scale. C has roughly fifteen precedence levels. Fifteen near-identical functions, fifteen stack frames to reach a bare identifier, and every change to the precedence table is an edit across several of them.

Worse, the functions are not merely repetitive, they are *identical up to a set of operator kinds*. parseTerm and parseExpression in [[recursive-descent]] differ in exactly two places: which operators they match, and which function they call for their operands. Any time code differs only in data, the data should be data.

Vaughan Pratt made that observation in 1973 and produced the algorithm below. It goes by two names for two nearly-identical formulations: Pratt parsing when the per-token behaviour is dispatched through handler functions, and precedence climbing when it is a single function with a precedence table. The core loop is the same, and it is about fifteen lines.

Binding power

simplifiedThe absolute numbers are arbitrary and only their order matters; real implementations space them out (rustc and many others use multiples of ten or a named enum) so that a new operator can be inserted between two existing ones without renumbering. The gaps also matter for the prefix powers: a prefix operator needs a power above every infix operator whose operand it should capture, and getting that wrong is how -a.b parses as (-a).b in a language that meant -(a.b).

The central idea is to stop thinking about precedence as levels and start thinking about it as *grip*. Every infix operator grips the expression to its left with some strength and the expression to its right with some other strength. In 1 + 2 * 3, the * grips 2 more strongly than the + does, so 2 goes to the *.

Two binding powers per operator rather than one is what makes associativity fall out for free. For a left-associative operator give the right side slightly *more* power than the left: parsing 1 - 2 - 3, after building 1 - 2 the loop sees - with left power 10 and is currently demanding at least 11, so it stops, returns (1 - 2), and the outer loop folds it in — left association. For a right-associative operator like ^, give the right side slightly *less*: parsing 2 ^ 3 ^ 2, the inner call demands only 29 while ^ offers 30, so it keeps going and builds 3 ^ 2 first — right association.

That is the entire trick. One integer comparison expresses precedence and associativity together, and adding an operator to the language becomes adding a row to a table rather than a function to a call chain.

A binding-power table for a small expression language
TokenPrefix (nud)Left BPRight BPReading
=—21Right-associative: a = b = c is a = (b = c). Right BP is lower.
? :—43Ternary, right-associative; the : arm is parsed at the lower power.
||—67Left-associative: right BP is higher by one.
&&—89Binds tighter than ||, so both powers are higher.
== !=—1011Left-associative.
< > <= >=—1213Left-associative.
+ -- prefix: 901415One token, two roles. Prefix minus binds tighter than every infix operator.
* / %—1617The classic level above +.
^—2019Right-associative: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2) = 512, not 64. Right BP is *lower*.
!prefix: 90——Prefix only; there is no left denotation, so it can never follow an expression.
( )group: restart at 0100—As a prefix it groups; as an infix it is a call, and calls bind tighter than any operator.
. [—100101Member access and indexing, left-associative, at the top.

The loop

Here is the whole algorithm. parseExpr(minBp) parses one prefix form, then loops for as long as the next token is an infix operator whose *left* binding power is at least minBp, recursing at that operator's *right* binding power to collect its right operand.

Read the two lines that carry it. if (bp.left < minBp) break is the entire precedence and associativity mechanism. parseExpr(bp.right) is the recursion, and the argument it is given is what decides how much the right operand is allowed to swallow.

Pratt parsing in full — the loop, the table, and the two handler kinds
1type Bp = { left: number; right: number }
2 
3const INFIX: Record<string, Bp> = {
4  '=':  { left: 2,  right: 1  },   // right-assoc: right < left
5  '||': { left: 6,  right: 7  },   // left-assoc:  right = left + 1
6  '&&': { left: 8,  right: 9  },
7  '==': { left: 10, right: 11 }, '!=': { left: 10, right: 11 },
8  '<':  { left: 12, right: 13 }, '>':  { left: 12, right: 13 },
9  '+':  { left: 14, right: 15 }, '-':  { left: 14, right: 15 },
10  '*':  { left: 16, right: 17 }, '/':  { left: 16, right: 17 },
11  '^':  { left: 20, right: 19 },   // right-assoc: 2^3^2 === 2^(3^2)
12  '.':  { left: 100, right: 101 },
13}
14 
15const PREFIX_BP = 90
16 
17/** Null denotation: what a token means with no expression to its left. */
18function nud(p: Parser, tok: Token): Ast {
19  switch (tok.kind) {
20    case 'NUMBER': return { kind: 'Number', value: Number(tok.text), span: tok.span }
21    case 'IDENT':  return { kind: 'Name', text: tok.text, span: tok.span }
22 
23    case 'MINUS':
24    case 'BANG': {
25      const operand = parseExpr(p, PREFIX_BP)     // prefix ops grip tightly
26      return { kind: 'Unary', op: tok.text, operand, span: join(tok.span, operand.span) }
27    }
28 
29    case 'LPAREN': {
30      const inner = parseExpr(p, 0)               // inside parens, start from scratch
31      const close = p.expect('RPAREN', 'to close the grouped expression')
32      return { ...inner, span: join(tok.span, close.span) }
33    }
34 
35    default:
36      throw new ParseError(
37        `Expected an expression. Found '${tok.text}' instead.`, tok.span)
38  }
39}
40 
41/** Left denotation: what a token means when an expression is already to its left. */
42function led(p: Parser, left: Ast, tok: Token, rightBp: number): Ast {
43  if (tok.kind === 'LPAREN') {                    // '(' as infix is a CALL
44    const args = parseArgs(p)
45    const close = p.expect('RPAREN', 'after the argument list')
46    return { kind: 'Call', callee: left, args, span: join(left.span, close.span) }
47  }
48  const right = parseExpr(p, rightBp)             // ← the whole recursion
49  return { kind: 'Binary', op: tok.text, opSpan: tok.span, left, right,
50           span: join(left.span, right.span) }
51}
52 
53/** Parse an expression that binds at least as tightly as `minBp`. */
54function parseExpr(p: Parser, minBp: number): Ast {
55  let left = nud(p, p.next())
56 
57  for (;;) {
58    const op = p.peek()
59    const bp = INFIX[op.text]
60    if (!bp) break                 // not an infix operator: the expression ends here
61    if (bp.left < minBp) break     // ← precedence AND associativity, in one comparison
62 
63    p.next()                       // consume the operator
64    left = led(p, left, op, bp.right)
65  }
66 
67  return left
68}
69 
70// Entry point: parse a whole expression, accepting operators of any strength.
71const ast = parseExpr(p, 0)

Note that MINUS appears in both nud and INFIX. That is the feature, not an accident: a token's meaning depends on whether something is already to its left, and separating the two denotations is exactly what lets one token be both unary and binary without a lookahead hack. The same mechanism makes ( both grouping and call, and [ both a list literal and an index.

Tracing it

Run 1 + 2 * 3 through the loop with minBp = 0. The trace below is the whole behaviour: two entries to parseExpr and one comparison that goes each way.

Then compare the last two rows against 2 ^ 3 ^ 2. Identical code, identical loop, opposite grouping — because for ^ the right binding power is one *below* the left, so the inner call is still willing to accept another ^ where the * version was not.

parseExpr on 1 + 2 * 3 (left-assoc +) and on 2 ^ 3 ^ 2 (right-assoc ^)
StepCallSeesComparisonAction
1parseExpr(0)NUMBER 1—nud → Number(1); left = 1
2parseExpr(0)+ (14,15)14 >= 0consume; call led → parseExpr(15)
3parseExpr(15)NUMBER 2—nud → Number(2); left = 2
4parseExpr(15)* (16,17)16 >= 15 ✓consume; call led → parseExpr(17)
5parseExpr(17)NUMBER 3EOF nextreturns 3
6parseExpr(15)EOF—returns (2 * 3) to the outer led
7parseExpr(0)EOF—returns 1 + (2 * 3) ✓
————Now the right-associative case:
8parseExpr(0)2, then ^ (20,19)20 >= 0consume; call led → parseExpr(19)
9parseExpr(19)3, then ^ (20,19)20 >= 19 ✓does NOT stop — consumes the second ^
10parseExpr(19)2—builds (3 ^ 2), returns it
11parseExpr(0)EOF—returns 2 ^ (3 ^ 2) = 512 ✓

What it costs

implementationThe hybrid is what production frontends actually do. Clang's ParseRHSOfBinaryExpression is precedence climbing over a getBinOpPrecedence table while statements are hand-written descent; rustc's parse_expr_res climbs an AssocOp precedence table; Go's parser loops over prec levels in binaryExpr. The formulations differ in detail — Clang and rustc keep a single precedence per operator plus an associativity flag rather than two binding powers — but they compute the same tree. Two binding powers is the presentation that makes associativity fall out of one comparison; a precedence-plus-flag formulation needs a second condition in the loop.

The gains are real: adding an operator is a table row, the stack depth is proportional to the *nesting* of the expression rather than the number of precedence levels, and one function handles the whole expression grammar. The costs are equally real and worth naming.

First, the grammar is no longer visible. A stratified recursive-descent parser can be read against the language specification line by line; a Pratt table cannot, and a wrong number in it produces silently wrong trees. Second, the failure mode is uniquely nasty: precedence bugs never produce a diagnostic. a & b == c in C parses as a & (b == c) because of a precedence choice made in 1972, compiles cleanly, and returns the wrong answer — that is a language-design consequence of a precedence table, and the same class of bug in your own table looks identical. Third, diagnostics need work: the default failure in nud is "expected an expression", which is honest but unhelpful, and improving it means writing per-token messages that a stratified parser got from its structure.

It is also, strictly, only an expression parser. Statements, declarations and type syntax are not operator-shaped and gain nothing from a binding-power table. Which is why the real design is a hybrid — recursive descent for the constructs that differ from one another, Pratt for the ones that do not.

How it works

The steps, in the order the compiler takes them.

  • Build a table mapping each token kind to its prefix handler, its infix handler, and its left and right binding powers.
  • Call parseExpr(0) — willing to accept an operator of any strength.
  • Consume one token and run its prefix handler to produce the initial left-hand expression; a token with no prefix handler is where "expected an expression" comes from.
  • Look at the next token. If it has no infix entry, the expression is finished.
  • If its left binding power is below the current minimum, stop and return — the operand belongs to an outer call.
  • Otherwise consume the operator and call the infix handler, which recurses into parseExpr with that operator's right binding power to collect the right operand.
  • Fold the result into the accumulated left-hand expression and loop.
  • Prefix handlers recurse at a high fixed power so that a prefix operator captures only a tightly-bound operand; grouping handlers recurse at zero so that parentheses reset the ladder.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • Two operators are given the same binding power by mistake, and expressions mixing them associate by accident of the loop condition. No error is reported; a subset of programs quietly computes the wrong value.
  • A right-associative operator is given right = left + 1 like everything else, so 2 ^ 3 ^ 2 yields 64 instead of 512 and a = b = c assigns in the wrong order.
  • The prefix binding power is set below an infix operator's, so -a * b parses as -(a * b). In a language with operator overloading or saturating arithmetic that is a different answer, not just a different tree.
  • A token has an infix entry but no prefix handler, and an expression beginning with it fails with "expected an expression" pointing at a * — technically correct and useless to the user until per-token messages are added.
  • Assignment is given a left binding power above a comparison, and a == b = c parses without complaint in a language that meant to forbid it.
  • The table and the language reference drift, and the compiler's precedence disagrees with the documentation for one rarely-used operator, which surfaces as a bug report years later.

When it helps

  • Any language with more than about four precedence levels — which is essentially all of them.
  • Languages where operators are added over time, or user-definable: a table row is a cheap extension point where a stratified grammar is not.
  • Tokens with dual roles — unary and binary -, grouping and call (, list and index [ — which the nud/led split handles without lookahead special cases.
  • Anywhere a hand-written frontend wants both good diagnostics and a compact expression parser, which is why the technique dominates production compilers.

When it hurts

  • Non-expression syntax. Statements, declarations, patterns and type syntax are not operator-shaped, and forcing them through a binding-power table produces something harder to read than the descent it replaced.
  • Grammars where an operator's precedence depends on context rather than on the token — some template and macro syntaxes — since the table is keyed on token kind alone and the exception has to be bolted on.
  • Teaching or specification contexts where the grammar must be readable as a grammar. A table of integers is not a document a language committee can review.

What it costs

Every one of these is paid by something.

  • Turning precedence into data buys a one-row cost for every new operator and a shallow stack, and pays with a grammar that is no longer visible in the code — a wrong integer in the table produces a silently wrong tree that no test of "does it parse" will catch.
  • The nud/led split buys dual-role tokens with no lookahead hacks, and pays with two dispatch points per token kind and a default error message ("expected an expression") that is much worse than a stratified parser's until per-token messages are written by hand.
  • One loop instead of fifteen functions buys code size and edit locality, and costs debuggability: a stack trace no longer names the construct being parsed, only parseExpr repeated, so you lose the free structural information recursive descent gave you.
  • Spacing binding powers apart buys room to insert operators later, and costs the property that the numbers mean anything on their own — they are only meaningful relative to each other, so reviewing a table change requires reviewing the whole table.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Stratified recursive descent — one function per precedence level. Slower to change and deeper on the stack, but the grammar is legible in the code and the stack trace names the construct. Still the right choice for a language with three or four levels — see [[recursive-descent]].
  • An operator-precedence parser in the classical bottom-up sense, driven by a precedence relation table between terminals. Historically important and largely superseded; it cannot handle unary and binary uses of the same token cleanly, which is exactly what nud/led solves.
  • [[lr-parsing]] with precedence declarations: Bison's %left, %right and %nonassoc resolve shift/reduce conflicts in an ambiguous E -> E op E grammar, achieving the same result declaratively. The grammar stays readable; the diagnostics get worse.
  • Parser combinators with an explicit precedence-table helper (buildExpressionParser in Parsec and its descendants) express the same idea functionally, at the cost of the library's error-message and backtracking behaviour.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Read Clang's getBinOpPrecedence in clang/lib/Parse/ParseExpr.cpp alongside ParseRHSOfBinaryExpression — it is precedence climbing, about forty lines, and it parses all of C++'s binary operators.
  • rustc: compiler/rustc_ast/src/util/parser.rs defines AssocOp with precedence() and fixity(), consumed by parse_expr_res — the same algorithm with a precedence-plus-associativity formulation.
  • Go: cmd/compile/internal/syntax/parser.go, function binaryExpr, loops from the lowest precedence upward; Go has only five binary precedence levels, which is a deliberate language-design choice worth noticing.
  • Test your own table empirically rather than by reading it: parse a - b - c, a = b = c, 2 ^ 3 ^ 2, -a * b, -a.b and a & b == c, and print the trees. Every one of those distinguishes a correct table from a plausible wrong one.
  • Our stepper at /compilers/parsing shows minBp, the current token and the accumulated left operand at each iteration of the loop.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Pratt parsing and precedence climbing are different algorithms." They are two presentations of the same loop. Pratt dispatches per-token handlers; precedence climbing branches on a precedence table. Both compute the same tree and both stop on the same comparison.
  • "The binding-power numbers mean something." Only their relative order does. Doubling every number changes nothing; changing one by one can change the language.
  • "Left-associative means the right binding power is lower." It is the other way round, and this is the single most common error. Left-associative gives the right side *more* power so the inner call stops early and the outer loop folds left.
  • "Pratt parsing replaces recursive descent." It replaces the expression part of it. Statements and declarations remain descent in every production compiler that uses it.
  • "It is a bottom-up technique because it builds from operands upward." It is top-down: it recurses before it reduces, and the call stack holds pending left operands rather than a table-driven state stack.

Misconceptions

The claim, and what is actually true.

You need one function per precedence level to get precedence right.
You need an ordering. Whether that ordering lives in the call graph or in a table is an implementation choice, and the table version is what production compilers ship.
A parser that produces a tree for every valid input is correct.
Precedence bugs produce a tree for every valid input. Correctness here means producing the tree the language specifies, and only tests over mixed-operator expressions distinguish the two.
Unary minus needs lookahead to distinguish it from subtraction.
It needs to know whether an expression is already to its left, which the parser always knows: prefix position runs nud, infix position runs led. No lookahead is involved.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Give every operator a number saying how tightly it holds on. Parse one operand, then keep grabbing operators as long as their number is at least as big as the one you were told to demand; when you recurse to get the right-hand operand, tell that call to demand the operator's own number. Higher numbers win, so * takes 2 away from + in 1 + 2 * 3. That is the whole algorithm.

practical

Write the table first and space the numbers by ten. Left-associative gets right = left + 1; right-associative gets right = left - 1; memorise that, because getting it backwards is the standard bug and it is silent. Put prefix operators above every infix operator whose operand they should capture, and make grouping recurse at zero. Then test with a - b - c, 2 ^ 3 ^ 2 and -a.b — those three inputs catch associativity, right-associativity and prefix-power errors respectively, and no simpler test catches any of them.

advanced

The formulation generalises past binary operators once you see led as "what this token does with an expression already on its left". A call is ( in infix position. Indexing is [. A ternary is ? in infix position parsing an inner expression at power 0, expecting :, then recursing at its own right power. Postfix is a led that recurses at nothing. Even statement-position constructs can be folded in if you are willing to give statements binding powers, which some languages that treat everything as an expression do. The limit is context: the table is keyed on token kind alone, so a construct whose precedence depends on what came before — a macro that changes an operator's meaning, or a language where < may open a generic argument list — needs state outside the table, and that is where the elegance stops and the hand-written special cases begin.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationClang, rustc and Go's gc all use precedence climbing for binary expressions as of their current frontends, but each uses a precedence-plus-associativity formulation rather than explicit left/right binding powers. The two are interchangeable; the two-power form removes a conditional from the loop, which is why it dominates modern write-ups (notably Matklad's, 2020) even though the older form is what is deployed.
specThat 2 ^ 3 ^ 2 is 512 rather than 64 is a fact about languages whose exponentiation is right-associative — Python's **, Ruby, Haskell, F#, and JavaScript's **. It is not universal: Excel formulas and MATLAB evaluate ^ left-associatively, giving 64. The associativity is a language decision, and the parser only implements it.
simplifiedThe table shown omits postfix operators (x++), mixfix forms (the ? : ternary needs its own led that parses the middle arm at power 0 and then expects :), and the special handling most languages need for assignment targets. Each is a handler, not a change to the loop, but the handler set in a real language is a few dozen entries rather than a dozen.

If you were asked this in an interview

  • Implement parseExpr(minBp) on a whiteboard and then tell me which single character you change to make an operator right-associative.
  • Why does the same - token need two handlers, and what would you have to do without them?
  • Your language gives 2 ^ 3 ^ 2 the answer 64. Where is the bug and what test would have caught it?

Connections

DSArecursionstackhash-table
Domains that do not exist yet
  • Software Design — Replacing branching logic with a table
    Turning the precedence tower into a binding-power table is a general refactoring — behaviour that differs only in data becomes data — and the pattern belongs there. Here it is the difference between fifteen functions and one.