Pratt Parsing: Operator-Precedence Parsing with Binding Power

The problem Pratt parsing solves

Parsing arithmetic like 1 + 2 * 3 - 4 requires respecting precedence (* binds tighter than +) and associativity (- is left-associative, ^ usually right-associative). The textbook recursive-descent answer is to write one function per precedence level — parseExpr → parseTerm → parseFactor → parsePrimary — chained by calls. Every new precedence level adds another mutually recursive function, and prefix (-x), postfix (x!), ternary (a ? b : c), and mixfix (a[b], f(args)) operators each need special-casing.

Pratt's insight was to attach the parsing logic to the tokens rather than to grammar productions. Each token type gets:

• a nud (null denotation): what to do when the token appears with nothing to its left — literals, prefix operators, parentheses;
• a led (left denotation): what to do when it appears with an expression to its left — infix and postfix operators;
• a binding power (a.k.a. left binding power, lbp): how strongly it pulls on the expression to its left.

Precedence becomes data — a number — not control flow. One loop replaces the ladder of functions.

How it works: the binding-power loop

The heart is a single function, conventionally parseExpression(minBp), that takes the minimum binding power it is willing to accept. It first consumes one token as a prefix (its nud), then loops: while the next token's left binding power exceeds minBp, it consumes that operator and lets its led combine the left subtree with a recursively parsed right operand.

fn parseExpr(minBp):
    left = nud(next_token())        # literal or prefix op
    loop:
        op = peek()
        if lbp(op) <= minBp: break
        advance()
        left = led(op, left)         # led recurses with op's rbp
    return left

# For a binary op with precedence p:
#   led(op, left): right = parseExpr(rbp); return (op left right)
#   left-assoc  -> rbp = p        (equal-prec op won't re-enter)
#   right-assoc -> rbp = p - 1    (equal-prec op re-enters)

Associativity falls out of the right binding power. For a left-associative operator, set its right binding power equal to its precedence so that another operator of equal precedence fails the lbp > minBp test and is left for the outer loop. For a right-associative operator (like ^), lower the right binding power by one so the recursion re-enters and nests to the right. Prefix operators simply call parseExpr with their own high binding power in their nud.

Complexity and a worked step trace

Time: every token is consumed exactly once as either a nud or a led, and each does O(1) work plus at most one recursive call, so the whole parse is O(n) in the number of tokens. Space: the only extra memory is the call stack, bounded by the maximum operator-nesting depth d, giving O(d) worst case (O(n) for pathological deeply-nested input like ((((…))))).

Trace 1 + 2 * 3 with binding powers + = 10, * = 20, starting parseExpr(0):

parseExpr(0):
  left = 1                     # nud(1)
  peek '+', lbp 10 > 0  ->  led('+')
     right = parseExpr(10):    # + is left-assoc, rbp = 10
        left = 2
        peek '*', lbp 20 > 10 -> led('*')
           right = parseExpr(20):
              left = 3
              peek EOF, lbp 0 -> stop; return 3
           left = (* 2 3)
        peek EOF -> stop; return (* 2 3)
     left = (+ 1 (* 2 3))
  peek EOF -> stop
result: (+ 1 (* 2 3))

The * node captured the 3 because parseExpr(10) allowed operators with lbp > 10, but the outer parseExpr(0) would not have let a second + steal the 2 — precedence correctly realized as a numeric comparison.

Where it's used in real systems

Pratt parsing is the go-to when you control the grammar and want a hand-written, debuggable, fast expression parser:

• JSLint / JSHint — Douglas Crockford popularized the technique in modern practice; his JavaScript tooling parses expressions with a Pratt core, and his essay "Top Down Operator Precedence" reintroduced it to a generation of engineers.
• The Go compiler — early gc and later hand-written frontends use precedence-based expression parsing closely related to Pratt for the operator grammar.
• IDEs and language servers — JetBrains' plugin framework and many Language Server Protocol implementations favor Pratt-style parsers because error recovery and incremental reparsing are easier in hand-written top-down code.
• Interpreters and DSLs — Crafting Interpreters (Nystrom) builds the Lox expression parser with Pratt; countless calculator, query, and template engines embed one. Databases parsing SQL WHERE expressions and spreadsheet formula engines use the same pattern.

Its appeal in production is pragmatic: adding a new operator is a one-line handler registration, and because the parser is ordinary code you can breakpoint it, emit precise diagnostics, and recover from syntax errors far more gracefully than a generated LR table permits.

Comparison to alternatives and the tradeoff

Pratt parsing occupies a sweet spot between hand-written recursive descent and table-driven generators. Precedence climbing (Clarke, Richards) is essentially the binary-operator subset of Pratt: the minBp argument is the same idea, and for pure infix grammars the two are equivalent — precedence climbing is arguably even more compact but doesn't cleanly generalize to prefix/postfix/mixfix the way nud/led do.

Shunting-yard (Dijkstra, 1961) achieves the same O(n) result iteratively with two explicit stacks, avoiding recursion, but it is awkward for unary and mixfix operators and produces RPN/postfix rather than a tree directly. LR parsers (yacc/bison) handle vastly larger grammar classes and resolve precedence via declarations, but shift/reduce conflicts are opaque and error recovery is notoriously hard to customize.

The core tradeoff: Pratt trades the formal grammar guarantees of a generator for readability, extensibility, and control. You get O(n) parsing and effortless operator addition, but you must reason about binding powers by hand and you don't get an automated proof that your grammar is unambiguous.

Pitfalls, failure modes, and significance

Common ways Pratt parsers go wrong:

• Off-by-one associativity bugs — forgetting to subtract 1 from the right binding power of a right-associative operator (or accidentally doing so for a left one) silently flips 2^3^2 from 2^(3^2) to (2^3)^2. This passes many tests because both sides look plausible.
• Binding-power collisions — two unrelated operators sharing a level can produce surprising parses; keeping a single ordered enum of precedences prevents drift.
• Unary vs. binary minus — - needs both a nud (prefix negation, high bp) and a led (subtraction, lower bp); conflating them mis-parses a - -b.
• Deep recursion / stack overflow — adversarial input with thousands of nested parentheses or unary operators can blow the native stack; production parsers add a depth limit.

Its significance is durability: a 1973 algorithm still ships in modern compilers, linters, and IDEs precisely because it hits the practical trifecta of linear time, tiny code, and painless extension. Pratt himself remarked that operator precedence deserved to be understood as data about tokens rather than a special grammar theory — a perspective that quietly underlies how most real expression parsers are written today.

Pratt parsing vs. common expression-parsing alternatives

Technique	Time	How precedence is expressed	Extensibility / notes
Pratt / TDOP	O(n)	Numeric binding power per token (nud/led)	Add an operator = add a handler; runtime-extensible
Recursive descent (per-level)	O(n)	One grammar function per precedence level	N levels = N mutually recursive functions; verbose
Precedence climbing	O(n)	min-precedence argument threaded through recursion	Essentially Pratt for binary operators; very compact
Shunting-yard (Dijkstra)	O(n)	Explicit operator + output stacks	Iterative, no recursion; awkward for prefix/mixfix
LR / yacc / bison	O(n)	Precedence declarations resolve shift/reduce	Table-driven, powerful, but opaque conflicts
Packrat (PEG)	O(n) w/ memo	Ordered choice, no left recursion natively	O(n) memory; precedence must be encoded by hand