Precedence Climbing for Binary Expressions

A grammar with one nonterminal per precedence level is the textbook way to parse expressions: expr for addition, term for multiplication, factor for primaries, and so on. It is correct, it is obviously left-associative, and it collapses under its own weight as soon as a language has ten levels. Ten mutually recursive functions, each with a loop and a switch, is a lot of code to change when a new operator is added, and the shape of the recursion no longer tells a reader anything about the language.

Precedence climbing replaces all of it with one function and a table.

One function, one parameter

The parser carries a minimum binding power. It parses a left operand, then loops: while the next token is a binary operator whose binding power is at least the minimum, it consumes the operator, recursively parses the right operand with a threshold derived from that operator, and combines.

# Higher number binds tighter. Left-associative: rhs threshold is prec + 1.
# Right-associative: rhs threshold is prec.
BINARY = {
    "+": (10, "left"), "-": (10, "left"),
    "*": (20, "left"), "/": (20, "left"),
    "^": (30, "right"),
}

def parse_binary(p, min_prec=0):
    left = parse_primary(p)
    while True:
        tok = p.peek()
        entry = BINARY.get(tok.kind)
        if entry is None:
            return left
        prec, assoc = entry
        if prec < min_prec:
            return left
        p.advance()
        next_min = prec + 1 if assoc == "left" else prec
        right = parse_binary(p, next_min)
        left = ("binop", tok.kind, left, right)

The loop is what makes the parse left-associative for + without any recursion on the left. After combining a + b, the loop returns to the top with the combined node as left and tests the next operator again, so a chain of equal precedence nests to the left. The recursion happens only on the right operand, and for a left-associative operator only when the next operator binds tighter, so a chain of same-precedence left-associative operators consumes constant stack depth regardless of length. A right-associative operator recurses once per operator in the chain, which is the cost of getting the tree shape the language asks for.

A right-associative operator passes its own precedence as the threshold rather than one more. The recursive call then sees an operator of equal precedence, accepts it because the test is >=, and the chain nests to the right. This single-character difference in the threshold is the entire associativity mechanism, and it is the part easiest to get wrong when the table is edited.

Why the threshold is a minimum and not an equality

The test prec < min_prec with >= acceptance is what allows a tighter operator to appear to the right of a looser one without the outer loop consuming it. When parsing the right operand of + with threshold 11, a following * at precedence 20 passes the test and is consumed inside the recursive call, so the multiplication becomes a child of the addition.

An equality test would instead stop the loop at any operator that differs, and the parse would fail or produce a wrong tree as soon as precedence levels mixed. The asymmetry is deliberate: the left side has already been consumed and cannot be revisited, so the loop may only extend it with operators at or above the threshold, while the right side is still open and may take anything that binds tighter.

The correspondence to a layered grammar

Precedence climbing and the layered grammar accept exactly the same language and, with matching tables, build exactly the same tree. The correspondence is direct: each precedence level becomes a threshold value, and the operator’s associativity decides whether the recursive call’s threshold is one higher or equal.

The advantage is that the grammar becomes data. Adding an operator is one line in a dictionary, not a new function plus an edit to two callers. The disadvantage is that the language’s precedence table is no longer visible as code structure, so a reviewer must consult the table to know what a + b * c means. For a language with a published precedence table in its specification, keeping the parser’s table in the same order as the specification’s is worth the discipline.

There is a subtler cost: the layered grammar’s functions are individually simple, and each can be given a precise error message naming the construct. The single climbing function has one error path for all binary operators, so a diagnostic has to be assembled from the operator table at the failure point rather than being written once per level.

Unary operators and the prefix boundary

Prefix operators do not fit the binary loop directly, because they have no left operand. The usual treatment is a separate step between the primary parse and the binary loop: collect the prefix operators, parse the operand at the prefix operator’s binding power, then apply them in reverse.

The threshold used for the operand is where the interesting decisions live. In C, prefix - binds tighter than * but looser than a postfix call, so -f(x) is a negation of a call rather than a call on a negation. Setting the prefix operand’s threshold just above multiplication’s value produces that grouping. Getting it wrong is not a crash; it is a wrong tree that survives until a later pass and shows up as an unexpected type error.

Postfix operators are easier: they apply to whatever the primary parse produced, and they can be handled inside the primary parser or in a loop immediately after it. Their binding power is the highest, so they consume their operand before any binary operator sees it.

Where the method breaks down

Precedence climbing assumes the operator table is a total order with no ambiguity. Two operators at the same precedence with different associativity produce a grammar that no table can express, and the parser will silently impose whichever rule the threshold arithmetic produces.

The method also assumes every binary operator is left- or right-associative in a uniform way. Operators that are non-associative, such as comparison in some languages, must be rejected explicitly: after parsing one comparison at that level, the parser checks that the next token is not another comparison at the same level, and reports an error if it is. Without that check the chain parses as left-associative and the language accepts input its specification rejects.

A third limit is that the technique is for binary infix expressions. A construct whose precedence depends on the operand types, or one that is only sometimes infix, needs a predicate in the loop, which puts the decision back into code and out of the table.

A fourth is error reporting quality. A layered grammar fails inside the function for the level it was parsing, so the diagnostic knows it was in a multiplicative expression and can say so. The climbing parser fails inside a recursive call whose threshold value is the only clue to the level, and a threshold of 41 means “addition” only if the reader consults the table. Storing a representative token kind alongside each precedence level, and naming that token in the diagnostic, recovers most of the lost specificity for a few lines of code.

For grammars that are not expression-shaped, and where rewriting the grammar is not an option, the table-driven alternative is described in LALR Table Construction and What the Conflicts Mean. The token-level questions that precede any of this, such as how a+++b splits, belong to Maximal Munch and the Boundary Between Tokens.

A table with mixed associativity

The table form is worth seeing with a mix of all three associativities, because that is where the threshold arithmetic earns its keep.

Operator	Precedence	Associativity	Right-hand threshold
=	5	right	5
||	10	left	11
&&	20	left	21
==	30	non-associative	31, with a post-check
+ -	40	left	41
* /	50	left	51
unary prefix	60	prefix	61 (the operand must not swallow a lower binary operator)
call, index	70	postfix	—

Reading the table as a parser: a = b = c parses as a = (b = c) because the right-hand threshold for = equals its own precedence, so the inner assignment is accepted. a == b == c parses the first comparison, then finds a second at the same threshold, which the non-associativity check rejects. -a * b groups as (-a) * b: the prefix step parses its operand at threshold 61, which admits only the tighter postfix level, so the loop that follows the prefix handles * and builds the multiplication.

The numbers themselves are arbitrary; only their order matters. Choosing them with gaps of ten leaves room to insert a new level without renumbering, which is the same reason old code leaves gaps in enumerated constants. When the gaps run out, the table is a few dozen entries and renumbering it is a mechanical edit.