Lesson 4.1 — Expression parsing: layered grammars, precedence climbing, Pratt parsing, shunting-yard¶

Techniques: the precedence-layered grammar (ALGOL 60, Naur 1960), precedence climbing (Richards 1979; Clarke 1986), Pratt parsing / top-down operator precedence (Pratt 1973), Dijkstra's shunting-yard (1961) · Pebble implements: Pratt parsing in the parser (exercise E2); all four in the comparison lab (SPEC, L1–L2) · Prerequisites: Lesson 2.1 (layering), Lesson 2.5 (recursive descent) · Time: 4 hours

Statements are easy to parse top-down: a keyword announces each one. Expressions are not: in a - b * c ^ d ^ e - f nothing but a table of precedences and associativities says which operator is the root. Ch 2 wrote that table into the grammar, one nonterminal per level; Ch 3 wrote it into %left/%right declarations that resolve LR conflicts. Hand-written front ends do neither: Clang, GCC, Go, rustc, rust-analyzer, V8 and pebblec parse statements by recursive descent and hand every expression to one small loop driven by the table. This lesson gives the four classic forms of that loop, proves that they build the same tree, and measures what each one costs.

1. Problem and motivation¶

The problem. Input: an operator table $T$ (Definition 4.1.1) and a token string $w$. Output: the abstract syntax tree of $w$ in which every operator's operands are grouped as the table says ($a - b * c$ is $(-\ a\ (*\ b\ c))$, $a - b - c$ is $(-\ (-\ a\ b)\ c)$ for a left-associative -, $d \mathbin{\hat{}} e \mathbin{\hat{}} f$ is $(\hat{}\ d\ (\hat{}\ e\ f))$ for a right-associative ^), or a syntax error. In pebblec this is parseExpression and every expression inside a statement (pebble-spec §4.2: nine binary levels, a non-associative comparison level, prefix - and !, the postfix-like as, and [], .f and calls).

Precedence-layered grammar¶

The ALGOL 60 report [Nau60] defined arithmetic expressions with one nonterminal per level: <simple arithmetic expression>, <term>, <factor>, <primary>. The grammar is the specification, it is unambiguous (Lemma 4.1.4), and every LL or LR tool accepts it once left recursion is written as a loop. The cost is one grammar rule and one parser function per level: C has 17 levels from primary-expression to expression [ALSU07 §4.3], so a recursive-descent parser makes 17 nested calls to reach each identifier. CPython's PEG grammar still spells out its levels this way (sum, term, factor, power in Grammar/python.gram [CPY-Gram]).

Precedence climbing¶

Martin Richards's BCPL compiler parsed expressions with one recursive procedure that takes the minimum precedence it may consume as a parameter; Keith Clarke described the method for recursive-descent parsers in a 1986 report [Cla86], and Theodore Norvell named it precedence climbing in his survey of expression parsing [Nor99]. One function replaces the $k$ level functions: it reads an operand, then keeps absorbing operators whose level is at least the minimum, parsing each right operand with a higher minimum. Clang's Parser::ParseRHSOfBinaryExpression [CLANG-ParseExpr], Go's parseBinaryExpr [GO-ParseBinary], rustc's parse_expr_assoc_with [RUSTC-ParseExpr] and V8's ParseBinaryContinuation [V8-ParserBase] are precedence climbing.

Pratt parsing¶

Vaughan Pratt's top-down operator precedence [Pra73] attaches parsing actions to tokens instead of to grammar rules: each token has a null denotation (nud, what it means at the start of an operand: a literal, a prefix operator, () and a left denotation (led, what it means after an operand: an infix or postfix operator), plus a left binding power. The driver is the same loop as precedence climbing with binding powers instead of levels; its gain is extensibility, since prefix, postfix, mixfix (?:), calls and indexing are all just tokens with a nud or a led. Crockford's JSLint parser popularized it [Cro07] and Aleksey Kladov's formulation with pairs of binding powers [Kla20] is what rust-analyzer uses (expr_bp [RA-Expr]) and what pebblec uses.

Shunting-yard¶

Dijkstra's ALGOL 60 translator for the Electrologica X1 [Dij61] converted infix expressions to reverse Polish notation with two stacks and no recursion, the way a railway shunting yard reorders wagons: operands go straight to the output, operators wait on a stack until an operator of lower precedence (or a closing parenthesis) arrives. It needs no recursion and so no call stack proportional to the nesting depth, which mattered on a machine with 4096 words of memory. GCC's C parser still parses binary operators with an explicit precedence stack (c_parser_binary_expression [GCC-CParser]).

2. Definitions and algorithms¶

Throughout, $w = t_1 \cdots t_n$ is the token string and $t_{n+1} = \$$ the end marker.

Definition 4.1.1 (Operator table)

An operator table $T = (O, \mathrm{lev}, \mathrm{assoc}, \mathrm{Pre})$ consists of a finite set $O$ of infix operator tokens, a level function $\mathrm{lev} : O \to \{1, \dots, k\}$ (level 1 binds loosest), an associativity $\mathrm{assoc} : \{1, \dots, k\} \to \{\mathsf{left}, \mathsf{right}, \mathsf{none}\}$, and a finite set $\mathrm{Pre}$ of prefix operator tokens, which bind tighter than every infix operator (we give them level $k+1$). $O_p = \{\, o \in O \mid \mathrm{lev}(o) = p \,\}$. The other tokens are atoms (identifiers, literals) and the parentheses ( ). A token may be both infix and prefix (-).

The running table $T_{\mathrm{ar}}$

$O_1 = \{+, -\}$ left, $O_2 = \{*, /\}$ left, $O_3 = \{\hat{}\}$ right, $\mathrm{Pre} = \{-\}$ (level 4). The running input is $w$ = a - b * c ^ d ^ e - f.

Definition 4.1.2 (Layered grammar and the tree of an expression)

The layered grammar $G_T$ has nonterminals $E_1, \dots, E_{k+1}, A$, start symbol $E_1$ and, for each level $p \le k$ and each $o \in O_p$,

\[ \begin{aligned} E_p &\to E_p \; o \; E_{p+1} \mid E_{p+1} && \text{if } \mathrm{assoc}(p) = \mathsf{left} \\ E_p &\to E_{p+1} \; o \; E_p \mid E_{p+1} && \text{if } \mathrm{assoc}(p) = \mathsf{right} \\ E_p &\to E_{p+1} \; o \; E_{p+1} \mid E_{p+1} && \text{if } \mathrm{assoc}(p) = \mathsf{none} \end{aligned} \]

and $E_{k+1} \to u \; E_{k+1} \mid A$ for $u \in \mathrm{Pre}$, $A \to a \mid (\, E_1 \,)$ for every atom $a$. For $v \in L(E_p)$ with its (unique, Lemma 4.1.4) parse tree, $\mathrm{tree}_p(v)$ is the S-expression read off that tree: a production $E_q \to X\, o\, Y$ gives $(o\ \mathrm{tree}(X)\ \mathrm{tree}(Y))$, $E_{k+1} \to u\, E_{k+1}$ gives $(u\ \mathrm{tree}(\cdot))$, $A \to a$ gives $a$, and unit productions and parentheses add nothing. $\mathrm{tree}(w) = \mathrm{tree}_1(w)$ is the tree of $w$: the specification every algorithm of this lesson must meet.

Definition 4.1.3 (Chunks and depth-0 operators)

A chunk is a string of $L(E_{k+1})$: zero or more prefix operators followed by an atom or by a parenthesized $L(E_1)$ string. Every $x \in L(E_1)$ factors uniquely as $x = c_0\, o_1\, c_1\, o_2 \cdots o_r\, c_r$ with chunks $c_i$ and infix operators $o_i$; the $o_i$ are the depth-0 operators of $x$ (those outside every parenthesis). For a level $p$, the factorization is $p$-admissible if $\mathrm{lev}(o_i) \ge p$ for all $i$ and no two depth-0 operators $o_s, o_t$ ($s < t$) of the same non-associative level $q$ have only operators of level $\ge q$ between them.

Chunks of the running input

$w = c_0\, o_1 \cdots o_5\, c_5$ with chunks $a, b, c, d, e, f$ and depth-0 operators $-_1, *, \hat{}_1, \hat{}_2, -_2$ of levels $1, 2, 3, 3, 1$. The factorization is 1-admissible, not 2-admissible.

Lemma 4.1.4 (Structure of the layered language: the root rule)

Let $x = c_0\, o_1\, c_1 \cdots o_r\, c_r$ as in Definition 4.1.3. Then $x \in L(E_p)$ if and only if the factorization is $p$-admissible and every chunk is in $L(E_{k+1})$. In that case $x$ has exactly one parse tree from $E_p$, and $\mathrm{tree}_p(x)$ is determined by the root rule: if $r = 0$ it is the tree of the chunk; otherwise let $q = \min_i \mathrm{lev}(o_i)$ and let $o_s$ be the last operator of level $q$ if $\mathrm{assoc}(q) = \mathsf{left}$, the first if $\mathsf{right}$, the only one if $\mathsf{none}$; then $\mathrm{tree}_p(x) = (o_s\ \mathrm{tree}_q(c_0 \cdots c_{s-1})\ \mathrm{tree}_{q'}(c_s \cdots c_r))$ with $q' = q$ for a right-associative level and $q' = q + 1$ otherwise.

Proof

By induction on $|x|$. Chunks ($r = 0$): a derivation from $E_p$ that uses a binary production produces a depth-0 operator, so it must take the unit productions $E_p \Rightarrow E_{p+1} \Rightarrow \cdots \Rightarrow E_{k+1}$; from $E_{k+1}$ the first token decides the production (a prefix operator, an atom or (), and the parenthesized case uses the induction hypothesis on the shorter inside. So $x \in L(E_p)$ iff $x \in L(E_{k+1})$, with one tree.

Operators present ($r \ge 1$). ($\Rightarrow$) Every sentential form derived from $E_q$ has depth-0 operators of level $\ge q$ only, because each binary production of $E_q$ introduces an operator of level $q$ between strings derived from $E_q$ or $E_{q+1}$ (induction on the derivation). So $x \in L(E_p)$ forces $\mathrm{lev}(o_i) \ge p$. For $\mathsf{none}$ levels: $E_q \to E_{q+1}\, o\, E_{q+1}$ puts no depth-0 operator of level $\le q$ into either side, so two level-$q$ operators of a non-associative level are always separated by an operator of lower level; this is admissibility.

($\Leftarrow$, and uniqueness) Let $q$ be the minimum level. Every derivation from $E_p$ must reach $E_q$ through unit productions, since a binary production at a level $p' < q$ would create a depth-0 operator of level $p' < q$. At $E_q$ with $\mathsf{left}$: the production must be $E_q \to E_q\, o\, E_{q+1}$ (otherwise no level-$q$ operator appears at depth 0), and the right side $E_{q+1}$ derives no depth-0 level-$q$ operator, so $o$ is the last level-$q$ operator $o_s$: the split is forced. The left part $c_0 \cdots c_{s-1}$ is $q$-admissible, the right part $c_s \cdots c_r$ is $(q+1)$-admissible (all its operators have level $> q$ by the choice of $s$), both are shorter, so by the induction hypothesis each is in the language with a unique tree, and the production applies. $\mathsf{right}$ is symmetric (the first level-$q$ operator is forced, the right side is $q$-admissible). $\mathsf{none}$: admissibility says there is only one level-$q$ operator, both sides are $(q+1)$-admissible. In every case exactly one parse tree exists, and reading it off gives the root rule.

The root rule on the running input

$q = 1$, left: the root is the last - ($-_2$). The left part a - b * c ^ d ^ e has root $-_1$ (the only level-1 operator), whose right part b * c ^ d ^ e has root *, whose right part c ^ d ^ e (right-associative) has root the first ^. So $\mathrm{tree}(w) = (-\ (-\ a\ (*\ b\ (\hat{}\ c\ (\hat{}\ d\ e))))\ f)$.

Precedence-layered grammar¶

The layered grammar is left-recursive; recursive descent (Lesson 2.5) parses it after the left recursion becomes a loop (Lesson 2.4): $E_p \to E_{p+1} \{ o\, E_{p+1} \}$ for a left level, building the tree left-nested as the loop runs.

Algorithm 4.1.5 (ParseLayered: one function per level)

Input: an operator table $T$ with $k$ levels; tokens $t_1 \cdots t_n\, \$$; look is the current token.
Output: $\mathrm{tree}(w)$, or a syntax error.
Precondition: $\mathrm{Pre}$ binds tighter than every infix level (Definition 4.1.1).
Postcondition: returns $\mathrm{tree}(w)$ iff $w \in L(G_T)$, else reports an error (Theorem 4.1.14).
Invariant: a call Level(p) that returns normally has consumed a $p$-admissible string $x$ and returns $\mathrm{tree}_p(x)$; the token after $x$ is not an infix operator of level $\ge p$ (Lemma 4.1.11).

function Parse(w):   e ← Level(1);  expect($);  return e

function Level(p):                       # 1 ≤ p ≤ k + 1
    if p = k + 1: return Unary()
    lhs ← Level(p + 1)
    if assoc(p) = left:
        while look ∈ O_p:  o ← advance();  lhs ← (o lhs Level(p + 1))
    else if assoc(p) = right:
        if look ∈ O_p:     o ← advance();  lhs ← (o lhs Level(p))
    else:                                # none
        if look ∈ O_p:
            o ← advance();  lhs ← (o lhs Level(p + 1))
            if look ∈ O_p: error("non-associative operators chained")
    return lhs

function Unary():
    if look ∈ Pre:  u ← advance();  return (u Unary())
    if look is an atom:  return advance()
    if look = "(":  advance();  e ← Level(1);  expect(")");  return e
    error("expected an operand")

CPython's grammar is layered: one PEG rule per level

Reproduce (CPython 3.11.15; the grammar file is Grammar/python.gram at tag v3.11.15 [CPY-Gram]):

python3.11 -c "import ast; print(ast.dump(ast.parse('a - b * c - d << 1', mode='eval').body, indent=1))"

Output (complete):

BinOp(
 left=BinOp(
  left=BinOp(
   left=Name(id='a', ctx=Load()),
   op=Sub(),
   right=BinOp(
    left=Name(id='b', ctx=Load()),
    op=Mult(),
    right=Name(id='c', ctx=Load()))),
  op=Sub(),
  right=Name(id='d', ctx=Load())),
 op=LShift(),
 right=Constant(value=1))

What to notice: the rules behind this tree are shift_expr: shift_expr '<<' sum | … | sum, sum: sum '+' term | sum '-' term | term, term: term '*' factor | … | factor: exactly $G_T$ of Definition 4.1.2, left recursion and all (pegen supports left-recursive rules, Lesson 4.2). The root is the loosest operator <<, and the two - nest to the left: the root rule of Lemma 4.1.4.

Precedence climbing¶

Look at the layered calls on one operand: Level(1) calls Level(2) calls … Level(k+1), and on the way back each level checks whether the lookahead is one of its operators. Precedence climbing merges those $k$ functions into one, parameterized by the minimum level.

Algorithm 4.1.6 (Precedence climbing)

Input: $T$ and the tokens, as in Algorithm 4.1.5.
Output: $\mathrm{tree}(w)$ or an error.
Precondition: as in Algorithm 4.1.5.
Postcondition: Climb(p) returns what Level(p) returns (Lemma 4.1.11), so Parse returns $\mathrm{tree}(w)$ iff $w \in L(G_T)$.
Invariant: the operators absorbed by one call Climb(p) all have level $\ge p$; the loop's lhs is the tree of the consumed $p$-admissible prefix; last is the level of the previous operator if it was non-associative.

function Parse(w):   e ← Climb(1);  expect($);  return e

function Climb(p):
    lhs ← Unary()                          # Algorithm 4.1.5's Unary, calling Climb(1) inside ( )
    last ← none
    while look ∈ O and lev(look) ≥ p:
        q ← lev(look)
        if assoc(q) = none and last = q: error("non-associative operators chained")
        o ← advance()
        rhs ← Climb(q + 1 if assoc(q) ∈ {left, none} else q)
        lhs ← (o lhs rhs)
        last ← q if assoc(q) = none else none
    return lhs

Clang and Go: precedence climbing on C's and Go's tables

Reproduce (clang 23.1.2; go 1.24.7):

cat > prec.c <<'EOF'
int f(int a, int b, int c, int d) { return a - b * c - d << 1; }
EOF
clang-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics prec.c 2>&1 \
  | sed -n '/ReturnStmt/,$p' | grep -E 'BinaryOperator|DeclRefExpr|IntegerLiteral' | sed 's/0x[0-9a-f]*/0x…/g'
mkdir -p goprec && cat > goprec/main.go <<'EOF'
package main

import (
    "fmt"
    "go/ast"
    "go/parser"
)

func show(e ast.Expr) string {
    switch x := e.(type) {
    case *ast.BinaryExpr:
        return fmt.Sprintf("(%s %s %s)", x.Op, show(x.X), show(x.Y))
    case *ast.Ident:
        return x.Name
    case *ast.BasicLit:
        return x.Value
    }
    return "?"
}

func main() {
    for _, src := range []string{"a - b * c - d << 1", "a == b || c < d && e"} {
        e, _ := parser.ParseExpr(src)
        fmt.Printf("%-22s %s\n", src, show(e))
    }
}
EOF
(cd goprec && go run main.go)

Output (complete):

      `-BinaryOperator 0x… <col:44, col:61> 'int' '<<'
        |-BinaryOperator 0x… <col:44, col:56> 'int' '-'
        | |-BinaryOperator 0x… <col:44, col:52> 'int' '-'
        | | | `-DeclRefExpr 0x… <col:44> 'int' lvalue ParmVar 0x… 'a' 'int'
        | | `-BinaryOperator 0x… <col:48, col:52> 'int' '*'
        | |   | `-DeclRefExpr 0x… <col:48> 'int' lvalue ParmVar 0x… 'b' 'int'
        | |     `-DeclRefExpr 0x… <col:52> 'int' lvalue ParmVar 0x… 'c' 'int'
        |   `-DeclRefExpr 0x… <col:56> 'int' lvalue ParmVar 0x… 'd' 'int'
        `-IntegerLiteral 0x… <col:61> 'int' 1
a - b * c - d << 1     (- (- a (* b c)) (<< d 1))
a == b || c < d && e   (|| (== a b) (&& (< c d) e))

What to notice: the same tokens, two tables, two trees. In C << (level prec::Shift = 12 in OperatorPrecedence.h [CLANG-OpPrec]) is looser than - (prec::Additive = 13), so it is the root; in Go << shares precedence 5 with *, so d << 1 is the right operand of the last -. Clang's ParseRHSOfBinaryExpression(LHS, MinPrec) [CLANG-ParseExpr] is Algorithm 4.1.6: it stops when NextTokPrec < MinPrec and parses the right operand with ThisPrec + !isRightAssoc, exactly q + 1 for left and q for right (assignment and ?:). Go's parseBinaryExpr(x, prec1) [GO-ParseBinary] is the same loop with levels 1–5.

Pratt parsing¶

Pratt's formulation replaces levels by binding powers so that associativity becomes arithmetic: an operator binds with a left power to what precedes it and a right power to what follows.

Definition 4.1.7 (Binding powers of a table)

For $o \in O_p$: $(\mathrm{lbp}(o), \mathrm{rbp}(o)) = (2p, 2p+1)$ if $\mathrm{assoc}(p) \in \{\mathsf{left}, \mathsf{none}\}$ and $(2p+1, 2p)$ if $\mathsf{right}$; a non-associative level is also marked so that a second operator of it in the same loop is an error. A prefix operator $u$ has $\mathrm{rbp}(u) = 2(k+1)$. The level of a binding power is $\lambda(m) = \max(1, \lceil m/2 \rceil)$.

Binding powers of $T_{\mathrm{ar}}$

+, -: $(2, 3)$; *, /: $(4, 5)$; ^: $(7, 6)$; prefix -: right power 8. $\lambda(3) = 2$: after a -, only levels $\ge 2$ may continue the right operand; $\lambda(6) = 3$: after a ^, another ^ (left power 7 $\ge$ 6) may.

Algorithm 4.1.8 (Pratt parsing: expr_bp)

Input: binding powers (Definition 4.1.7); per token a nud (atom, prefix operator, () and a led (infix operator).
Output: $\mathrm{tree}(w)$ or an error.
Precondition: as in Algorithm 4.1.5.
Postcondition: ExprBP(m) returns what Climb(λ(m)) returns (Lemma 4.1.12); Parse returns $\mathrm{tree}(w)$ iff $w \in L(G_T)$.
Invariant: every operator absorbed by the loop of ExprBP(m) has $\mathrm{lbp} \ge m$; lhs is the tree of the consumed prefix.

function Parse(w):   e ← ExprBP(0);  expect($);  return e

function ExprBP(m):
    t ← advance()                          # nud: the token in operand position
    if t is an atom:       lhs ← t
    else if t = "(":       lhs ← ExprBP(0);  expect(")")
    else if t ∈ Pre:       lhs ← (t ExprBP(rbp(t)))
    else:                  error("expected an operand")
    last ← none
    loop:                                  # led: tokens after an operand
        o ← look
        if o ∉ O:                          # ")", "$", or garbage (caught by the caller)
            break
        if lbp(o) < m: break
        if o's level is non-associative and last = lbp(o): error("chained")
        advance()
        lhs ← (o lhs ExprBP(rbp(o)))
        last ← lbp(o) if o's level is non-associative else none
    return lhs

A postfix operator is a led that builds (o lhs) without a right operand; a mixfix ?: is a led for ? that parses ExprBP(0), expects :, then parses the right operand with its right power; a call f(…) and an index a[…] are leds of ( and [ with a left power above every infix level (§6).

rust-analyzer: Pratt parsing with (power, associativity) pairs

Reproduce (rust-analyzer 1.94.1, installed with rustup component add rust-analyzer):

printf 'fn f() { a - b * c - d << 1 }\n' > prec.rs
rust-analyzer parse < prec.rs | grep -E 'BIN_EXPR|MINUS|STAR|SHL|IDENT@|INT_NUMBER'

Output (complete):

      IDENT@3..4 "f"
        BIN_EXPR@9..27
          BIN_EXPR@9..22
            BIN_EXPR@9..18
                      IDENT@9..10 "a"
              MINUS@11..12 "-"
              BIN_EXPR@13..18
                        IDENT@13..14 "b"
                STAR@15..16 "*"
                        IDENT@17..18 "c"
            MINUS@19..20 "-"
                    IDENT@21..22 "d"
          SHL@23..25 "<<"
            INT_NUMBER@26..27 "1"

What to notice: current_op in crates/parser/src/grammar/expressions.rs [RA-Expr] returns (9, T![<<], Left), (10, T![-], Left), (11, T![*], Left), and expr_bp stops when op_bp < bp and recurses with op_bp + 1 for left associativity and op_bp for right: Algorithm 4.1.8 with Kladov's pair convention [Kla20]. Rust puts << below - like C, unlike Go. The @9..27 ranges are byte offsets in a lossless tree (Lesson 4.7).

Shunting-yard¶

Algorithm 4.1.9 (Shunting-yard)

Input: $T$ and the tokens.
Output: the reverse-Polish sequence of $w$ and $\mathrm{tree}(w)$ (built by an operand stack), or an error.
Precondition: as in Algorithm 4.1.5.
Postcondition: returns $\mathrm{tree}(w)$ iff $w \in L(G_T)$ (Theorem 4.1.14).
Invariant: in state operator (an operand was just completed), the infix operators on the stack between two parentheses have non-decreasing levels from bottom to top, strictly increasing except between right-associative operators of one level; prefix operators sit above the infix operators they bind tighter than (Lemma 4.1.13).

function ShuntingYard(w):
    out ← [];  ops ← [];  state ← operand
    for t in t1 … tn:
        if state = operand:
            if t is an atom:        Emit(t);  state ← operator
            else if t = "(":        push "(" on ops
            else if t ∈ Pre:        push prefix t on ops
            else: error("expected an operand")
        else:                                  # state = operator
            if t = ")":
                while top(ops) ≠ "(":           # error if ops runs out: unmatched ")"
                    Emit(pop(ops))
                pop(ops)                         # discard "("
            else if t ∈ O:
                while top(ops) binds at least as tightly as t:
                    if both are comparisons of one non-associative level: error("chained")
                    Emit(pop(ops))
                push t on ops;  state ← operand
            else: error("expected an operator")
    if state = operand: error("expected an operand at the end")
    while ops is not empty:                      # error if a "(" is left: unclosed
        Emit(pop(ops))
    return out, the single tree on the operand stack

function Emit(x):                                # append to the RPN output and build the tree
    append x to out
    if x is an atom:          push x on the operand stack
    if x is a prefix op:      pop r;  push (x r)
    if x is an infix op:      pop r;  pop l;  push (x l r)

"top binds at least as tightly as t": top is a prefix operator, or an infix operator with
lev(top) > lev(t), or lev(top) = lev(t) and assoc(lev(t)) ≠ right.   "(" never pops.

GCC's C parser: an explicit precedence stack

Reproduce (gcc 14.2.0; the function is unchanged on the releases/gcc-15 branch [GCC-CParser]):

cat > sy.c <<'EOF'
int f(int a, int b, int c, int d) { return a - b * c - d << 1; }
EOF
gcc-14 -c -fdump-tree-original=sy.orig sy.c -o /dev/null && cat sy.orig

Output (complete):

;; Function f (null)
;; enabled by -tree-original


{
  return (a - b * c) - d << 1;
}

What to notice: c_parser_binary_expression in gcc/c/c-parser.cc keeps a stack[NUM_PRECS] of (expression, operator, precedence) and, in its own comment, "when a new operator is encountered with precedence less than or equal to that at the top of the stack, triples E[i-1] op[i] E[i] are popped": Algorithm 4.1.9's reduction rule for C, whose binary operators are all left-associative. The dump prints the tree with the parentheses GCC needs to show it: (a - b * c) - d is the left operand of <<.

3. Worked example¶

The table is $T_{\mathrm{ar}}$ and the input a - b * c ^ d ^ e - f (the example after Definition 4.1.1). All four algorithms return $(-\ (-\ a\ (*\ b\ (\hat{}\ c\ (\hat{}\ d\ e))))\ f)$, the tree that the root rule predicts:

flowchart TD
  M2["- (root, last level-1)"] --> M1["- "]
  M2 --> F[f]
  M1 --> A[a]
  M1 --> S["*"]
  S --> B[b]
  S --> P1["^ (first level-3)"]
  P1 --> C[c]
  P1 --> P2["^"]
  P2 --> D[d]
  P2 --> E[e]

Precedence-layered grammar¶

Level(1) calls Level(2), which calls Level(3), which calls Level(4) = Unary(): four calls to read a. The table lists which call absorbs each operator and which call starts each operand (the operand chunks are the single atoms).

step	token	absorbed by	right operand parsed by	returns to the caller
1	`a`	`Unary` (via `Level(1)`→`Level(2)`→`Level(3)`→`Unary`)	—	`a` up to `Level(1)` (levels 2, 3 see `-`, not theirs)
2	`-`	`Level(1)` loop	`Level(2)`
3	`b`	`Unary` via `Level(2)`→`Level(3)`	—	`b` up to `Level(2)`
4	`*`	`Level(2)` loop	`Level(3)`
5	`c`	`Unary` via `Level(3)`	—	`c` to `Level(3)`
6	`^`	`Level(3)` (right)	`Level(3)` (recursive)
7	`d`	`Unary` via `Level(3)`	—	`d` to the inner `Level(3)`
8	`^`	inner `Level(3)`	`Level(3)`
9	`e`	`Unary`	—	`e`; the next token `-` is not level 3: return `(^ d e)`, then `(^ c (^ d e))`
10	`-`	not level 2: `Level(2)` returns `(* b …)`; `Level(1)` loop absorbs it	`Level(2)`	`(- a (* b …))` becomes `lhs`
11	`f`	`Unary` via `Level(2)`→`Level(3)`	—	`f`
12	`$`	nobody: every level returns; `Parse` expects `$`	—	the tree

Calls made: Level is called 16 times for 6 operands, as chains of 4, 3, 2, 2, 2 and 3 calls (Proposition 4.1.16 counts them in general).

Precedence climbing¶

One row per operator absorbed (the operands are read by Unary):

step	operator	its level, assoc	`Climb(p)` that absorbs it	right operand parsed by
1	`-`	1, left	`Climb(1)`	`Climb(2)`
2	`*`	2, left	`Climb(2)` (inside step 1)	`Climb(3)`
3	`^`	3, right	`Climb(3)` (inside step 2)	`Climb(3)`
4	`^`	3, right	the inner `Climb(3)` (inside step 3)	`Climb(3)`
5	`-`	1, left	`Climb(1)`: every inner call stops at it because $1 < 3, 3, 3, 2$	`Climb(2)`

The calls are Climb(1), Climb(2), Climb(3), Climb(3), Climb(3), Climb(2): six calls, one per operand.

Pratt parsing¶

The full trace (generated by the course oracle, tools/course/lib/exprparse.py); depth is the recursion depth:

step	depth	min_bp	token	event	detail
1	0	0	`a`	call	expr_bp(0)
2	0	0	`a`	atom	lhs = a
3	0	0	`-`	infix	lbp 2 ≥ 0: rhs = expr_bp(3)
4	1	3	`b`	call	expr_bp(3)
5	1	3	`b`	atom	lhs = b
6	1	3	`*`	infix	lbp 4 ≥ 3: rhs = expr_bp(5)
7	2	5	`c`	call	expr_bp(5)
8	2	5	`c`	atom	lhs = c
9	2	5	`^`	infix	lbp 7 ≥ 5: rhs = expr_bp(6)
10	3	6	`d`	call	expr_bp(6)
11	3	6	`d`	atom	lhs = d
12	3	6	`^`	infix	lbp 7 ≥ 6: rhs = expr_bp(6)
13	4	6	`e`	call	expr_bp(6)
14	4	6	`e`	atom	lhs = e
15	4	6	`-`	stop	lbp 2 < 6
16	4	6	`-`	return	return e
17	3	6	`^`	build	lhs = (^ d e)
18	3	6	`-`	stop	lbp 2 < 6
19	3	6	`-`	return	return (^ d e)
20	2	5	`^`	build	lhs = (^ c (^ d e))
21	2	5	`-`	stop	lbp 2 < 5
22	2	5	`-`	return	return (^ c (^ d e))
23	1	3	`*`	build	lhs = (* b (^ c (^ d e)))
24	1	3	`-`	stop	lbp 2 < 3
25	1	3	`-`	return	return (* b (^ c (^ d e)))
26	0	0	`-`	build	lhs = (- a (* b (^ c (^ d e))))
27	0	0	`-`	infix	lbp 2 ≥ 0: rhs = expr_bp(3)
28	1	3	`f`	call	expr_bp(3)
29	1	3	`f`	atom	lhs = f
30	1	3	`$`	stop	end of this operand
31	1	3	`$`	return	return f
32	0	0	`-`	build	lhs = (- (- a (* b (^ c (^ d e)))) f)
33	0	0	`$`	stop	end of this operand
34	0	0	`$`	return	return (- (- a (* b (^ c (^ d e)))) f)

Steps 9 and 12: the right power of ^ is 6, below its left power 7, so the second ^ continues inside the first one's right operand: right associativity.
Steps 15–25: the final - has left power 2, which is below every pending minimum (6, 6, 5, 3), so it unwinds four calls and is absorbed by the outermost call at step 27: this is where left associativity of the two - comes from.
The calls' minimum powers are $0, 3, 5, 6, 6, 3$; with $\lambda$ they are the levels $1, 2, 3, 3, 3, 2$ of the precedence-climbing calls (Lemma 4.1.10 predicts it).

Shunting-yard¶

One row per input token, plus the final pops (stacks bottom first):

step	token	action	operator stack	output (RPN)
1	`a`	operand → output	—	a
2	`-`	push `-`	-	a
3	`b`	operand → output	-	a b
4	`*`	push `*` (level 2 > 1)	- *	a b
5	`c`	operand → output	- *	a b c
6	`^`	push `^`	- * ^	a b c
7	`d`	operand → output	- * ^	a b c d
8	`^`	push `^` (same level, right-associative: no pop)	- * ^ ^	a b c d
9	`e`	operand → output	- * ^ ^	a b c d e
10	`-`	pop `^ ^ * -` (all bind at least as tightly), push `-`	-	a b c d e ^ ^ * -
11	`f`	operand → output	-	a b c d e ^ ^ * - f
12	`$`	pop `-`	—	a b c d e ^ ^ * - f -

Evaluating the RPN with a stack rebuilds the tree: ^ combines d e, the next ^ combines c (^ d e), * takes b, - takes a, then f and the last -.

Try it

./course drill pratt-trace --seed 3 --difficulty medium --solution and ./course drill shunting-yard --seed 5 --difficulty hard --solution generate new tables and inputs with the same trace formats; ./course drill pratt-trace --seed 7 --difficulty hard adds a prefix operator and non-associative levels.

4. Invariants and correctness¶

We prove each algorithm correct against the specification of Definition 4.1.2, then conclude that all four agree.

Lemma 4.1.10 (Binding powers encode levels)

Call $m$ an argument power if $m = 0$, $m = \mathrm{rbp}(o)$ for an infix operator $o$, or $m = \mathrm{rbp}(u)$ for a prefix operator $u$: these are the only values Algorithm 4.1.8 passes to ExprBP. For every infix operator $o$ and every argument power $m$: $\mathrm{lbp}(o) \ge m \iff \mathrm{lev}(o) \ge \lambda(m)$. Moreover $\lambda(\mathrm{rbp}(o)) = \mathrm{lev}(o) + 1$ for left and non-associative levels, $\lambda(\mathrm{rbp}(o)) = \mathrm{lev}(o)$ for right-associative ones, and $\lambda(\mathrm{rbp}(u)) = k + 1$.

Proof

Let $\mathrm{lev}(o) = q$, so $\mathrm{lbp}(o) \in \{2q, 2q + 1\}$. Case $m = 0$: both sides hold. Case $m$ even, $m = 2p$ ($\lambda(m) = p$): $2q \ge 2p \iff q \ge p$ and $2q + 1 \ge 2p \iff q \ge p$ (integers). Case $m$ odd, $m = 2p + 1$ ($\lambda(m) = p + 1$): an odd argument power is the right power of a left or non-associative operator of level $p$ (right powers of right-associative operators and of prefix operators are even), so level $p$ is not right-associative and no operator has left power $2p + 1$; hence $\mathrm{lbp}(o) \ge 2p + 1 \iff \mathrm{lbp}(o) \ge 2p + 2 \iff q \ge p + 1$ when $q \ne p$, and when $q = p$ we have $\mathrm{lbp}(o) = 2p < m$ and $q < p + 1$: both sides false. The formulas for $\lambda(\mathrm{rbp})$ are direct: $\lceil (2q+1)/2 \rceil = q + 1$, $\lceil 2q/2 \rceil = q$, $\lceil 2(k+1)/2 \rceil = k + 1$.

The odd case is why Definition 4.1.7 gives only right-associative operators an odd left power: an odd right power $2p+1$ must stop every operator of level $p$, and it does because no level-$p$ operator then has left power $2p + 1$. (With arbitrary $m$ the equivalence is false: a right-associative operator of level $p$ has left power $2p + 1 \ge 2p + 1$ although $p < \lambda(2p+1)$; such an $m$ never occurs.)

Lemma 4.1.11 (Layered descent and precedence climbing compute the root rule)

Let $x = c_0\, o_1 \cdots o_r\, c_r$ be a $p$-admissible string of chunks followed in the input by a token $s$ that is not an infix operator of level $\ge p$. Then Level(p) (Algorithm 4.1.5) and Climb(p) (Algorithm 4.1.6), started at the first token of $x$, both consume exactly $x$ and return $\mathrm{tree}_p(x)$. Conversely, whenever either call returns normally, the string it consumed is $p$-admissible, followed by such an $s$, and the returned tree is its $\mathrm{tree}_p$.

Proof

Both parts by induction on $|x|$, with an inner induction on $k + 1 - p$ for Level.

Chunks. Unary reads prefix operators and an atom or a parenthesized expression; inside the parentheses the call is Level(1)/Climb(1) on a shorter string followed by ), which is not an infix operator, so the induction hypothesis applies.

Climb(p). After Unary returns $c_0$, the loop absorbs $o_1$ (level $\ge p$ by admissibility). Its right operand call is Climb(p') with $p' = \mathrm{lev}(o_1) + 1$ (left, none) or $\mathrm{lev}(o_1)$ (right). Let $j$ be the first index $> 1$ with $\mathrm{lev}(o_j) < p'$, or $r + 1$ if there is none. The string $y = c_1\, o_2 \cdots c_{j-1}$ is $p'$-admissible (its operators have level $\ge p'$; the non-associative condition is inherited from $x$), and it is followed by $o_j$ (level $< p'$) or by $s$ (level $< p \le p'$ or not an operator), so by the induction hypothesis the call returns $\mathrm{tree}_{p'}(y)$. The loop then builds $(o_1\ c_0\ y)$ and continues with $o_j$. Repeating the argument, the loop builds $(\cdots((c_0\ o_1\ y_1)\ o_{j_1}\ y_2) \cdots)$ where the $o$'s are exactly the depth-0 operators of $x$ of level $<$ the $p'$ of their predecessor. Compare with the root rule: the minimum level $q$ is reached by the last absorbed operator for a left level (every later operator has level $> q$ and is inside the last right operand), by the first for a right level (its right operand, Climb(q), absorbs all later level-$q$ operators), and for a non-associative level there is only one. Unfolding the root rule recursively on the left part gives the same left spine. The loop stops at $s$, which has level $< p$ or is not an operator, so $x$ is consumed exactly. A second operator of a non-associative level $q$ that reaches the same loop after the first means no lower operator separates them: the error branch fires exactly on non-admissible input.

Level(p). Level(p) first calls Level(p+1), which by the (inner) induction hypothesis consumes the longest prefix of $x$ whose depth-0 operators have level $\ge p + 1$ and returns its tree; the next token is then a level-$p$ operator or ends $x$. For a left level the loop absorbs each level-$p$ operator and parses a maximal $(p+1)$-admissible right part: the result is left-nested over the level-$p$ operators, which is the root rule at level $p$ when $q = p$, and just $\mathrm{tree}_{p+1}(x)$ when $x$ has no level-$p$ operator (then $\mathrm{tree}_p = \mathrm{tree}_{p+1}$ by the unit production). Right and non-associative levels are analogous.

Converse. Every tree node built corresponds to a production of $G_T$ applied to the strings consumed by the calls it combines (induction on the call tree), and a call returns only when the lookahead is not an operator it may absorb; by Lemma 4.1.4 the string is then $p$-admissible and the tree is its unique tree.

Lemma 4.1.12 (Pratt = precedence climbing)

For every argument $m$ that Algorithm 4.1.8 passes to ExprBP, ExprBP(m) performs the same sequence of token reads, errors and tree constructions as Climb(λ(m)); in particular it returns the same tree.

Proof

Induction on the number of tokens consumed. The nud part is Unary with ExprBP(0) for Climb(1) inside parentheses ($\lambda(0) = 1$) and ExprBP(rbp(u)) for the operand of a prefix operator, which is Unary again because $\lambda(\mathrm{rbp}(u)) = k + 1$ admits no infix operator (Lemma 4.1.10). In the loop, ExprBP continues at $o$ iff $\mathrm{lbp}(o) \ge m$, iff $\mathrm{lev}(o) \ge \lambda(m)$ (Lemma 4.1.10), which is Climb's test; the right operand call ExprBP(rbp(o)) corresponds to Climb(λ(rbp(o))), which is Climb(q+1) or Climb(q) as in Algorithm 4.1.6 (Lemma 4.1.10 again); the non-associativity tests coincide because last records the same operator in both. By the induction hypothesis the recursive calls behave identically.

Lemma 4.1.13 (Shunting-yard simulates precedence climbing)

Run Algorithm 4.1.9 on $w$. At every point where the state is operator, let $f_1, \dots, f_d$ be the frames of precedence climbing that are active after it has read the same tokens (outermost first), and let each open parenthesis delimit a group. Then: (a) the infix operators on the stack are, bottom to top, the operators $o$ whose right-operand call Climb is among $f_1, \dots, f_d$, in the same order, with ( markers where Unary entered a parenthesized expression and prefix operators where Unary read one; (b) the operand stack holds, for each such pending operator, the tree of its left operand, and on top the tree of the operand just completed. Hence the final pops build $\mathrm{tree}(w)$, and the RPN output is its postorder.

Proof

Induction on the number of tokens read. Reading an atom (state operand) matches Unary returning an atom. Reading an infix operator $t$ of level $q$ in state operator: precedence climbing returns from every active frame whose minimum level exceeds $q$ (they cannot absorb $t$), and each return combines the pending operator of that frame with its left operand and the completed right operand; the frame that absorbs $t$ is the innermost one with minimum level $\le q$. On the stack, by (a), the pending operators above that frame are exactly those whose right-operand minimum is $> q$: the operators $o$ with $\mathrm{lev}(o) > q$, or $\mathrm{lev}(o) = q$ with $o$ left- or non-associative (minimum $q + 1$), plus prefix operators (minimum $k + 1 > q$). This is the "binds at least as tightly" test, and each pop builds the same tree as the corresponding return, by (b). Pushing $t$ then corresponds to the new right-operand frame. A ) pops to the matching ( just as the frames opened inside the parentheses return to Unary; the end marker pops everything just as every frame returns. The chained-comparison test fires when a non-associative operator would pop one of its own level, which is exactly when Climb's last test fires. Emitting in pop order is the postorder of the combinations.

Theorem 4.1.14 (The four expression parsers agree)

Let $T$ be an operator table whose prefix operators bind tighter than every infix level. For every token string $w$, Algorithms 4.1.5 (layered), 4.1.6 (precedence climbing), 4.1.8 (Pratt) and 4.1.9 (shunting-yard) each return $\mathrm{tree}(w)$ if $w \in L(G_T)$, and each report an error if $w \notin L(G_T)$. In particular they return the same tree on every input.

Proof

If $w \in L(G_T) = L(E_1)$, then $w$ is 1-admissible (Lemma 4.1.4) and followed by $\$$, so Level(1) and Climb(1) consume $w$ and return $\mathrm{tree}(w)$ (Lemma 4.1.11), the final expect($) succeeds, and Pratt and shunting-yard follow (Lemmas 4.1.12 and 4.1.13). If $w \notin L(G_T)$ and some algorithm returned normally, the consumed string would be all of $w$ (the final expect($), or the end of the token loop for shunting-yard) and, by the converse parts of Lemmas 4.1.11–4.1.13, $w$ would be 1-admissible and in $L(E_1)$: a contradiction.

What breaks without the hypothesis

Give prefix - a level below * (the mathematical convention -a^b = -(a^b) needs it below ^). Then a * - b is still meaningful to Pratt (the prefix operand is ExprBP(rbp(-)), which stops at nothing tighter), but the layered grammar of Definition 4.1.2 generates - b only at the level of the prefix operator, so the right operand $E_3$ of * cannot start with -: the layered parser rejects a * - b while Pratt accepts it. Languages resolve this by allowing prefix operators at the start of every operand (C, Rust, Pebble put them above all binary levels; Python places unary minus above * but below **, and its grammar then has factor: '-' factor | power and power: await_primary '**' factor, so the operand of ** may itself start with -).

5. Complexity¶

Let $n$ be the number of tokens, $k$ the number of infix levels, and $r$ the number of operands (chunks, counting those inside parentheses).

Proposition 4.1.15 (Linear time for climbing, Pratt and shunting-yard)

Precedence climbing, Pratt parsing and shunting-yard run in $\Theta(n)$ time. The recursion depth of the first two, and the stack height of the third, is $\Theta(n)$ in the worst case.

Proof

Pratt: every call of ExprBP begins by consuming a token (its nud), so there are at most $n$ calls; each loop iteration either consumes an operator or ends the loop, so the loops run at most $n + (\text{number of calls})$ times in total; everything else is $O(1)$ per step. Climbing is the same (Lemma 4.1.12). Shunting-yard: each token is pushed at most once and popped at most once, and each loop iteration pushes or pops. Lower bound: every token must be read. Depth: on $a \mathbin{\hat{}} a \mathbin{\hat{}} \cdots \mathbin{\hat{}} a$ (right-associative) or on $r$ nested parentheses, Pratt keeps $\Theta(n)$ frames open and shunting-yard $\Theta(n)$ stack entries.

Proposition 4.1.16 (The layered grammar pays per level)

On an input without prefix operators, Algorithm 4.1.5 makes $\sum_{i=1}^{r} (k + 2 - p_i)$ calls of Level, where $p_i$ is the level at which operand $i$'s chain of calls starts: $p_i = 1$ for the first operand and after (, $p_i = q + 1$ after a left or non-associative operator of level $q$, and $p_i = q$ after a right-associative one. This is at most $(k+1)\,r$, attained when every operand starts at level 1, and the running time is $\Theta(k\,n)$ in the worst case.

Proof

Each operand is reached by a chain Level(p_i), Level(p_i + 1), …, Level(k+1) of fresh calls ($k + 2 - p_i$ of them), and every call of Level belongs to exactly one such chain: a call is made either at the start of an operand's chain (as the right operand of an operator, as Level(1) inside parentheses, or by Parse) or by its caller at the next level down the chain. The values of $p_i$ are read off Algorithm 4.1.5. Each call does $O(1)$ work besides its callees and its loop iterations, and each loop iteration consumes an operator, so the time is $\Theta(\text{calls} + n)$. If all $r$ operands start at level 1 (for instance all operators at level 1), the count is $(k + 1)\,r$ with $r = \Theta(n)$. On the running example the chains start at levels $1, 2, 3, 3, 3, 2$ with $k + 2 = 5$: $4 + 3 + 2 + 2 + 2 + 3 = 16$ calls.

Pathological family. For the layered grammar: $x_1 \mathbin{\|} x_2 \mathbin{\|} \cdots \mathbin{\|} x_r$ in C's grammar costs $13\,r + 4$ calls (17 from expression down to primary-expression for $x_1$, then 13 from logical-AND-expression down for each later operand), against $r$ for climbing: the constant factor that made GCC and Clang abandon per-level functions. For recursion: $r$ nested parentheses around an atom use $\Theta(r)$ stack frames in every recursive method; pebblec caps the depth at 256 (pebble-spec §13.1 rule 4) and Clang at 256 brackets by default (-fbracket-depth), while shunting-yard only needs heap memory.

At scale. The comparison lab measures, on random Pebble expressions of about 28 500 tokens: Pratt 7.8 ms and 1.18 loop steps per token, shunting-yard 5.8 ms and 1.18 steps per token (reproduce with build/<preset>/bin/ch04-parsebench, SPEC §6).

Technique	Time (worst)	Time (typical)	Extra space	Variables
Layered grammar	$\Theta(k\,n)$	$k + 2 - p_i$ calls per operand	$O(n)$ stack	$k$ levels, $n$ tokens, $p_i$ of Proposition 4.1.16
Precedence climbing	$\Theta(n)$	1 call per operand	$O(n)$ stack
Pratt parsing	$\Theta(n)$	1 call per operand	$O(n)$ stack
Shunting-yard	$\Theta(n)$	1 push + 1 pop per operator	$O(n)$ heap

Precedence-layered grammar¶

EBNF loops instead of left recursion [Wir76]: E1 = E2 {("+"|"-") E2} builds left-nested trees in a loop — trade-off: the grammar is no longer left-recursive (LL-friendly) but the tree shape must come from the loop's accumulator, not from the grammar.
Precedence declarations in LR generators (%left/%right, Lesson 3.5): an ambiguous one-level grammar plus a table — trade-off: fewer states and nonterminals, but correctness now depends on conflict resolution rather than on the grammar.

Precedence climbing¶

Clang's extensions [CLANG-ParseExpr]: ?: handled in the loop by parsing the middle operand with the lowest precedence, and C++'s > inside template argument lists turned off by a flag (GreaterThanIsOperator) — trade-off: context enters the table.
Norvell's "classic" form [Nor99]: one function per level for the few levels with special syntax, climbing for the rest — trade-off: hybrid code, but each unusual level (comparisons in Python, chained a < b < c) gets its own place.

Pratt parsing¶

Pairs of binding powers [Kla20] instead of Pratt's single binding power plus "subtract one for right associativity" — trade-off: none in power; associativity is visible in the table.
Mixfix and postfix as leds: ?:, calls, indexing, as (Pebble's cast is a postfix led with power 10 whose argument is a type), and Rust's .. ranges — trade-off: every construct is local to one token's handlers, at the price of a grammar that exists only in code.
User-defined operators (Swift, Haskell): the parser collects a flat sequence e1 op1 e2 op2 … and folds it later, when the declared precedences are known. Swift's type checker does this in foldSequence (lib/Sema/TypeCheckExpr.cpp [SWIFT-Fold]) — trade-off: precedence can depend on imported declarations, but the parser cannot build the tree on its own.

Shunting-yard¶

Prefix/postfix operators via a two-state automaton (operand expected vs operator expected), as in Algorithm 4.1.9 and the lab — trade-off: the state doubles the cases but distinguishes unary from binary - without lookahead.
Floyd's operator-precedence parsing (Lesson 3.5) derives the pop/push decisions from precedence relations computed from a grammar — trade-off: works for operator grammars in general, but relations can conflict and error detection is weak.

7. In real compilers¶

Precedence-layered grammar¶

CPython's Grammar/python.gram [CPY-Gram] layers disjunction, conjunction, inversion, comparison, bitwise_or, …, power, primary, and pegen turns the left-recursive levels into memoized seed-growing functions (Lesson 4.2). Language standards (C23 §6.5, ECMAScript) specify expressions this way even when their compilers do not parse them this way. The real-world box is in §2.

Precedence climbing¶

Clang clang/lib/Parse/ParseExpr.cpp, Parser::ParseRHSOfBinaryExpression with the levels of clang/include/clang/Basic/OperatorPrecedence.h [CLANG-ParseExpr, CLANG-OpPrec]; Go src/go/parser/parser.go, parseBinaryExpr [GO-ParseBinary]; rustc compiler/rustc_parse/src/parser/expr.rs, parse_expr_assoc_with [RUSTC-ParseExpr]; V8 src/parsing/parser-base.h, ParseBinaryExpression/ParseBinaryContinuation [V8-ParserBase]. The box in §2 shows Clang and Go.

Pratt parsing¶

rust-analyzer crates/parser/src/grammar/expressions.rs, expr_bp and current_op [RA-Expr]; JSLint/JSHint [Cro07]; the pebblec reference parser, solutions/pebble/lib/Parse/src/ParseExpr.cpp, Parser::parseExprBP (look after your own E2). The box in §2 shows rust-analyzer.

Shunting-yard¶

GCC gcc/c/c-parser.cc, c_parser_binary_expression, and the C++ front end's cp_parser_binary_expression in gcc/cp/parser.cc [GCC-CParser, GCC-CPParserBin]: an explicit stack of (expression, operator, precedence). Calculators and spreadsheet formula engines use the textbook form. The box in §2 shows GCC.

LLVM

LLVM's own textual parsers need no precedence: LLVM IR (llvm/lib/AsmParser/LLParser.cpp) is prefix-structured. The precedence-driven parsers in the LLVM project are Clang's (above) and the one in the Kaleidoscope tutorial, whose ParseBinOpRHS(int ExprPrec, …) is precedence climbing with a BinopPrecedence map (llvm/examples/Kaleidoscope/Chapter2/toy.cpp [LLVM-Kaleidoscope]).

Find where Clang decides associativity

Open clang/lib/Parse/ParseExpr.cpp at llvmorg-23.1.2 and find the variable that decides whether an operator's right operand may contain another operator of the same precedence. Which two precedence levels are right-associative? (Quiz question find-clang-right-assoc.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Precedence-layered grammar	Any finite table of infix levels (+ prefix above them), as an unambiguous CFG usable by every LL/LR/PEG tool	$\Theta(k\,n)$ · up to $(k+1)$ calls per operand (16 calls for 6 operands in §3)	The grammar documents the language; errors per level ("expected term")	Low per level, but one rule and function per level	Language standards, generated parsers, CPython's PEG grammar
Precedence climbing	Same trees as the layered grammar (Theorem 4.1.14); `?:` and context flags added by hand	$\Theta(n)$ · one call per operand	Good; errors where an operand is missing	Low: one loop and a level table	Clang, Go, rustc, V8
Pratt parsing	Same, plus prefix/postfix/mixfix/call/index as per-token handlers	$\Theta(n)$ · one call per operand (1.18 steps/token, 7.8 ms at 28 500 tokens in the lab)	Good; handlers give token-specific messages	Low: a table of (nud, led, powers)	rust-analyzer, JSLint, `pebblec`
Shunting-yard	Same trees; prefix/postfix via a two-state automaton	$\Theta(n)$ · no recursion (1.18 steps/token, 5.8 ms at 28 500 tokens in the lab)	Weaker: errors are detected on stack states, far from their cause	Low for infix; fiddly for calls and prefix operators	GCC's C/C++ binary expressions, calculators, RPN conversion

Choose the layered grammar when a grammar is the deliverable (a standard, a generator input) or there are only a few levels. Choose precedence climbing when you hand-write a recursive-descent parser for a C-like language and want the minimum of code. Choose Pratt parsing when the expression language keeps growing (postfix, mixfix, user-visible operators) or you want every construct's syntax next to its token. Choose shunting-yard when recursion depth must be bounded by heap rather than stack, or you need RPN output directly.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Precedence-layered grammar	`layered-calls`, `root-rule`	`pratt-trace` (the tree is the layered tree)	`layered`	lab stretch goal
Precedence climbing	`climb-min-level`, `find-clang-right-assoc`	`pratt-trace` (levels = $\lambda$ of powers)	`climbing`	lab stretch goal
Pratt parsing	`pratt-calls`, `pratt-bp-right`	`pratt-trace`	`pratt`	E2, lab L1
Shunting-yard	`sy-stack`, `sy-rpn`, `gcc-shunting`	`shunting-yard`	`shunting-yard`	lab L2

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Extra space	Variables
Layered grammar	\(\Theta(k\,n)\)	\(k + 2 - p_i\) calls per operand	\(O(n)\) stack	\(k\) levels, \(n\) tokens, \(p_i\) of Proposition 4.1.16
Precedence climbing	\(\Theta(n)\)	1 call per operand	\(O(n)\) stack
Pratt parsing	\(\Theta(n)\)	1 call per operand	\(O(n)\) stack
Shunting-yard	\(\Theta(n)\)	1 push + 1 pop per operator	\(O(n)\) heap

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Precedence-layered grammar	Any finite table of infix levels (+ prefix above them), as an unambiguous CFG usable by every LL/LR/PEG tool	\(\Theta(k\,n)\) · up to \((k+1)\) calls per operand (16 calls for 6 operands in §3)	The grammar documents the language; errors per level ("expected term")	Low per level, but one rule and function per level	Language standards, generated parsers, CPython's PEG grammar
Precedence climbing	Same trees as the layered grammar (Theorem 4.1.14); `?:` and context flags added by hand	\(\Theta(n)\) · one call per operand	Good; errors where an operand is missing	Low: one loop and a level table	Clang, Go, rustc, V8
Pratt parsing	Same, plus prefix/postfix/mixfix/call/index as per-token handlers	\(\Theta(n)\) · one call per operand (1.18 steps/token, 7.8 ms at 28 500 tokens in the lab)	Good; handlers give token-specific messages	Low: a table of (nud, led, powers)	rust-analyzer, JSLint, `pebblec`
Shunting-yard	Same trees; prefix/postfix via a two-state automaton	\(\Theta(n)\) · no recursion (1.18 steps/token, 5.8 ms at 28 500 tokens in the lab)	Weaker: errors are detected on stack states, far from their cause	Low for infix; fiddly for calls and prefix operators	GCC's C/C++ binary expressions, calculators, RPN conversion

Lesson 4.1 — Expression parsing: layered grammars, precedence climbing, Pratt parsing, shunting-yard¶

1. Problem and motivation¶

Precedence-layered grammar¶

Precedence climbing¶

Pratt parsing¶

Shunting-yard¶

2. Definitions and algorithms¶

Precedence-layered grammar¶

Precedence climbing¶

Pratt parsing¶

Shunting-yard¶

3. Worked example¶

Precedence-layered grammar¶

Precedence climbing¶

Pratt parsing¶

Shunting-yard¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Precedence-layered grammar¶

Precedence climbing¶

Pratt parsing¶

Shunting-yard¶

7. In real compilers¶

Precedence-layered grammar¶

Precedence climbing¶

Pratt parsing¶

Shunting-yard¶

8. Comparison¶

9. Assessment¶

References¶