Every compiler, interpreter, configuration-file reader, or query-language engine starts with the same job: turning a flat stream of tokens into a structured tree the rest of the program can walk. That job is parsing, and for hand-written parsers, two techniques dominate: recursive descent, which maps each grammar rule directly onto a function, and Pratt parsing, a specialized technique for expressions that handles operator precedence without a function explosion. Recursive descent is simple and works beautifully for most of a language’s grammar — statements, declarations, blocks — but it gets awkward exactly where arithmetic-style expressions live, because precedence and associativity don’t map cleanly onto “one function per rule.” Pratt parsing exists specifically to fix that. This explainer covers how each technique works, where recursive descent breaks down, and how Pratt parsing’s precedence-driven loop solves the same problem with far less code.
At a Glance
| Recursive descent | One parsing function per grammar rule, calling each other top-down |
| Pratt parsing | One generic expression-parsing loop driven by per-token precedence (binding power) |
| Best suited for | Recursive descent: statements/structure. Pratt: expressions with operators |
| Precedence handling | Recursive descent: a separate function per precedence level. Pratt: a precedence number per operator |
| Adding a new operator | Recursive descent: insert/renumber grammar functions. Pratt: register one new table entry |
| Origin | Pratt parsing comes from Vaughan Pratt’s 1973 paper “Top Down Operator Precedence” |
What Problem This Solves
Parsing takes the token stream produced by a lexer (e.g. NUM(1), OP(+), NUM(2), OP(*), NUM(3) for the text 1 + 2 * 3) and builds an abstract syntax tree that reflects the language’s grammar rules — in particular, which operations bind more tightly than others. A parser that got this wrong would parse 1 + 2 * 3 as (1 + 2) * 3 instead of the mathematically correct 1 + (2 * 3). Both recursive descent and Pratt parsing are top-down parsing strategies — they start from the whole expression and work down into its parts — but they differ sharply in how they encode precedence, which is the crux of the problem this explainer is about.
How Recursive Descent Works
Recursive descent translates a grammar almost mechanically: each production rule becomes a function, and each function calls the functions for the rules it references. A grammar rule like statement -> if_statement | while_statement | expr_statement becomes a parse_statement() function that peeks at the next token and dispatches to parse_if(), parse_while(), or parse_expr_statement(). This is simple to write, simple to debug (a stack trace literally shows you the grammar path taken), and it maps cleanly onto most of a real language’s syntax — declarations, blocks, control flow. It struggles specifically with left-recursive rules (a rule that refers to itself as its own first symbol, which causes infinite recursion in a naive top-down implementation) and, most relevantly here, with operator precedence in expressions.
Why Operator Precedence Breaks Naive Recursive Descent
The standard recursive-descent fix for precedence is to write one function per precedence level, each calling the next tighter-binding level before trying to consume an operator at its own level. For a language with just +, -, *, and /, that’s already parse_additive() calling parse_multiplicative() calling parse_unary() calling parse_primary(). Real languages have far more precedence levels than that — in his widely cited article on the subject, developer Bob Nystrom points out that JavaScript’s expression grammar has roughly seventeen distinct precedence levels. Written the naive recursive-descent way, that means roughly seventeen near-identical functions, each differing only in which operator tokens it checks for and which function it calls next. Associativity (does a - b - c group as (a - b) - c or a - (b - c)?) has to be hand-coded into each of those functions separately, and adding a new operator at a new precedence level means inserting a new function into the chain and renumbering everything below it.
What Pratt Parsing Does Differently
Pratt parsing — sometimes called “top-down operator precedence parsing,” after Vaughan Pratt’s original 1973 title — replaces that chain of functions with a single loop and a table. Every token type that can start an expression (a number, a variable, a unary -, an opening parenthesis) gets a prefix handler. Every token type that can appear after an expression as an operator (+, *, etc.) gets an infix handler and a precedence number, sometimes called its “binding power.” The core function, often called parse_expression(min_precedence), works like this: parse one prefix expression to get a starting value, then repeatedly look at the next operator — as long as its precedence is at least as high as the minimum precedence the caller asked for, consume it, recursively parse its right-hand side (passing in that operator’s own precedence, which is what produces correct left-associativity), and fold the result into the running expression. Precedence is no longer encoded as “which function am I in” — it’s a plain number compared at one single point in the code, so adding a new operator means adding one entry to a table, not a new function in a chain.
Recursive Descent vs Pratt Parsing
| Aspect | Recursive Descent (naive) | Pratt Parsing |
|---|---|---|
| Functions needed for N precedence levels | N separate functions | 1 function + N table entries |
| Adding a new operator | Insert a function, renumber the chain | Register one prefix/infix handler with a precedence number |
| Associativity | Hand-coded per level (loop vs recursion choice) | Controlled by passing precedence vs precedence+1 to the recursive call |
| Readability of the grammar structure | Very explicit — one rule, one function | Less explicit — precedence lives in a table, not the control flow |
| Best fit | Statements, declarations, overall language structure | Expressions with many operators and precedence levels |
Code Example: A Minimal Pratt Parser in Python
The example below parses simple arithmetic with +, -, *, /, and parentheses into a nested tuple AST, using the precedence-climbing form of Pratt parsing (a restricted version that handles binary operators without a full prefix/infix table). Calling parse("1 + 2 * 3") correctly returns ('+', 1, ('*', 2, 3)), and parse("(1 + 2) * 3") returns ('*', ('+', 1, 2), 3) — multiplication binds tighter than addition in the first case, while the parentheses override that in the second.
import re
TOKEN_RE = re.compile(r"\s*(?:(\d+)|(.))")
PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2}
def tokenize(text):
tokens = []
for num, op in TOKEN_RE.findall(text):
if num:
tokens.append(("NUM", int(num)))
elif op:
tokens.append(("OP", op))
return tokens
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
def peek(self):
return self.tokens[self.pos] if self.pos < len(self.tokens) else (None, None)
def advance(self):
tok = self.peek()
self.pos += 1
return tok
def parse_expression(self, min_precedence=0):
kind, value = self.advance()
if kind == "NUM":
left = value
elif kind == "OP" and value == "(":
left = self.parse_expression(0)
self.advance() # consume the matching ")"
else:
raise SyntaxError(f"Unexpected token: {value}")
while True:
kind, op = self.peek()
if kind != "OP" or op not in PRECEDENCE:
break
precedence = PRECEDENCE[op]
if precedence < min_precedence:
break
self.advance() # consume the operator
# precedence + 1 on the right side gives left-associativity
right = self.parse_expression(precedence + 1)
left = (op, left, right)
return left
def parse(text):
return Parser(tokenize(text)).parse_expression()
print(parse("1 + 2 * 3")) # ('+', 1, ('*', 2, 3))
print(parse("(1 + 2) * 3")) # ('*', ('+', 1, 2), 3)Trade-Offs
- Pro (Pratt): Adding an operator or changing precedence is a one-line table edit, not a restructuring of the function chain.
- Pro (Pratt): Naturally handles prefix, infix, postfix, and mixfix operators (like
a ? b : c) within the same uniform mechanism. - Pro (Recursive descent): The control flow directly mirrors the grammar, which makes it easier for newcomers to read and debug, especially outside of pure expression parsing.
- Con (Pratt): Precedence lives in a table rather than in the code’s structure, which can make the grammar less self-documenting to someone unfamiliar with the technique.
- Con (Recursive descent): Scales poorly as the number of precedence levels grows — real language grammars (e.g. JavaScript’s ~17 levels) turn into long chains of near-duplicate functions.
- Shared limitation: Both are typically hand-rolled for expressions; for very large or ambiguous grammars, parser-generator tools (LALR, PEG) may be a better fit than either.
Bottom Line
Recursive descent and Pratt parsing aren’t competitors so much as a division of labor: use recursive descent for the overall shape of a language — statements, declarations, blocks — and drop into a Pratt-style parse_expression(precedence) loop the moment you hit arithmetic-like expressions with multiple operators and precedence levels. Nearly every production hand-written parser for a language with infix operators — including real-world interpreters and compilers — uses exactly this hybrid, because it avoids both recursive descent’s function explosion and the complexity of a full parser-generator toolchain.
FAQ
Is Pratt parsing a replacement for recursive descent?
No — it’s typically combined with it. Recursive descent handles the overall grammar; a Pratt-style loop is dropped in specifically for expression parsing.
What does “binding power” mean?
It’s another name for an operator’s precedence value inside the Pratt algorithm — how strongly it “pulls” neighboring operands into its own sub-expression versus letting an outer operator claim them.
What are “nud” and “led”?
Terms from Vaughan Pratt’s original 1973 paper for a token’s “null denotation” (how it parses with nothing to its left — i.e. a prefix handler) and “left denotation” (how it parses with an already-parsed expression to its left — i.e. an infix handler). Modern explanations, including Bob Nystrom’s, often use the friendlier terms “prefix” and “infix” parselets instead.
Does Pratt parsing handle right-associative operators like exponentiation?
Yes — passing the operator’s own precedence (rather than precedence + 1) to the recursive call on the right-hand side produces right-associativity instead of left.
Why doesn’t the code example handle left recursion directly?
It doesn’t need to — the while loop inside parse_expression handles left-leaning chains of operators (like a - b - c) iteratively, which is precisely how Pratt parsing avoids the infinite-recursion problem that a naive left-recursive grammar rule would cause in straight recursive descent.