Give every operator a binding power and one recursive routine parses the whole expression — no grammar, no precedence table between token pairs. Descending into the right side of +, it raises a threshold so a following * can still grab its operands but a following + cannot. That threshold is precedence. Extensible, table-free, and short enough to hold in your head.
THE TECHNIQUE one loop, a minimum binding power
Parse left to right with a threshold min_bp: take the left value, then keep swallowing operators to the right while they bind tighter than the threshold, recursing into each right operand with the operator’s own binding power as the new threshold. Below: 1 + 2 * 3 with PLUS lbp=10, STAR lbp=20. Watch the moment * (20) clears the ‘+’ threshold (10) and grabs 2 and 3 first. live demo
HISTORY & CREDIT 1973, not the revival
“Crockford invented it” — no; he invented revived it (Beautiful Code, 2007, JSLint). The names nud, led, binding power are Pratt’s, 1973. cited
1960/61 · Samelson-Bauer operator stack; Dijkstra’s shunting-yard (1961) — the same precedence problem, an iterative stack shape. 1963 · Robert Floyd — operator-precedence grammars: bottom-up, table-driven on precedence relations between token pairs. The named predecessor Pratt improves on — not restates. 1973 · Vaughan Pratt (MIT), “Top Down Operator Precedence” (POPL, pp. 41–51): binding power on each token + a nud/led pair + one recursive routine. Top-down, table-free, extensible; deployed in CGOL (1976). 1986 / 2016 · Keith Clarke independently re-derives the infix loop (without citing Pratt), later named “precedence climbing”; Andy Chu (2016) shows it is the binary-infix special case of Pratt’s more general nud/led scheme.
Left recursion is the easy case here — precedence rides the tokens, so left-associative infix is natural, not a defect. Pratt, 1973
RECOMMEND FOR I-13 array-return threads (value, position)
A parser must return two things — a value and how far it got — and I-13 functions return one value; but an array is one value, so -> [value, pos] threads the cursor. The precedence lands exactly:
$ i13 run pratt.i13 # tokens [1, +, 2, *, 3] (PLUS lbp 10, STAR lbp 20)
parse(min_bp=0): STAR's 20 clears the '+' threshold 10 -> (* 2 3) groups first
value = 7 # tree (+ 1 (* 2 3)); a precedence-blind left-fold gives 9
Recommend:nothing new — tokens are an f64 array (operators as sentinel tags, PLUS=−1, STAR=−2, END=−9); binding power is a compare; the recursive routine returns [value, pos] (a real 2-element array return, verified working), threading the cursor with no mutable state (verified 7, the precedence-correct answer, not 9). Note: it opens the parser family for the corpus — the same [value, pos] trick carries recursive descent (128) and packrat (129); and it resonates with the 8/19 benchmark, whose P1-002 target is exactly “expression precedence and associativity.”