In precedence climbing, how does one minimum-binding-power loop parse an expression that a layered grammar would need a rule per level for?

middlemust knowfreq 62%

answer

numbers, not layers
one loop, one operand step
a floor the caller sets
compare left power against the floor
the right power becomes the next floor

basics

~20 s

A binding power is a number per operator saying how tightly it grips its neighbours. One loop parses an operand, then keeps absorbing operators whose power clears the caller's minimum, recursing once per right operand.

solid answer

~50 s

Instead of a function per precedence level, every operator gets numbers in a table: a left binding power for how tightly it grips the operand on its left, and a right binding power that it imposes on its own right operand. A single function parse_expr(min_bp) parses one operand, then loops: if the next token is an infix operator whose left power is at least min_bp, it consumes the operator, calls itself with that operator's right power to build the right operand, combines the two into a node and goes round again; otherwise it stops and returns. The min_bp argument carries the context that the chain of per-level calls used to carry — it is a promise not to steal an operator the caller wanted. Adding an operator is then a row in the table rather than a new function.

Instead of a function per precedence level, every operator gets numbers in a table: a left binding power for how tightly it grips the operand on its left, and a right binding power that it imposes on its own right operand. A single function `parse_expr(min_bp)` parses one operand, then loops: if the next token is an infix operator whose left power is at least `min_bp`, it consumes the operator, calls itself with that operator's right power to build the right operand, combines the two into a node and goes round again; otherwise it stops and returns. The `min_bp` argument carries the context that the chain of per-level calls used to carry — it is a promise not to steal an operator the caller wanted. Adding an operator is then a row in the table rather than a new function.

code

pseudocode · 16 lines

pseudocode

# left_power(op) and right_power(op) come from a table
# left-associative op at level L:  left = L, right = L + 1
# right-associative op at level L: left = L, right = L

function parse_expr(min_bp):
    left = parse_operand()          # literal, name, or ( expr )
    loop:
        op = peek_token()
        if op is not an infix operator:
            break
        if left_power(op) < min_bp:
            break
        take_token()                # consume the operator
        right = parse_expr(right_power(op))
        left = node(op, left, right)
    return left

go deeper

for a junior

Know that operator precedence has to be encoded somewhere, and that one common way is a table of numbers per operator rather than a separate parse function for each level.

for a middle

Be able to state what the minimum binding power means, write the loop from memory, and trace a three-operator expression showing which call refuses which operator and why.

for a senior

Show why this shape survives a growing operator set: adding a row touches no existing code path, so the change is reviewable and the risk sits in the numbers rather than in control flow.

for a principal

Weigh legibility against extensibility. Precedence as numbers is data you can change and even load at run time, but it stops being readable off the parser, so the precedence table becomes a documented artefact you own.

Why a rule per precedence level gets expensive

An expression language with the usual arithmetic, comparison and logical operators has ten to twenty precedence levels. The textbook hand-written shape gives each level its own function: the addition level loops over + and - and calls the multiplication level for each of its operands, the multiplication level loops over * and / and calls the level below it, and so on down to the function that reads a literal, a name or a bracketed sub-expression. The nesting of the calls is the precedence — an operator can only ever capture operands produced by a tighter level.

That works, and it has two costs that surface as soon as the operator set stops being fixed.

Every addition is at least two edits. A new level means a new function plus a change to the function above it, so that the chain still routes through the new one.
Every operand pays for every level. Parsing the single literal 7 descends through all fifteen or twenty functions before a token is consumed, because the only route to the operand reader is the whole chain.

Binding power: one number per side of an operator

Precedence climbing deletes the chain and replaces it with data. Each infix operator carries two numbers — a left binding power, saying how strongly it grips the operand on its left, and a right binding power, the floor it imposes on the parse of its own right operand. Higher means tighter. Gaps of ten are conventional, so a level can be inserted later without renumbering the table.

operator	left power	right power
`or`	3	4
`and`	5	6
`=`, `<`	7	8
`+`, `-`	10	11
`*`, `/`	20	21
`^`	30	30

The loop

One function does the parsing. It takes a minimum binding power — the loosest operator this call is allowed to swallow — and does three things:

Parse one operand: a literal, a name, or a bracketed sub-expression.
Look at the next token. If it is not an infix operator, or its left power is below the minimum, stop and hand back what has been built.
Otherwise consume the operator, call the same function recursively with that operator's right power to build its right operand, combine the two into a node, and go round again.

The recursion carries the context that the call chain used to carry. The minimum is not a counter and not a depth limit: it is a promise to the caller that this call will not take an operator the caller wanted for itself.

A trace

Parsing 1 + 2 * 3 - 4 with the table above, starting at a floor of 0:

Parse 1. The next token + has left power 10, which clears the floor 0, so consume it.
Recurse with the right power 11. That call parses 2, sees * at left power 20, which clears 11, consumes it and recurses with 21.
The innermost call parses 3, then sees - at left power 10, below its floor of 21, so it stops and returns 3.
The middle call builds 2 * 3, then sees - at 10, below its own floor of 11, so it stops and returns 2 * 3.
The outer call builds 1 + (2 * 3), sees - at 10 still clearing its floor of 0, consumes it and recurses with 11 to get 4.

The result is ((1 + (2 * 3)) - 4). No function in the parser mentions * by name, and no level of the language has a function of its own.

What the flat shape buys

Adding an operator is a row, not a function and not an edit to an existing code path. In a tool whose users keep asking for one more operator — the formula evaluator behind a report's calculated columns is the standard case — that is the whole point.
Parsing an operand costs one call, not one per level, because the descent is gone.
The precedence data can be built at run time, since it is a table rather than the shape of the code; a layered rule set cannot offer that without regenerating the parser.
The same loop accommodates the other fixities: an operator with no left operand is consumed by the operand step, and one with no right operand is a wrap-and-continue branch inside the loop.

The price is that precedence is no longer legible as the shape of the parser. It lives in numbers, which have to be documented deliberately rather than read off the code.

## Why a rule per precedence level gets expensive An expression language with the usual arithmetic, comparison and logical operators has ten to twenty precedence levels. The textbook hand-written shape gives each level its own function: the addition level loops over `+` and `-` and calls the multiplication level for each of its operands, the multiplication level loops over `*` and `/` and calls the level below it, and so on down to the function that reads a literal, a name or a bracketed sub-expression. The nesting of the calls **is** the precedence — an operator can only ever capture operands produced by a tighter level. That works, and it has two costs that surface as soon as the operator set stops being fixed. - **Every addition is at least two edits.** A new level means a new function plus a change to the function above it, so that the chain still routes through the new one. - **Every operand pays for every level.** Parsing the single literal `7` descends through all fifteen or twenty functions before a token is consumed, because the only route to the operand reader is the whole chain. ## Binding power: one number per side of an operator Precedence climbing deletes the chain and replaces it with data. Each infix operator carries two numbers — a **left binding power**, saying how strongly it grips the operand on its left, and a **right binding power**, the floor it imposes on the parse of its own right operand. Higher means tighter. Gaps of ten are conventional, so a level can be inserted later without renumbering the table. | operator | left power | right power | |---|---|---| | `or` | 3 | 4 | | `and` | 5 | 6 | | `=`, `<` | 7 | 8 | | `+`, `-` | 10 | 11 | | `*`, `/` | 20 | 21 | | `^` | 30 | 30 | ## The loop One function does the parsing. It takes a **minimum binding power** — the loosest operator this call is allowed to swallow — and does three things: 1. Parse one operand: a literal, a name, or a bracketed sub-expression. 2. Look at the next token. If it is not an infix operator, or its left power is below the minimum, stop and hand back what has been built. 3. Otherwise consume the operator, call the same function recursively with that operator's **right** power to build its right operand, combine the two into a node, and go round again. The recursion carries the context that the call chain used to carry. The minimum is not a counter and not a depth limit: it is a promise to the caller that this call will not take an operator the caller wanted for itself. ## A trace Parsing `1 + 2 * 3 - 4` with the table above, starting at a floor of 0: 1. Parse `1`. The next token `+` has left power 10, which clears the floor 0, so consume it. 2. Recurse with the right power 11. That call parses `2`, sees `*` at left power 20, which clears 11, consumes it and recurses with 21. 3. The innermost call parses `3`, then sees `-` at left power 10, below its floor of 21, so it stops and returns `3`. 4. The middle call builds `2 * 3`, then sees `-` at 10, below its own floor of 11, so it stops and returns `2 * 3`. 5. The outer call builds `1 + (2 * 3)`, sees `-` at 10 still clearing its floor of 0, consumes it and recurses with 11 to get `4`. The result is `((1 + (2 * 3)) - 4)`. No function in the parser mentions `*` by name, and no level of the language has a function of its own. ## What the flat shape buys - **Adding an operator is a row**, not a function and not an edit to an existing code path. In a tool whose users keep asking for one more operator — the formula evaluator behind a report's calculated columns is the standard case — that is the whole point. - **Parsing an operand costs one call**, not one per level, because the descent is gone. - **The precedence data can be built at run time**, since it is a table rather than the shape of the code; a layered rule set cannot offer that without regenerating the parser. - **The same loop accommodates the other fixities**: an operator with no left operand is consumed by the operand step, and one with no right operand is a wrap-and-continue branch inside the loop. The price is that precedence is no longer legible as the shape of the parser. It lives in numbers, which have to be documented deliberately rather than read off the code.

What does the parser do when the next token is not an infix operator at all?
It breaks out of the loop and returns the node it has built, leaving the token unconsumed. Whether that token is an error or a legitimate terminator is the caller's business, which is what lets the same loop serve an expression that ends at a closing bracket, at a comma in an argument list, or at end of input.
Why must the right-operand recursion be given a power derived from the operator rather than zero?
A floor of zero refuses nothing, so the sub-parse would absorb every remaining operator and the whole expression would come out nested to the right regardless of precedence. The operator's right power is exactly what stops the sub-parse at the first operator that binds too loosely to belong inside it.
Does the loop ever recurse for the left operand?
No. The left operand is already in hand when the loop looks at an operator — it was produced by the operand step or by a previous turn of the loop. Only the right operand needs a recursive call, which is why left-nested trees are built iteratively and right-nested ones through the recursion.

Binding power is the strength of the glue on each side of an operator. The operand between two operators goes to whichever one is glued to it more strongly, and a tie is broken by a rule fixed in advance.

saying these in an interview costs you the question

Thinks each precedence level still needs a parse function of its own
Says the loop recurses on the left operand as well as the right
Treats binding power as an operand count rather than grip strength
Claims adding an operator means editing the loop itself
Believes the minimum binding power limits recursion depth

In precedence climbing, how does one minimum-binding-power loop parse an expression that a layered grammar would need a rule per level for?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why a rule per precedence level gets expensive

Binding power: one number per side of an operator

The loop

A trace

What the flat shape buys

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

Why a rule per precedence level gets expensive

Binding power: one number per side of an operator

The loop

A trace

What the flat shape buys

answer

go deeper