Tokens, a tree, a number. Move one line in the parser and 2-3-4 becomes 3 instead of −5 — but 324 of 432 expressions come out identical, and the same edit is the fix for ^. A study guide for interp.py.
Python 3.15.0a8 (main, Apr 14 2026, 14:20:41) [Clang 22.1.3], stdlib only.
cd tiny-interpreter
python3 demo.py # the aha (§6) -- about 3s
python3 demo.py --pipeline # just the one-expression walkthrough
python3 test_interp.py # 13 tests, 54 assertions, ~3sThis toy is the three classic stages, at their smallest: a tokenizer that turns characters into tokens, a recursive-descent parser that turns tokens into a tree, and a tree-walk evaluator that turns the tree into a number.
There is only one parser. That is the thing to hold on to. Parser reads a table of precedence levels and, for each level, a fold direction, so the left-folding and right-folding versions are the same object with a different argument. The tokenizer is shared, the node classes are shared, the evaluator is shared. When two runs disagree, there is exactly one place the disagreement can have come from.
2-3-4 evaluates to 3 instead of −5 — but 324 of 432 three-operand expressions come out identical. The bug is real, total, and almost invisible.
By the end you should be able to:
2 ** 3 ** 2 is 512 in Python and JavaScript, in terms of the same line that produced the bug (§6.9).The space, up front, because the whole page rests on it. Every percentage below is over the same enumerated set: a op b op c where a, b, c ∈ {2,3,4} and op ∈ {+, -, *, /} — no parentheses, no prefix minus. That is 33 × 42 = 432 expressions. §6.4 stretches it to four and five operands; §6.6 shrinks the operator set until the bug becomes impossible.
A tokenizer hands you a flat list. 2 - 3 - 4 is five tokens in a row, and a list has no shape. But arithmetic is a tree: something has to be computed first. Nothing in the token stream says which.
So every language invents two conventions and writes them into its parser:
1 + 2 * 3: does the 2 belong to the + or the *?2 - 3 - 4: does the 3 belong to the first - or the second?Both are pure convention. Neither is discoverable from the tokens, and neither is checked by anything downstream — the evaluator will happily walk whichever tree it is handed. Wikipedia's Associative property article puts the convention plainly: subtraction and division are non-associative, so "mathematical convention treats them as left-associative by default", x − y − z = (x − y) − z.
The competing goals that make more than one design defensible:
expr, term, factor) reads exactly like the BNF in a language reference, and adding a level means adding a function and re-wiring its two neighbours. A table of levels adds a row. §7.1 measures how much this choice costs — the answer is nothing behaviourally, and quite a lot in how visible a mistake is.Fraction, which is slow and is not what real languages do — but see §6.10, where floating point turns out to break the very property the boundary section relies on.| Concept | Where it's used in the toy | One link |
|---|---|---|
| Tokenizer / lexer | tokenize, lines 38–61 — one pass, no lookahead, no regex | Wikipedia: Lexical analysis |
| Recursive descent ⭐ | Parser.binary, lines 152–166 — one function call per precedence level, and the call stack is the grammar | Wikipedia: Recursive descent parser |
| Operator precedence | the index into LEVELS, line 111. Level 0 is loosest; tighter walks one row down | Wikipedia: Order of operations |
| Associativity ⭐ | the assoc tuple, lines 113–115, consumed at lines 155–164. This is the whole page | Wikipedia: Operator associativity |
| Precedence climbing | the shape of binary(level): the same algorithm as the classic one, with the level passed down instead of a minimum-precedence integer | Eli Bendersky: Parsing expressions by precedence climbing |
| Abstract syntax tree | Num / Neg / Bin, lines 66–104. Three node kinds, and Bin.__repr__ prints the grouping that is the toy's whole subject | Wikipedia: Abstract syntax tree |
| Tree-walk interpreter | evaluate, lines 190–216 — post-order, and notably free of any precedence logic | Crafting Interpreters: Evaluating Expressions |
| Exact rational arithmetic | Fraction everywhere; §6.10 shows what floats would have done to the boundary claim | Python: fractions |
The two starred rows carry the result. Recursive descent is why there is a single line to point at — the grammar is literally the call graph, so a grammar property like associativity has to be encoded as a choice of which function to call. Associativity is the property being encoded, and the only reason the bug is subtle is that most operators do not care.
Three stages, and only the middle one has an opinion:
The fold itself, in one picture. A chain a - b - c - d arrives as four operands and three operators. The parser must bracket them, and there are only two ways to do it consistently:
Which one you get is decided by what you put on the right-hand side of that one assignment: one operand (and the loop folds), or the whole rest of the chain (and the recursion folds).
def tokenize(source):
"""`2-3-4` -> [('num', 2), ('-', '-'), ('num', 3), ('-', '-'), ('num', 4), ('eof', None)]
Symbols carry themselves as their kind, so the parser can test a token
directly against an entry in `LEVELS` without a second lookup table. The
trailing `eof` makes `peek` total: no bounds check anywhere in the parser.
"""
tokens, i = [], 0
while i < len(source):
char = source[i]
if char.isspace():
i += 1
elif char.isdigit():
start = i
while i < len(source) and source[i].isdigit():
i += 1
tokens.append(("num", int(source[start:i])))
elif char in SYMBOLS:
tokens.append((char, char))
i += 1
else:
raise SyntaxError(f"stray {char!r} at offset {i}")
tokens.append(("eof", None))
return tokensThe docstring names the two shortcuts; what it does not say is what each one buys downstream.
A symbol is its own kind. ("-", "-") rather than ("op", "-"). That means self.peek() in LEVELS[level] is a direct membership test against the precedence table, with no second lookup mapping token kinds to operator strings. The precedence table becomes the only place operators are named.
The eof sentinel. Without it every peek needs a bounds check, and a bounds check in a recursive-descent parser is the kind of thing that gets forgotten in one branch out of five. With it, peek is total: there is always a token, it is just sometimes the one that matches nothing.
The tokenizer has no opinion about grouping. Feed it 2-3-4 and it hands back the same five tokens no matter what the parser is about to do with them — which is exactly why §6.1's transcript can print one token line above two different trees.
LEVELS = (("+", "-"), ("*", "/"), ("^",))
CORRECT = ("left", "left", "right") # what every real language does
FLIPPED = ("right", "right", "right") # the bug, in both arithmetic levels
ADD_FLIPPED = ("right", "left", "right") # the bug in `expr()` onlyLoosest first, so the index is the precedence: binary(0) parses a whole expression, binary(2) parses only a power chain. This is the entire precedence mechanism. Nothing else in the file mentions precedence at all.
Putting assoc beside it as a parallel tuple is the load-bearing design decision of the toy. Associativity is usually spelled as a shape — which function you recurse into — which makes it invisible, unnameable and untestable. Hoisting it into data makes it a value you can pass, print, and sweep over. CORRECT and FLIPPED are the two arguments the demo runs; ADD_FLIPPED is §6.3's third.
Note CORRECT is not ("left", "left", "left"). Level 2 asks for a right fold on purpose — §6.9.
def tighter(self, level):
"""Whatever binds one notch tighter than `level`. Below the last infix
level there is no next table row, so control drops out to prefixes.
"""
if level + 1 < len(LEVELS):
return self.binary(level + 1)
return self.unary()
def binary(self, level):
node = self.tighter(level)
while self.peek() in LEVELS[level]:
op = self.take()[0]
if self.assoc[level] == "right":
# Re-enter the SAME level: this call consumes the entire rest
# of the chain, so the `while` never gets a second turn and
# the tree leans right.
rhs = self.binary(level)
else:
# One operand only. The loop does the folding, and each turn
# buries the tree built so far one node deeper on the left.
rhs = self.tighter(level)
node = Bin(op, node, rhs)
return nodeself.tighter(level) against self.binary(level). One method name.
The reason this is worth a whole toy is that neither form looks wrong. rhs = self.binary(level) is not a typo and not a slip; it is the standard, documented way to implement a right-associative operator. Crockford's Top Down Operator Precedence does it by calling expression(bp - 1) instead of expression(bp); precedence climbing does it by not adding one to min_precedence before recursing. Same idea, three spellings. Someone adding ^ to this parser has to write self.binary(level) somewhere, and the mistake is applying it one row too far up the table.
Two things follow, and both were checked by running them rather than by reading.
The while is dead code under a right fold. If the recursive call has already eaten the rest of the chain, the loop condition is false when it returns. Replacing while with if therefore costs the right fold nothing — and breaks the left fold in half the space (verify_cf.py, CF2):
216 = the 8 mixed-precedence pairs × 27 operand triples. The other 8 pairs put two operators at the same level, one if consumes one of them, and parse finds a trailing token. Note the left fold never quietly changes a value — it raises. The loop is not an optimisation; it is where left-folding lives.
The loop is where the left spine is built. node = Bin(op, node, rhs) re-wraps the accumulated tree as the left child of the new node, so each turn buries everything built so far one level deeper. The right fold never executes that line more than once per call.
def unary(self):
if self.peek() == "-":
self.take()
# Not `self.unary()`: prefix minus binds LOOSER than `^`, so
# `-2^2` is -(2^2) = -4, matching Python's `-2**2`.
return Neg(self.binary(len(LEVELS) - 1))
return self.atom()Prefix minus sits below the last infix level, so -2*3 is (-2) * 3. But it must bind looser than ^, because -2^2 means -(2^2). Python's language reference states the rule directly — "The power operator binds more tightly than unary operators on its left; it binds less tightly than unary operators on its right" — and gives the same example: -1**2 results in -1.
Write the obvious Neg(self.unary()) instead and the toy disagrees with Python on two of three test expressions (verify_cf.py, CF4):
^ and no prefix minus, so a second, equally real grouping bug scores 432 of 432 against it. A number like "324 of 432 agree" is only ever a statement about the space you enumerated.
JavaScript's designers refused to pick a side here at all — MDN notes that a unary operator "immediately before the base number" is a SyntaxError, so -2 ** 2 does not compile and you must write -(2 ** 2) or (-2) ** 2.
def evaluate(node):
"""Post-order walk. Note what is NOT here: no precedence, no
associativity, no operator table. By the time a tree exists, every
grouping question has already been answered by the parser -- which is why
a one-line parser change can move an answer without the evaluator
changing at all.
"""
if isinstance(node, Num):
return node.value
if isinstance(node, Neg):
return -evaluate(node.operand)
left, right = evaluate(node.left), evaluate(node.right)
if node.op == "+":
return left + right
if node.op == "-":
return left - right
if node.op == "*":
return left * right
if node.op == "/":
if right == 0:
raise ZeroDivisionError("division by zero")
return left / right
if node.op == "^":
if right.denominator != 1:
raise ValueError("fractional exponent would leave the rationals")
return left ** right
raise ValueError(f"unknown operator {node.op!r}")The docstring makes the claim; the shape of the code is the evidence. evaluate dispatches on node.op — a string it reads off the tree — and never once asks what that operator's precedence or associativity is, because there is nowhere left to put the question. Grouping is not data the evaluator consults. It is the tree, and the tree already happened.
That asymmetry is the reason the bug is so quiet. An evaluator can be exhaustively unit-tested — every operator, division by zero, the fractional-exponent guard — and pass all of it while the parser hands it the wrong tree. The tests are not weak; they are aimed at the wrong stage.
This is why the toy can make its claim cleanly. test_evaluator_is_not_where_grouping_lives hands the same function two trees built from the same token list and gets two different numbers. Nothing was configured, patched or monkeyed with; the parser simply handed over a different shape.
python3 demo.py, whole output reproduced across the subsections below.
The arithmetic: (2 − 3) − 4 = −1 − 4 = −5. 2 − (3 − 4) = 2 − (−1) = 3. The gap is 8, which is 2 × 4 — flipping the fold flips the sign of the last operand's contribution, so the answer moves by twice it. That is the general shape of the error for a three-term subtraction chain, and it is why the witnesses in §6.2 come in ± pairs.
Where 432 comes from. Three operand slots from a 3-element set and two operator slots from a 4-element set: 33 × 42 = 27 × 16 = 432.
Where 108 comes from — and it is four numbers, not one. Go through the 16 operator pairs by hand. Write the left fold as (a ⊕ b) ⊗ c and the right fold as a ⊕ (b ⊗ c).
Mixed precedence — ⊕ additive and ⊗ multiplicative, or the reverse. There is only one operator at each level, so binary never loops at either level and both folds build the identical tree. 8 pairs, 0 differences, by construction rather than by arithmetic.
Same level — the remaining 8 pairs. Take the additive four and multiply out both sides:
| pair | left fold | right fold | equal? |
|---|---|---|---|
++ | (a+b)+c | a+(b+c) = a+b+c | always |
+- | (a+b)−c | a+(b−c) = a+b−c | always |
-+ | (a−b)+c = a−b+c | a−(b+c) = a−b−c | iff c = 0 |
-- | (a−b)−c = a−b−c | a−(b−c) = a−b+c | iff c = 0 |
The pattern: the first operator decides. If ⊕ is +, the right fold's inner result is simply added, and the brackets do nothing. If ⊕ is −, the right fold negates the whole inner result, which flips the sign of c's contribution — so the two answers differ by 2c. The multiplicative four are the identical argument with × for + and ÷ for −, and "differ by 2c" becomes "differ by a factor of c2".
So the differing pairs are exactly -+, --, /*, // — first operator non-associative, both operators at the same level — which is precisely the list the demo prints. 4 pairs × 27 operand triples = 108, and 432 − 108 = 324 agree.
The "iff c = 0" is a real condition, not a hedge. The operand set {2,3,4} has no zero, which is why all four pairs score 27 of 27. Admit 0 and they drop (verify_cf.py, CF6):
48 of 64 = 3/4, and 64 = 43. The missing 16 are the 4 × 4 combinations with c = 0. Every differing case has a nonzero third operand, as the derivation requires.
ADD_FLIPPED flips only the additive level and scores 378 of 432 (87.50%) — 54 differences, which is 2 pairs (-+, --) × 27. The multiplicative pairs /* and // are folded correctly, so they vanish from the culprit list.
This matters because it is the number a hand-written parser produces. In the textbook expr / term / factor shape, the fold direction is not a parameter; it is a call, written out once per function. Someone who right-folds expr() has changed one function and left term() correct — so the same conceptual bug is half as visible in the hand-written shape as in the table-driven one.
The two shapes are otherwise behaviourally identical. verify_cf.py's CF1 runs a hand-written expr/term/power/unary/atom parser against the shipped table-driven one over both folds:
11,244 = the 11,232 flat arithmetic cases (432 + 5,184 expressions, times two folds) plus 12 involving ^. Zero mismatches: the table is a refactor, not a different algorithm.
ADD_FLIPPED figure above. The headline moved to 324 of 432 when the toy shipped with the fold as an explicit per-level parameter, which flips both arithmetic levels at once. Both numbers are real and both are printed by demo.py.
5,184 = 34 × 43 = 81 × 64. 62,208 = 35 × 44 = 243 × 256.
The agreement rate is not a constant, and this is the practically useful half of the result. Each extra operator is another chance for two same-level operators to land next to each other with a non-associative one first. At three operands the flipped parser is right 75% of the time; at five it is right a third of the time. A bug's invisibility is a property of your inputs, not of the bug. If your test expressions are short — and hand-written test expressions are always short — you are sampling from the most forgiving end of the distribution.
Four of eighteen. Look at what the fourteen have in common: they are testing precedence (1+2*3, 2*3+4, 4+2*3), parentheses ((1+2)*3, 2*(3+4), (2+3)*(4-1)), each operator once (1+2, 2*3, 10-4, 8/2), or associative chains (1+2+3+4, 2*3*4). Every one of those is a test someone writes deliberately. None of them can see this bug.
The four that catch it are the accidents: two - in a row, two / in a row, a / followed by a *, a - in the middle of a + chain. Nobody writes 1+2-3+4 as a test of associativity; they write it as "a longer sum".
Contrast the neighbouring knob. Swap the two precedence rows and re-run the same 432 (verify_cf.py, CF3):
Precedence: half the space, plus nine crashes that were not crashes before. Associativity: a quarter of the space, silently. The first is caught by 1+2*3, which is the second test anyone writes. The second is caught by nothing on the list above except by luck.
This is the row to take away. Restrict the operators to + and * and the flipped parser is correct on all 23,328 six-operand expressions — 36 × 25 = 729 × 32. Not "almost all". All, at every length, forever. + and * are associative, so both trees compute the same number and the parser's opinion is unobservable. If every operator in your language is associative, this entire toy is about nothing, and that is the honest boundary: a language of +, *, min, max, and, or, string concatenation and set union has no associativity bugs to find.
The mirror row: {-} and {/} alone agree on zero expressions at any length, because every adjacent pair is same-level and non-associative-first.
The 12.5% row is worth a second look. {-,/} at four operands is 648 = 34 × 23, and 81 = 34 — exactly one of the eight operator sequences survives. CF8 asks which:
Only /-/. Note that -/- — equally "alternating" — does not survive: its two - are both at the additive level and both consumed by one call to binary(0), which folds. In /-/ the lone - splits the two / into separate multiplicative subexpressions, so no single call ever sees two of its own operators, and no fold ever happens.
Explicit grouping is the one thing the fold cannot override, because atom re-enters at binary(0) and returns a finished subtree that no enclosing level can restructure. This is the practical defence, and it is why the convention survives in the wild: people who are unsure parenthesise, and their code is then immune to the whole class.
-2-3 has one binary operator, so there is nothing to fold and no disagreement is possible. -2*3/4 has two, but at the same level with * first — associative-first, so it agrees, exactly as §6.2's table predicts. The three that differ differ because of their binary chain (- -, / /, - -), not because of the prefix.
2-3--4 is the nicest of the six: correct −5 and flipped 3 are the two values from 2-3-4 in §6.1, swapped. (2−3)−(−4) = −1+4 = 3 and 2−(3−(−4)) = 2−7 = −5.
This is the point the rest of the page exists to set up.
rhs = self.binary(level) on level 0 is the bug that produced §6.1's wrong −5→3. The identical expression, on level 2, is what makes ^ correct. (23)2 = 82 = 64; 2(32) = 29 = 512. Python prints 512 for 2 ** 3 ** 2; so does JavaScript, whose MDN reference spells out the same three lines this transcript does — 2 ** 3 ** 2 is 512, (2 ** 3) ** 2 is 64.
Wikipedia's Operator associativity article notes there is "no general agreement" on exponentiation's associativity across languages, and §5.4's neighbouring question is contested too. On the machine these transcripts came from, bash -c 'echo $(( -2 ** 2 ))' prints 4; Python's -2 ** 2 is −4; JavaScript refuses to read it at all. Three languages, three answers, one expression — which is exactly what makes it a convention rather than a fact.
+ is associative in the rationals§6.6's headline row says the bug is impossible when the operators are + and *. That claim depends on the toy using Fraction. In floating point it is false (verify_cf.py, CF5):
Six values, 63 = 216 triples, 48 of them non-associative under +. Wikipedia states it plainly: "addition and multiplication of floating point numbers are not associative, as different rounding errors may be introduced when dissimilar-sized values are joined in a different order."
So the toy's exactness is not fastidiousness — it is what makes the 100.00%-agree row mean something. Had the evaluator used floats, that row would have been measuring the FPU's rounding behaviour on a particular operand set, and "the bug cannot exist here" would have been false in a way that had nothing to do with parsers. It is also why compilers do not reassociate floating-point arithmetic unless you pass a flag that says you do not mind.
The textbook shape is expr() calls term() calls factor(). It reads like BNF and it is what most tutorials teach. It lost here for one reason: it cannot express the fold direction as data. In that shape, right-folding expr means editing expr, so a demo that runs both parsers would need two copies of the parser — and then the reader is entitled to wonder what else differs between the copies. The whole argument rests on there being one parser.
The cost of the table is that the mistake is worse when it happens: one edit hits every level, which is why the headline is 324 and not 378 (§6.3). The cost of the hand-written shape is that the bug is quieter. Neither shape is safer; they fail differently. And they are otherwise indistinguishable — 11,244 checked pairs, zero mismatches.
Pratt parsing / TDOP attaches a binding power and a parse method to each token, which is strictly more powerful: it handles prefix, infix and postfix uniformly, and extends to ?:, function calls and indexing without new machinery. It is also the shape where associativity is least visible — buried in bp versus bp - 1 inside a token's handler.
Precedence climbing over an explicit table puts the same decision in a place you can point at, which is the only reason the toy exists. A Pratt version would be a better parser and a worse commentary.
Dijkstra's shunting-yard would produce the same trees with an explicit operator stack and no recursion. It lost because associativity there is spelled as >= versus > in a stack-popping comparison — a genuinely one-character difference, which sounds ideal, but it is a character inside a loop condition whose meaning takes a paragraph to explain. tighter versus binary is a difference a reader can see. (The sibling toy regex-engine uses shunting-yard, where the same >= appears with a comment noting the operators are left-associative.)
binary could return a number instead of a Bin, which would delete the three node classes (lines 66–104) and the evaluator (lines 190–216) — 66 of the file's 224 lines. It would also delete the demo, because the entire aha is that two shapes produce two numbers, and a parser that returns numbers has no shape to show. §6.1's side-by-side trees are the toy.
Fraction, not float or intint would make / lossy and 2/3/4 uninteresting. float would make "these two parsers agree" mean "these two parsers agree to within rounding", which is a different and much weaker claim — see §6.10, where floats break +'s associativity outright. Fraction costs speed the toy does not need and buys exact equality, which is the comparison every number on this page depends on.
Neg as its own node, not Bin("-", Num(0), x)Desugaring prefix minus to 0 - x would remove a class. It would also make §6.8 unprovable: the claim there is that prefix minus contributes no associativity difference of its own, and if prefix minus were a subtraction node it would be a same-level - and would join the chain. Keeping it distinct is what lets the demo print ((-2) - 3) and show the prefix sitting outside the fold.
4^(1/2) raises rather than returning 2.0, because leaving the rationals would smuggle a float back in and undermine §6.10. This is the toy defending its own measuring instrument.
No variables, no statements, no functions. A real interpreter's parser has a statement level above the expression level, and the tree has declarations, scopes and control flow. Everything on this page is about one expression, so the environment — the thing that makes an interpreter an interpreter — is absent entirely. Add variables and the next question is evaluation order, which is a different convention from associativity and equally invisible: f() - g() - h() fixes the grouping but not which of the three runs first.
No error recovery. The first SyntaxError ends everything. A production parser must report several errors per run, which means it needs to invent a plausible tree for the broken part and keep going — panic-mode recovery, synchronising on statement boundaries. That machinery is usually larger than the parser it protects.
No source positions. Tokens carry no offsets except in the tokenizer's own "stray character" message, so the toy cannot say where a problem is. Every real front end threads spans through every node, because an error message without a location is worthless and because the same spans drive the debugger.
Recursion depth is the real limit, and the fold decides who hits it (verify_cf.py, CF7):
Read the 1,200 row carefully. Under the left fold the parser is fine — its loop is flat — and the evaluator blows the stack, because the tree is a 1,200-deep left spine. Under the right fold the parser blows up first and there is no tree to evaluate. Same depth, different component, entirely because of the fold. Real parsers cap nesting depth explicitly rather than letting the stack decide: CPython refuses eval("("*2000 + "1" + ")"*2000) with SyntaxError: too many nested parentheses, having accepted the same expression at 200. The alternative is converting the walk to an explicit stack. A 1,200-term expression is not hypothetical: generated SQL IN lists and machine-written config routinely look like this.
One namespace of operators, hard-coded. Real languages let you define operators (Haskell's infixl 6 <+>, Scala's precedence-by-first-character rule), which means precedence and associativity become runtime data the parser must read before it can parse — the exact table this toy hard-codes, built from declarations. That is also where associativity bugs stop being transcription errors and become genuine ambiguities: two libraries can declare incompatible fixities for the same symbol.
Fraction is not what anybody ships. Real evaluators use machine integers and IEEE doubles, and inherit §6.10's non-associativity as a permanent property. This is why -ffast-math is controversial and why compilers will not reassociate floating-point sums by default.
The toy uses operands {2,3,4} and gets "27 of 27" for each of the four culprit pairs. What would the four counts become with operand set {0,1,2}, and why is the answer not the same for all four?
Measured (verify_cf.py, CF9): -+ and -- score 18 of 27, /* and // score 4 of 27 with 15 of 27 raising ZeroDivisionError.
The additive half follows straight from §6.2: the condition is c ≠ 0, and 9 of the 27 triples have c = 0, leaving 18.
The multiplicative half is not symmetric with it, for two reasons. The neutral element of × is 1, not 0, so c = 1 also makes the folds agree — (a/b)*1 and a/(b*1). And zero is not merely neutral for division, it is fatal: a/b*c needs b ≠ 0 on the left and b*c ≠ 0 on the right, so the 9 triples with b = 0 plus the 9 with c = 0, less the 3 counted twice, are 15 crashes. Of the 12 survivors, c = 1 kills 6 and a = 0 kills 2 more, leaving 4.
That is the real lesson of the question. "27 of 27" is a property of the operand set — {2,3,4} was chosen with no 0 and no 1 precisely so that every culprit pair scores its maximum and division stays total. A different operand set is a different measuring instrument, and can make the same bug look four times rarer.
demo.py reports 8 mixed-precedence operator pairs that never differ. Would that still hold for a four-operand expression like 2+3*4-5?
No, and this is why §6.4's rate falls. The "mixed pairs never differ" argument is that each level sees at most one of its own operators, so no fold happens. With four operands there are three operator slots, and + * - puts two additive operators (+ and -) into one call to binary(0) — which loops, and therefore folds.
2+3*4-5: left fold (2 + (3*4)) - 5 = 14 - 5 = 9; right fold 2 + ((3*4) - 5) = 2 + 7 = 9. Equal here, because the first additive operator is +. Swap it: 2-3*4+5 gives left (2 - 12) + 5 = -5 and right 2 - (12 + 5) = -15. The §6.2 rule survives intact — the first operator at the level decides — it just now has more opportunities to apply.
§5.3 shows that while → if costs the right fold nothing. Does that mean the right-folding parser is simpler? What has it actually traded?
It has traded iteration for recursion, one-for-one. The left fold's loop runs k times for a k-operator chain and the stack stays flat; the right fold's loop runs once per call but calls itself k times, so the stack goes k deep. Neither does less work.
The consequence is measured in §8's CF7 table: at 1,200 operands the right fold dies in the parser with RecursionError while the left fold parses fine. The left fold then dies in evaluate instead — because a left-leaning tree is a left spine and the post-order walk is itself recursive. So the honest answer is that the recursion is conserved; the fold only chooses which component pays it.
You inherit a language whose parser you cannot read. You get to run 20 expressions. How do you find out whether - is left- or right-associative, and how would you look for the same answer about **?
One expression is enough, not 20: evaluate 2-3-4. −5 means left, 3 means right. §6.2's table is the proof that no other three-operand shape is needed — -+ and -- are the only additive witnesses, and both are single tests.
For ** you cannot use the same trick with a symmetric operand, so avoid 2**2**2 (16 either way). Use 2**3**2: 512 is right-associative, 64 is left. And test -2**2 separately: −4 means unary binds looser (Python), 4 means it binds tighter (bash), a SyntaxError means the language refused to choose (JavaScript). Three expressions, three independent conventions — which is §6.9's point, that these are per-operator facts and not one global policy.
Your team ships a parser for a config DSL with the operators +, *, min, max and || (string concatenation). A code review flags "you should have a test for associativity." What is the correct response?
That no such test can fail. All five operators are associative: min(min(a,b),c) = min(a,min(b,c)), and string concatenation is the free monoid — ("a"||"b")||"c" and "a"||("b"||"c") are the same string. §6.6's 100.00% rows for {+}, {*} and {+,*} at every length up to six operands are the same statement.
The correct response is therefore: write the test anyway if it is cheap, but know that it is a regression guard against a future operator, not a check on today's parser. The moment someone adds -, /, %, ** or a right-associative assignment or arrow (a -> b -> c), it starts being able to fail — and §6.4 says to write that test with at least four operands, because three is where the bug hides best.
The one caveat worth raising in the review: if + here means floating-point addition, associativity is only approximate (§6.10), so an exact-equality test over large and small magnitudes can fail for reasons that have nothing to do with the parser.
demo.py prints "324 of 432 agree". Name two ways that number is misleading about how likely you are to ship this bug undetected.
It is optimistic about the operators. The space gives +, -, *, / equal weight. Real expressions are not uniform: + and * dominate, which pushes the agreement rate up, so 75% understates the bug's invisibility in practice.
It is pessimistic about length. 75% is the three-operand figure — the most forgiving row in §6.4. Realistic expressions are longer, and by five operands the rate is 33.44%.
A third, from §5.4: the space contains no ^ and no prefix minus, so it scores 432 of 432 on a second, real grouping bug it simply cannot see. Every percentage on this page is a statement about an enumerated set, and the enumerated set is stated at the top for exactly that reason.
Every link below was fetched and confirmed live when this was written.
5^4^3^2, which right-associates to 5^(4^(3^2)) ≈ 6.2×10183230 and left-associates to something vastly smaller — §6.9's 2^3^2 with the stakes turned up. It also records that there is "no general agreement" on exponentiation across languages, which is the reason §6.9 has three different real-world answers for -2^2.x − y − z = (x − y) − z) and the non-associativity of floating-point addition, with a 4-bit-significand worked example. Read it as the source of both boundary conditions on this page.equality() method is §5.3's binary(level) with the level unrolled by hand: the same while (match(...)) { … expr = new Expr.Binary(expr, operator, right); } accumulation, which it explains is what "naturally produces left-associative trees". Read it for the hand-written shape §7.1 rejected, then read its right-associativity treatment of assignment for the other half.Parser.binary is a table-driven form of, and the best short account of why the associativity decision is one comparison. Its version of §5.3's line is next_min_prec = prec + 1 for left and prec for right; the article calls this "one of the coolest aspects of this algorithm". If §5.3 feels like a trick, this is the page that makes it a technique.tighter versus binary really is the standard +1, expressed as a table index instead of an integer.this.second = expression(bp) for left-associative, expression(bp - 1) for right. Worth reading to see how much more a parser can do once binding powers live on tokens — and how much harder that makes the one decision this toy is about to find.-1**2 is -1. The precedence table at the end marks ** as the one binary operator that groups right-to-left, which is CORRECT = ("left", "left", "right") in prose.**) — §6.9's transcript, in a language reference: 2 ** 3 ** 2 is 512 and (2 ** 3) ** 2 is 64, the same two numbers demo.py prints. Its unary rule is the interesting part — JavaScript makes -2 ** 2 a SyntaxError rather than choosing, noting bash reads it as 4 and Python as −4. A design decision that treats §5.4's trap as unresolvable and pushes it back to the programmer.