Sparkles

Appearance

Operator-Precedence & Pratt Parsing ​

Expression grammars are the one place where the clean rule-↔-function discipline of recursive descent breaks down: 1 + 2 * 3 and 2 ^ 3 ^ 4 cannot be parsed correctly without encoding precedence (which operator binds tighter) and associativity (which way equal-precedence operators group), and the naïve grammar that expresses them — E → E + E | E * E | … — is both ambiguous and left-recursive, the two things an LL parser cannot touch. This family of algorithms solves exactly that sub-problem: a small, table-driven engine that parses operator expressions in linear time and slots into an otherwise recursive-descent parser as its expression engine. It runs from Floyd's 1963 operator-precedence grammars (bottom-up, table-of-relations) through precedence climbing to Pratt's 1973 "Top Down Operator Precedence" (top-down, binding-power driven) — three faces of one idea. This is the operator-expression leaf of the parsing-theory subtree.

At a glance ​

DimensionOperator-precedence / Pratt parsing
Problem solvedParsing operator expressions with precedence + associativity, where a plain CFG is ambiguous and left-recursive
Grammar classOperator grammars (Floyd): no two adjacent nonterminals on any RHS, no ε-productions — a restricted, non-hierarchical subset of CFGs
Two algorithm familiesBottom-up: Floyd operator-precedence (precedence-relation matrix + shift/reduce). Top-down: Pratt / precedence climbing (binding power + one loop)
Core ideaAttach a numeric binding power (precedence) to each operator token; associativity = a deliberate asymmetry between left and right binding power
Lookahead / memory1 token of lookahead; O(d) stack for nesting depth d; no parse table beyond the per-operator precedence map
Time / spaceO(n) time, O(d) space — strictly linear, no backtracking, no memoization
Driving handlers (Pratt)nud (null denotation — atoms, prefix ops) and led (left denotation — infix, postfix ops), keyed per token
AmbiguityResolved by construction: the precedence/associativity table makes every input unambiguous; non-associative operators can be made a parse error
Error detectionImmediate, at the offending token (it's recursive descent); recovery is the host parser's panic-mode
Canonical referencesFloyd 1963; Pratt 1973; Norvell (precedence climbing); Crockford 2007; matklad 2020
Real-world toolsGCC & Clang C/C++ front-ends; V8/JSLint (Crockford); chumsky pratt & pest pratt_parser; Lua, rustc, Go, Zig expression parsers

NOTE

This page is the expression-parsing specialization of top-down parsing. Pratt parsing is recursive descent — it is the technique a hand-written recursive-descent parser reaches for the moment it hits an expression — so read top-down first for the surrounding parser, and bottom-up for the LR machinery that Floyd's operator-precedence method is a degenerate, restricted case of. Every term here (precedence, associativity, handle, shift/reduce) is defined in the parsing concepts glossary.

Overview ​

The expression problem ​

Write the obvious grammar for arithmetic and you get something both ambiguous and left-recursive:

ebnf
E → E "+" E | E "*" E | "(" E ")" | num

For 1 + 2 * 3 this grammar admits two parse trees — (1 + 2) * 3 and 1 + (2 * 3) — and only the second is arithmetically intended. The textbook fix is to stratify the grammar into one nonterminal per precedence level, recursing on the next-tighter level and using the right form of recursion to fix associativity:

ebnf
expr   → term   (("+" | "-") term)*
term   → factor (("*" | "/") factor)*
factor → num | "(" expr ")"

This works — it is unambiguous, non-left-recursive, and LL(1) — but it has two costs that motivate the whole family below. First, the structure no longer reads like the operator table: adding an operator or a precedence level means surgically inserting a new nonterminal and rewriting two existing rules. Second, every expression pays the descent through every precedence level even when no operator at that level is present — factor calls term calls expr for a bare num. Pratt opens his paper by naming this dissatisfaction with grammar-shaped expression parsing directly:

"BNF grammars alone do not deal adequately with either of these issues, and so they are stretched in some directions to increase generality and shrunk in others to improve efficiency." — Pratt, Top Down Operator Precedence, POPL 1973

His thesis is that precedence and associativity are data, not grammar — a number per operator — and that a single loop driven by those numbers replaces the whole stratified grammar.

The core idea: precedence as a number, associativity as an asymmetry ​

Every algorithm in this family rests on one move: assign each operator a numeric precedence (Pratt's binding power), and decide where the next operand belongs by comparing the binding power of the operator on the left against the operator on the right. matklad frames the intuition that makes the whole thing click:

"The key idea is that each operator has a binding power — a number. When you have an ambiguity, the operator with the higher binding power wins." — Kladov, Simple but Powerful Pratt Parsing

The subtle, beautiful part is associativity. To make + left-associative (a + b + c ⇒ (a + b) + c) you do not need a second mechanism — you give + a binding power that is slightly asymmetric, a hair stronger on the right than on the left, so when the parser reaches the second + the already-built left side wins:

text
expr:    a       +       b       +       c
power:       1       2       1       2       1

matklad visualizes exactly this — the right binding power is "pumped" up so the left + holds its right operand tighter than the next + can pull it away. Right associativity (a ^ b ^ c ⇒ a ^ (b ^ c), assignment a = b = c) is the mirror asymmetry: bind tighter on the left. That single trick — encode associativity as the direction of the precedence asymmetry — is what lets one loop handle both directions, and it is the unifying observation behind Pratt, precedence climbing, and the shunting yard alike.

Three faces of one idea ​

The family has three historically distinct presentations that turn out to be the same algorithm seen from different sides:

PresentationDirectionMechanismOrigin
Operator-precedence parsingBottom-upprecedence-relation matrix (⋖ ≐ ⋗) + shift/reduce on a stackFloyd 1963
Precedence climbingTop-downrecursive Exp(p) with a minimum-precedence argumentClarke 1986 / Norvell
Pratt / Top-Down Operator PrecedenceTop-downnud/led per token + an expression(rbp) loop driven by binding powerPratt 1973

Precedence climbing and Pratt parsing are literally the same algorithm (see below); Floyd's bottom-up method is their stack-based dual, restricted to operator grammars. The rest of this page works through each in turn, then shows the equivalence and where each shows up in practice.

How it works ​

Floyd 1963: operator-precedence grammars and the precedence matrix ​

Floyd's 1963 paper introduced operator grammars and the precedence-relation method that the whole family descends from. An operator grammar is a CFG with two restrictions (Floyd 1963):

  1. no ε-productions, and
  2. no two adjacent nonterminals on any right-hand side.

Arithmetic-expression grammars satisfy both: between any two operands there is always an operator terminal, so terminals are never "hidden" behind a nonterminal boundary. That property is what lets Floyd define precedence between terminals and parse by looking only at the terminal pair straddling the parser's current position.

Floyd defined three precedence relations between terminal symbols — note these are relations between operators, not numbers, and need not be symmetric:

RelationRead asMeaning for the handle
a ⋖ ba yields precedence to bthe right end of a handle has not been reached — keep shifting
a ≐ ba and b have equal precedencea and b belong to the same handle (e.g. ( ≐ ))
a ⋗ ba takes precedence over bthe left operator's handle is complete — reduce

These are tabulated in a precedence-relation matrix — one cell per ordered pair of terminals. Parsing is then a stack-based shift/reduce loop driven entirely by the matrix: between the terminal on top of the stack and the incoming terminal, look up the relation, then

  • on ⋖ or ≐ → shift (the handle continues), and
  • on ⋗ → reduce (the most recent handle, bracketed by a ⋖ … ⋗ pair, is reduced).

A ⋖ … ⋗ window in the relation stream brackets exactly one handle — the substring to reduce — so a higher-precedence operator like * sitting between two lower + operators is recognized as + ⋖ * ⋗ + and reduced first. The relations are precomputed from the operator precedences, so the inner loop is a single table lookup: the parse is O(n). This is the bottom-up specialization of LR parsing, and it is the engine that compiler-generated parsers embed to accelerate expressions (see Where it shows up).

NOTE

The relation symbols ⋖ ≐ ⋗ look like < = > but are not an ordering on numbers — a ⋖ b and b ⋖ a can both hold or both fail. They encode the handle-boundary decision, not arithmetic comparison. The numeric binding-power view (precedence climbing / Pratt) is the function representation that makes the common case — operators that do totally order by precedence — trivial to specify; the matrix is the more general but more laborious representation.

Floyd's method has a sharp limit that the top-down reformulations inherit and the matrix shows starkly: a terminal that is both unary and binary — the classic example is -, prefix negation vs. infix subtraction — wants two different precedences in the same matrix cell, which a single-relation table cannot express. Floyd 1963 already flagged this — the unary and binary signs satisfy different precedence relations:

"The difference between the precedence relations of the unary and binary plus and minus signs occurs because the unary signs are introduced in the definition of factor, rather than in that of simple arithmetic expression." — Floyd 1963

The top-down formulations dodge this cleanly by keying on position — a - seen with no expression to its left is prefix (a nud), with an expression to its left is infix (a led) — which is the next refinement.

Precedence climbing: the recursive minimum-precedence loop ​

Precedence climbing (the name is Norvell's, crediting Clarke's 1986 The Top-Down Parsing of Expressions) folds the entire stratified grammar into a single recursive function parameterized by a minimum precedence p. Norvell's canonical pseudocode is worth reproducing exactly, because every later Pratt presentation is a renaming of it:

text
Exp( p ) is
    var t : Tree
    t := P
    while next is a binary operator and prec(binary(next)) >= p
       const op := binary(next)
       consume
       const q := case associativity(op)
                  of Right: prec( op )
                     Left:  1 + prec( op )
       const t1 := Exp( q )
       t := mkNode( op, t, t1 )
    return t

P is
    if next is a unary operator
         const op := unary(next); consume
         const t := Exp( prec(op) ); return mkNode( op, t )
    else if next = "("
         consume; const t := Exp( 0 ); expect ")"; return t
    else if next is a value v
         consume; return mkLeaf( v )
    else error

Read the loop carefully — it is the whole algorithm:

  • Exp(p) parses a maximal expression whose operators all have precedence ≥ p; it returns the moment it sees a weaker operator, handing control back to the caller that owns that weaker level.
  • P (the atom parser) handles the leaf cases: a primary value, a parenthesized sub-expression (Exp(0) — re-enter at the lowest precedence inside brackets), or a prefix unary operator.
  • The recursive call's argument q encodes associativity, and this is the entire subtlety. For a left-associative operator, q = 1 + prec(op): the recursive call refuses any operator of equal precedence, so equal-precedence operators are not consumed by the recursion and instead fold left in the loop. For a right-associative operator, q = prec(op): the recursive call accepts equal precedence, so the chain builds rightward. Norvell states the rule plainly:

"if the binary operator is left associative, q = the precedence of the operator + 1, [and] if the binary operator is right associative, q = the precedence of the operator." — Norvell, Parsing Expressions by Recursive Descent

Eli Bendersky's equivalent presentation names the same quantity next_min_prec and tabulates the operators in an OPINFO map of (precedence, associativity) — e.g. '+': (1, LEFT), '^': (3, RIGHT) — confirming that the only per-operator data the algorithm needs is one integer and one bit.

Pratt 1973: nud, led, and binding power ​

Pratt's 1973 paper generalizes precedence climbing by making the token itself responsible for parsing, via two methods. Pratt's own definitions:

"We will call the code denoted by a token with (without) a preceding expression its left (null) denotation or led (nud)." — Pratt, POPL 1973

  • A nud (null denotation) is invoked when a token appears with no expression to its left — i.e. it starts an expression. Atoms (literals, identifiers), parenthesized groups, and prefix operators have a nud.
  • A led (left denotation) is invoked when a token appears with an expression to its left — i.e. it continues one. Infix and postfix/suffix operators have a led.

Crockford crystallizes the distinction:

"A nud does not care about the tokens to the left. A led does. A nud method is used by values (such as variables and literals) and by prefix operators. A led method is used by infix operators and suffix operators." — Crockford, Top Down Operator Precedence

Each token also carries a left binding power lbp (how strongly it pulls on the expression to its left). The engine is one function, expression(rbp), that takes a right binding power controlling how greedily it consumes to its right. Crockford's JavaScript implementation is the canonical 11-line form:

javascript
var expression = function (rbp) {
  var left;
  var t = token;
  advance();
  left = t.nud(); // parse the start of the expression
  while (rbp < token.lbp) {
    // while the next op binds tighter than our caller's...
    t = token;
    advance();
    left = t.led(left); // ...let it consume `left` as its left operand
  }
  return left;
};

The loop condition rbp < token.lbp is the binding-power comparison from the core idea: keep extending left as long as the upcoming operator binds tighter than what the caller demanded; stop the moment it binds looser and return, letting an outer call take over. Pratt frames the stop condition identically in the paper — "to return to q0 we require rbp < lbp" (Pratt 1973).

Associativity falls out of how each operator's led re-invokes expression:

Operator kindled recurses withEffect
Left-associative +expression(bp)next equal-precedence op stops the recursion → folds left
Right-associative ^, =expression(bp - 1)next equal-precedence op continues the recursion → folds right

Crockford states the rule directly: "we can also make right associative operators … by reducing the right binding power" — i.e. infixr calls expression(bp - 1) where infix calls expression(bp). This is exactly Norvell's q = prec(op) vs. q = 1 + prec(op), written from the other side of the comparison.

Pratt's structural innovation over precedence climbing is the per-token dispatch table: rather than a fixed unary / binary / atom case analysis in one P/Exp function, every token type owns its nud and led, so the parser is extensible — new syntax is a new token object, not an edit to the core loop. Bob Nystrom reifies this as the parselet abstraction (PrefixParselet ≈ nud, InfixParselet ≈ led) and notes the practical payoff of separate tables:

"Having separate tables for prefix and infix expressions is important because we sometimes have both a prefix and infix parselet for the same TokenType." — Nystrom, Pratt Parsers: Expression Parsing Made Easy

That separation is precisely what makes the unary/binary - that defeated Floyd's matrix trivial: the same - token registers a prefix nud and an infix led, and which fires is decided by whether expression is at the start of a sub-expression or in its loop — i.e. by position, for free.

Prefix, infix, postfix, and mixfix in one loop ​

The single nud/led loop handles the full operator zoo without special cases. matklad's Rust reference threads all four through expr_bp(lexer, min_bp) (his min_bp is Pratt's rbp, Norvell's p):

rust
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),                 // nud: atom
        Token::Op('(') => {                             // nud: parenthesized (mixfix)
            let lhs = expr_bp(lexer, 0);
            assert_eq!(lexer.next(), Token::Op(')'));
            lhs
        }
        Token::Op(op) => {                              // nud: prefix operator
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {  // led: postfix / index
            if l_bp < min_bp { break; }
            lexer.next();
            lhs = /* … e.g. `a!`, or `a[i]` with a closing `]` (mixfix) … */ lhs;
            continue;
        }
        if let Some((l_bp, r_bp)) = infix_binding_power(op) {  // led: infix
            if l_bp < min_bp { break; }
            lexer.next();
            let rhs = expr_bp(lexer, r_bp);
            lhs = S::Cons(op, vec![lhs, rhs]);
            continue;
        }
        break;
    }
    lhs
}

The encoding of each operator class as a binding-power shape is the elegant core:

Operator classBinding power shapeWhy
Atomnud, no bpself-delimiting; nothing binds
Prefix -x((), r_bp) — right onlybinds nothing on the left; greedily takes a right operand at r_bp
Infix a + b(l_bp, r_bp) — bothl_bp decides whether the caller keeps it; r_bp's asymmetry sets assoc.
Postfix a!(l_bp, ()) — left onlybinds its left operand; consumes no right operand, so the loop just continues
Mixfix a ? b : c, a[i], ( e )led/nud with an inner expression(0) to a closing tokenthe inner call resets to the lowest precedence inside the brackets

matklad handles the C ternary ?: as an infix operator whose led parses a middle expression at precedence 0 up to the : then a right operand at r_bp — a mixfix operator expressed entirely as one led with two recursive calls, no grammar edit. The same shape gives function calls (a(args)), array indexing (a[i]), and parenthesized grouping. This is the headline result: prefix, infix, postfix, and bracketed mixfix syntax, with arbitrary precedence and either associativity, all fall out of a single loop comparing one integer.

Power & limits ​

What it handles. Any operator grammar in Floyd's sense — expressions built from prefix/infix/postfix/mixfix operators over self-delimiting atoms, where every operand pair is separated by an operator terminal. That is precisely the expression sub-language of essentially every programming language, which is why the technique is ubiquitous inside otherwise-recursive-descent parsers.

What it cannot handle. Operator grammars are a restricted, non-hierarchical subset of context-free grammars — they are not a level in the Chomsky hierarchy, but a side-condition (no adjacent nonterminals, no ε). The technique parses expressions, not whole languages: statement structure, declarations, and block nesting are the job of the surrounding recursive-descent parser, which calls the Pratt loop wherever an expression is expected. Two adjacent operands with no operator between them (e.g. ML/Haskell juxtaposition application f x y) violate the operator-grammar condition; a Pratt parser handles it only by treating juxtaposition as an invisible infix operator with its own binding power — a known idiom, but it shows the boundary. Genuinely context-dependent or ambiguous non-expression structure is out of scope by construction.

Where it sits. Within the parsing hierarchy: Floyd operator-precedence is a strict, restricted case of LR/bottom-up parsing (linear, but for a far smaller grammar class than LALR); Pratt / precedence climbing is the top-down dual and a specialization of recursive descent for expressions. All three are O(n) and use bounded lookahead, sitting below the general parsers (Earley, GLR, GLL) in power and far below them in cost — exactly the trade a production compiler wants for the hot path of expression parsing.

Ambiguity handling ​

The defining feature of this family is that ambiguity is resolved by construction, not discovered at parse time. The ambiguous grammar E → E + E | E * E is never built; instead the precedence/associativity table assigns each (operator, operator) decision a single outcome, so for any input there is exactly one parse the engine can produce. There is no ambiguity report, no conflict, no GLR-style forest — the table is the disambiguation. Three knobs cover the cases real languages need:

  • Precedence (binding power) disambiguates different operators: * > + makes 1 + 2 * 3 parse as 1 + (2 * 3).
  • Associativity (the binding-power asymmetry) disambiguates repeated operators of equal precedence: left for -, right for ^/=.
  • Non-associativity rejects chaining outright. chumsky's none(prec) associativity does exactly this — "a < b < c will produce an error" — turning an ambiguous-or-meaningless chain into a clean parse error rather than an arbitrary grouping.

The cost of this convenience is that the disambiguation is global and implicit: the grouping of an expression is not visible in any grammar rule but distributed across the binding-power table, which is why every serious treatment (Pratt, Norvell, matklad) leads with the table.

Error detection & recovery ​

Because a Pratt parser is recursive descent, error detection is immediate and precise: an unexpected token surfaces exactly where the nud/led dispatch fails (no handler registered for this token in this position) or where a mixfix close-token is missing — matklad's reference simply assert_eq!(lexer.next(), Token::Op(')')), and a real parser raises a diagnostic at that token's source span. There is no deferred failure, no backtracking to unwind, and the offending token is named directly. This is a direct inheritance from top-down parsing: a stack trace through the parser is a partial parse tree, so the position of the error is the position in the input.

Recovery, by contrast, is not part of the algorithm — it belongs to the host recursive-descent parser. The standard technique is the same panic-mode synchronization used in LL parsers (Dragon Book §4.4): on an expression error, discard tokens until a synchronizing token (;, ), a statement keyword) and resume. The Pratt loop's binding-power discipline actually helps here — it returns cleanly to a known precedence level on any token it does not recognize as a continuation, so the host parser regains control at a well-defined point rather than mid-handle.

Performance & complexity ​

The algorithm is strictly linear: each token is consumed exactly once (the advance() / lexer.next() calls march monotonically forward), the inner decision is a single comparison against a per-operator binding power (an array or hash lookup, O(1)), and the recursion depth is bounded by the expression nesting depth d, not the input length. Hence:

  • Time: O(n) for input length n — no backtracking, no memoization (unlike packrat/PEG's O(n)-with-a-large-constant memo table), no chart (unlike Earley/GLL's O(n³)/O(n) chart).
  • Space: O(d) for the recursion/operand stack, O(1) per-operator table — the smallest memory footprint of any parsing family in this catalog. No parse table is generated; the "table" is the hand-written binding-power map.

This combination — linear time, minimal space, immediate errors, and trivial implementation — is why it is the universal choice for the expression hot path even in parsers that are otherwise grammar-generated.

Where it shows up in practice ​

Operator-precedence and Pratt parsing are everywhere expressions are parsed by hand or on a hot path:

  • GCC and Clang parse C/C++ with hand-written recursive descent but accelerate expressions with an embedded operator-precedence/precedence-climbing routine. Wikipedia's operator-precedence article records it: "GCC's C and C++ parsers, which are hand-coded recursive descent parsers, are both sped up by an operator-precedence parser that can quickly examine arithmetic expressions" — and Clang's ParseExpression is a textbook precedence-climbing loop (Bendersky).

  • Compiler-compiler output embeds it too: "Operator-precedence parsers are also embedded within compiler-compiler-generated parsers to noticeably speed up the recursive descent approach to expression parsing" (Wikipedia).

  • JavaScript tooling: Crockford built the JSLint/JSHint parser (and influenced V8's early parser) directly on Pratt's technique — his 2007 essay is the most-cited modern exposition.

  • Parser-combinator libraries expose Pratt as a first-class helper — the strongest cross-link from this page. chumsky's pratt module lets you write an expression parser declaratively from infix/prefix/postfix builders with left/right/none associativity (see the chumsky deep-dive):

    rust
    let expr = atom.pratt((
    postfix(4, op('!'), |lhs, _, _| Expr::Factorial(Box::new(lhs))),
    infix(right(3), op('^'), |l, _, r, _| Expr::Pow(Box::new(l), Box::new(r))),
    prefix(2, op('-'), |_, rhs, _| Expr::Neg(Box::new(rhs))),
    infix(left(1), op('+'), |l, _, r, _| Expr::Add(Box::new(l), Box::new(r))),
    infix(left(1), op('-'), |l, _, r, _| Expr::Sub(Box::new(l), Box::new(r))),
));

    chumsky's own docs name the lineage precisely: "Unlike precedence climbing, which defines operator precedence by structurally composing parsers of decreasing precedence, Pratt parsing defines precedence through a numerical 'binding power'" — and "Higher numbers should be used for higher precedence operators" (chumsky::pratt). pest ships an analogous pratt_parser module for post-processing a flat operator sequence into a tree.

  • Production language front-ends: Lua (subexpr with a priority table), rustc (parser::expr with binding-power-style precedence), Go, and Zig all use a precedence-climbing/Pratt loop for expressions inside hand-written recursive descent.

The recurring pattern is the same: a recursive-descent parser owns statement and declaration structure, and delegates the expression to a Pratt / precedence-climbing loop. That division of labor — top-down for structure, Pratt for expressions — is the single most common architecture for production hand-written parsers, and it is the reference point the cross-family comparison uses when weighing hand-written parsers against the generator-based families.

The equivalence: precedence climbing ⇔ Pratt ​

The two top-down presentations are the same algorithm. Andy Chu (oilshell) made the identification explicit, and Norvell now states it in his own notes:

"It turns out that precedence climbing is a special case of a more flexible technique called Pratt parsing." — Norvell

The dictionary between them is mechanical:

Precedence climbing (Norvell)Pratt / TDOP (Pratt / Crockford)
Exp(p) — parse with min precedence pexpression(rbp) — parse with right binding power rbp
P — the atom / prefix / paren casethe nud dispatch
loop body — consume a binary operatorthe led dispatch
prec(op) >= p — keep goingrbp < token.lbp — keep going
q = 1 + prec(op) (left-assoc)led calls expression(bp)
q = prec(op) (right-assoc)led calls expression(bp - 1)

Precedence climbing is the special case in which every token's role (atom / unary / binary / paren) is decided by a fixed if-cascade inside P/Exp; Pratt generalizes it by moving that decision into a per-token dispatch table (nud/led keyed by token type), which is what buys extensibility and lets a single token (the unary/binary -) carry two roles. The numeric core — "consume operators tighter than the threshold; recurse with prec or prec+1 to set associativity" — is identical. Floyd's bottom-up operator-precedence method is the third face: the same prec(left) vs prec(right) comparison, but resolved on an explicit stack with the ⋖ ≐ ⋗ matrix instead of via the call stack. As matklad shows, you can even mechanically transform the recursive Pratt loop into Dijkstra's iterative shunting-yard, completing the circle: recursion ⇔ explicit stack is the only real difference across the whole family.

Strengths ​

  • Tiny and transparent. The core is ~15 lines (Crockford, matklad); it can be written from memory, audited at a glance, and debugged with an ordinary stack trace. Pratt himself sold it as "very simple to understand, trivial to implement, easy to use, extremely efficient in practice."
  • Linear time, minimal space. O(n) time, O(d) stack, no generated tables, no memoization — the cheapest expression parser in this catalog.
  • Precedence/associativity as data. Adding an operator or precedence level is a new table row, not a grammar rewrite — the stratified-grammar approach demands surgery on multiple nonterminals for the same change.
  • Extensible per token (Pratt's nud/led / Nystrom's parselets). New syntax is a new token handler; the core loop never changes. A single token can be both prefix and infix (the unary/binary -) without conflict.
  • One loop for the whole operator zoo. Prefix, infix, postfix, and bracketed mixfix (ternary, indexing, calls, grouping) all reduce to binding-power shapes over one loop.
  • Composes with recursive descent. It is the expression engine to drop into a hand-written parser — structure handled top-down, expressions handled by Pratt.

Weaknesses ​

  • Expressions only. It parses operator expressions, not whole languages; it must be embedded in a surrounding parser for statements, declarations, and blocks.
  • Implicit, global disambiguation. The grouping of an expression lives in the binding-power table, not in any readable grammar rule — easy to get subtly wrong, and the parser will silently produce a valid but wrong tree rather than report a conflict (unlike an LALR generator, which flags a shift/reduce conflict).
  • No built-in ambiguity detection. A genuinely ambiguous design is not caught; it is silently resolved by whatever the table happens to say.
  • Floyd's matrix is laborious and brittle. The bottom-up relation-matrix form is O(t²) cells in the terminal count and chokes on operators that are both unary and binary — the reason the numeric top-down forms supplanted it for hand-written parsers.
  • Recovery is bolted on. Error detection is immediate, but error recovery is the host parser's panic-mode job; the algorithm itself has none.
  • Juxtaposition / no-operator adjacency is awkward. Languages with operator-free application (f x y) fit only by inventing an invisible infix operator.

Key design decisions and trade-offs ​

DecisionRationaleTrade-off
Precedence as a number (binding power), not grammarAdding/retuning an operator is a one-line table edit; one loop replaces a stratified grammarDisambiguation is implicit and global; the parse tree's shape is not visible in any single rule
Associativity as binding-power asymmetry (+1 / -1)One mechanism (a direction of asymmetry) handles both left and right associativityOff-by-one in the asymmetry silently flips associativity — a classic, hard-to-spot bug
Per-token nud/led dispatch (Pratt) vs. fixed cascade (climbing)Extensible: new syntax = new token handler; one token can be both prefix and infix (-)More machinery than precedence climbing's single if-cascade; the dispatch table is another thing to get right
Top-down recursion (Pratt) vs. bottom-up matrix (Floyd)Recursion reuses the call stack and keys on position, killing the unary/binary-- problemLoses the explicit, inspectable handle stack; bottom-up is what compiler-compilers embed for generated parsers
Embed in recursive descent, not a standalone parserBest-of-both: structure top-down, expressions via Pratt — the dominant production architectureTwo sub-parsers to keep coherent; the boundary (where descent calls expression(0)) must be placed carefully
Resolve ambiguity by table, not detect itZero parse-time ambiguity cost; none-associativity can turn illegal chains into clean errorsA genuinely ambiguous design is silently resolved, never reported — no conflict diagnostic like an LALR tool's

Sources ​