skip to content

Precedence Climbing

14 roadmaps5 questions

Parsing expressions without a rule layer per precedence level: give each operator a binding power and recurse while the next one binds tighter. A staple of hand-written parser interviews.

part ofComputer science fundamentalsoverview, primer and where to startread it →
on this pageshow

explore

questions

5

In a precedence-climbing parser, what makes an infix operator left-associative rather than right-associative?

level: middleimportance: must knowfreq 52%

answer

  1. two powers, one per side
  2. ties decide the nesting direction
  3. one side carries a plus one
  4. which operator keeps the middle operand?
  5. check it with 8 - 3 - 2

basics

~20 s

The power handed to the right-operand recursion decides it: recursing with the operator's power plus one makes it left-associative, because an equally binding operator is then refused; recursing with the same power makes it right-associative.

solid answer

~40 s

Each infix operator carries a left binding power and a right binding power, and the loop only absorbs an operator whose left power is at least the current floor. For a **left-associative** operator the right power is the left power **plus one**, so when the right-operand recursion meets an equally binding operator it is below the floor, the recursion returns, and the left node closes first — `a - b - c` becomes `(a - b) - c`. For a **right-associative** operator the two powers are equal, so an equal operator clears the floor and is pulled inside the right operand — `a ^ b ^ c` becomes `a ^ (b ^ c)`. Getting this wrong never produces a parse error; it silently changes the value of any chain of a non-associative operator.

go deeper

for a junior

Know that a - b - c means (a - b) - c and that some operators group the other way, and that a parser has to be told which, rather than working it out.

for a middle

Explain the plus-one rule and trace it: show the recursion refusing an equally binding operator, and name a three-operand expression whose value proves which shape was built.

for a senior

Treat a mis-set power as a silent numeric defect rather than a crash, and say what regression evidence would expose it across a corpus of stored expressions.

for a principal

Decide the associativity a language exposes, not just how it is encoded: an operator users read left to right should group that way, and any deviation is a documentation obligation.

## Associativity is a parsing decision, not an arithmetic fact Precedence decides which of two **different** operators captures a contested operand. Associativity decides which of two **equal** operators captures the operand between them. In `8 - 3 - 2` both minus signs carry the same power and the operand `3` is contested: the left minus wants it as its right operand, the right minus wants it as its left operand. Whoever wins determines whether the parser builds `(8 - 3) - 2` or `8 - (3 - 2)` — 3 or 7. In a layered parser the loop inside one level settles this: the level consumes operators from left to right and folds each new one onto the node it already has. Precedence climbing has no per-level loop, so the decision has to live in the numbers. ## Two powers per operator, differing by at most one Every infix operator carries a **left binding power** (how strongly it grips the operand to its left) and a **right binding power** (the floor it imposes on the recursion that builds its right operand). The rule is short: - **Left-associative**: right power = left power **plus one**. - **Right-associative**: right power = left power. The loop's only test is whether the next operator's left power is at least the current floor. That single comparison is where the plus one does its work. ## Tracing the left-associative case With `-` at left power 10 and right power 11, parsing `8 - 3 - 2` from a floor of 0: 1. Parse `8`. The first `-` has left power 10, which clears the floor 0, so consume it. 2. Recurse with the **right** power, 11. That call parses `3`, then sees the second `-` at left power 10. Ten is below eleven, so the call refuses it and returns `3` alone. 3. Back in the outer call, build `8 - 3`. The second `-` at 10 still clears the outer floor of 0, so consume it and recurse for `2`. The result is `(8 - 3) - 2`, which evaluates to 3. The plus one is exactly the statement *an operator of equal strength on my right is not mine to take*. ## Tracing the right-associative case With `^` at left power 30 and right power 30, parsing `a ^ b ^ c`: 1. Parse `a`, consume the first `^`, recurse with a floor of 30. 2. That call parses `b`, sees the second `^` at left power 30, and 30 does clear a floor of 30, so it consumes the operator and recurses again for `c`, building `b ^ c`. 3. The outer call receives `b ^ c` as its right operand. The result is `a ^ (b ^ c)`. | operator family | left power | right power | shape produced | |---|---|---|---| | `+`, `-`, `*`, `/` | L | L + 1 | left-nested | | `^` | L | L | right-nested | | assignment-style | L | L | right-nested | | comparison | L | L + 1 | left-nested | ## Why this is a silent bug class A wrong associativity produces no parse error. The input is accepted and only the tree differs, so the defect stays invisible until an operator that is not mathematically associative appears at least three operands wide: - `8 - 3 - 2` is 3 left-nested and 7 right-nested. - `100 / 10 / 2` is 5 left-nested and 20 right-nested. - Over exact integers, addition and multiplication agree under both shapes, which is why a test suite built on `1 + 2 + 3` will never catch it. Floating-point addition is not associative either, because rounding is applied per operation, so even a sum can drift in its last bits. The test worth writing is therefore a chain of at least three operands joined by a non-associative operator, with the expected value worked out by hand rather than taken from the parser under test. ## Practical consequences for the table - **Leave a gap of ten between levels.** The plus one consumes one unit, so consecutive numbering leaves no room to insert a level between two existing ones later. - **Avoid giving two operators the same left power with different associativity conventions.** The loop cannot tell them apart, so a mixed chain nests according to whichever right power was consulted first, which makes the shape depend on the order the operators appear in. - **Associativity is about tree shape, not about the kinds of value flowing through.** An operator whose two operands are of different kinds still follows the same rule. ## The direction to remember Both directions fall out of one comparison, so it is worth fixing which is which: **plus one on the right power refuses an equal operator, refusing it closes the left node first, and closing the left node first is left associativity.** If you have to produce it live, trace two operators over three operands rather than trying to recall the mapping.

  • How would you catch a mis-set associativity in testing?
    Exercise a chain of at least three operands joined by an operator that is not mathematically associative — subtraction, division, exponentiation — and assert a value computed by hand. `8 - 3 - 2` is 3 under the correct left-nested shape and 7 under the wrong one. Chains of addition or multiplication over exact integers agree under both shapes and prove nothing.
  • Does associativity still matter for an operator that is mathematically associative?
    Often yes. The tree shape differs even when the arithmetic result does not, so evaluation order, short-circuiting and error attribution differ. Floating-point addition is the clearest case: rounding happens per operation, so a left-nested and a right-nested sum of the same operands can disagree in their last bits.
  • What happens if an operator's right power is set two above its left power instead of one?
    For associativity, nothing: the test is only whether an equal operator clears the floor, and it fails either way, so the operator is still left-associative. The risk is collision — a right power two units up may land on the next declared level, so a genuinely tighter operator is refused where it should have been absorbed.

saying these in an interview costs you the question

  • Says associativity is decided by the left binding power alone
  • Thinks equal left and right powers give left-associative nesting
  • Claims a wrong associativity shows up as a parse error
  • Believes associativity only matters for the exponent operator
  • Assumes a chain of additions can prove associativity is right
open as a page

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

level: middleimportance: must knowfreq 62%

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.

open as a page

In a precedence-climbing parser, why does a prefix operator need its own binding power, separate from the infix operator spelled the same way?

level: seniorimportance: should knowfreq 40%

basics

~20 s

A prefix operator has no left operand, so it carries a single power of its own, used as the floor when parsing its argument. That number decides how far right the argument reaches, and it is usually higher than the infix power of the same symbol.

open as a page

When is a precedence-climbing binding-power table worth adopting for a formula evaluator whose users request a new operator every quarter, and what does it cost?

level: principalimportance: should knowfreq 33%

basics

~20 s

Adopt it when the operator set keeps growing or precedence must be data: each addition becomes one table row instead of a new rule layer and an edit to its neighbour. The cost is that precedence stops being readable from the code and becomes numbers you must document and regression-test.

open as a page

In precedence climbing, why is the sub-expression inside brackets parsed with a minimum binding power of zero?

level: seniorimportance: nice to knowfreq 24%

basics

~20 s

Brackets cancel the surrounding grip, so the inner parse starts from the loosest possible floor and can absorb every operator up to the closing bracket. Passing the ambient floor instead stops the inner parse early and reports a spurious error at the bracket.

open as a page