A dart thrown at the oldest question a parser faces: how do you know ∗ binds before + without recursion or guessing? Dijkstra’s answer — a single operator stack and a precedence rule — shunts tokens like railway cars into output-vs-siding until the expression comes out in postfix. We show it working, credit who built it, and ask what I-13 should learn. This one ends in a handshake, not a gap.
THE TECHNIQUE one stack · one precedence rule · infix → RPN
Read tokens left to right. A number goes straight to output. An operator waits on the stack — but first it evicts any operator already there of higher-or-equal precedence (left-associative), because those must apply first. Parentheses open a sub-yard. At the end, drain the stack. The output is Reverse Polish, ready to evaluate with a second tiny stack. live demo
precedence in this demo (matched to I-13’s own table): + − = 2 · ∗ / % = 3 · all left-associative · ( ) group
INPUT — tokens read left to right
OPERATOR STACK — the siding (top = left)
OUTPUT QUEUE — the RPN, in order
Watch the moment ∗ arrives on the empty siding while + waits — and the moment a lower-precedence + cannot evict the ∗ sitting on it, so ∗ reaches output first. That eviction test is operator precedence.
HISTORY & CREDIT credit where it is due
This one is refreshingly undisputed. No folk hero stole the credit here — the author named it himself, in print, with a picture of a rail yard. cited
Nov 1961 · Edsger W. Dijkstra (Mathematisch Centrum, Amsterdam) publishes it in the report “ALGOL 60 Translation” (MR 34/35), as part of building an ALGOL 60 translator for the Electrologica X1.
· He called it the “shunting-yard” algorithm himself — the operator stack is the siding a locomotive shunts cars onto to reorder a train.
· It is the classic answer to operator precedence: convert infix to postfix (RPN) in one linear pass, no grammar recursion required. lineage · postfix / Reverse Polish itself traces to Jan Łukasiewicz (Polish notation, 1920s); Dijkstra’s contribution is the conversion, not the notation.
What’s worth flagging as context, not dispute: precedence-climbing / Pratt parsing (Vaughan Pratt, 1973) is a different, recursive route to the same result. Many modern parsers — including I-13’s — use the climbing form. Same precedence semantics, different bookkeeping. context
RECOMMEND FOR I-13 a dart that credits a strength
Most darts find a wall in I-13 and prove it. This one found a door already open. Shunting-yard is a way to resolve operator precedence — and I-13’s parser already does exactly this. I read the source: src/compiler/parser.rs is a precedence-climbing parser with an explicit infix table:
// src/compiler/parser.rs :: infix_info()
Plus => (2, Add) Minus => (2, Sub) // precedence 2
Star => (3, Mul) Slash => (3, Div) // precedence 3
Percent => (3, Mod) // % slotted in at 3
// expression(min_prec): pop-or-recurse exactly when prec >= min_prec
// — the same eviction test shunting-yard runs against its stack.
That is not a coincidence resembling Dijkstra — it is the same idea in its recursive dress. I ran the live compiler to confirm the precedence actually resolves the way the table promises — proven, not asserted:
Recommend:no change needed here — this is I-13’s parser. The lesson runs the other way: the recent % (Percent → Mod) addition dropped straight into precedence level 3 next to ∗ and / — a new BinOp discriminant, zero new alphabet symbols, exactly the cheapest-fix move earlier darts kept recommending. The mod_slots = 7 run above is that addition working. When a future operator wants in, the shape is already proven: pick a precedence row, add a discriminant, keep the alphabet at 13. Tradeoff (honest): there isn’t one to pay here. Celebrating a strength costs I-13 nothing — and it names the seam future darts should reuse rather than reinvent. The one boundary to keep watching is that this table lives in the parser, outside the counted-alphabet census; growth here is measured in discriminants, and stays free of the 13-symbol budget only as long as that holds.