Skip to content

The Shunting Yard

Edit source

Turning a boolean query into something a machine can walk, in one pass over two stacks.

Part 12 of 38ofFamiliars
  1. 1Session Zero
  2. 2Rolling for a Name
  3. 3The Haunted Handler
  4. 4The Sparse Wheel
  5. 5The Fork in the Path
  6. 6The Planet as a Prefix
  7. 7The Long Division
  8. 8The Line You Usually Cancel
  9. 9Sixteen Bytes Too Far
  10. 10Packing a UUID
  11. 11Bytes You Can Type
  12. 12The Shunting Yard
  13. 13Interchangeable Parts
  14. 14One Loop Per Core
  15. 15The Seam
  16. 16Append Only
  17. 17Who Owns the Tree
  18. 18Down the Flume
  19. 19The Syscalls That Lie
  20. 20Asking the Machine
  21. 21The Earth Is Not a Ball
  22. 22Smith and Schmidt
  23. 23Many Ways to Be Similar
  24. 24Built to Disappear
  25. 25Sometimes a Mutex Is Right
  26. 26Work, Not Threads
  27. 27Before the Program Runs
  28. 28No Collisions, Ever
  29. 29The Names Enums Throw Away
  30. 30The Bag of Holding
  31. 31A Map of Blocks
  32. 32Certainly Absent
  33. 33A Tree Made of Types
  34. 34Everything but the Views
  35. 35Who Owns the Wheel
  36. 36A Guest on the Loop
  37. 37Acknowledged Means Durable
  38. 38Sorted as Bytes

Part of Familiars: the small, sharp libraries I carved out of Xapiand. This one is a little compiler in a single class: boolean-parser.

People write boolean queries in infix: a OR (b AND NOT c), operators between their operands, precedence in their heads, parentheses to override it. It is the natural way to write and the worst way to evaluate, because you cannot read it left to right and act as you go. When you reach OR you do not yet know its right operand; when you hit ( you have to remember everything outside it and come back. Infix demands you look ahead and back up, which is exactly the sort of thing a stack was invented to avoid.

boolean-parser turns that human-written query into something a machine can just walk. Its whole job fits in one class, BooleanTree, and its constructor does all the work: lex the string into tokens, then run Dijkstra’s shunting-yard algorithm over them to produce a queue in Reverse Polish Notation.

The shunting yard is one of those algorithms that feels like a magic trick the first time it clicks, and it is named after exactly what it looks like: a railway shunting yard where cars are shuffled onto a side track and pulled back in a different order. You make one linear pass over the tokens with two stacks in hand, an output queue and an operator stack, and follow a tiny set of rules. An operand goes straight to the output. An operator waits on the operator stack, but before it does, any operators already there with higher-or-equal precedence get popped off to the output first, which is how precedence gets baked in without any lookahead. A ( pushes; a ) pops operators back to output until it finds its matching (. At the end you drain the stack. What falls out is the same expression in RPN, a b c NOT AND OR, where the order of operations is now implicit in the sequence and there is nothing left to parenthesize.

RPN is not just tidy; it is directly executable. To evaluate it you walk it front to back with one stack: push operands, and when you hit an operator, pop its operands, apply, push the result. No tree, no recursion, no precedence logic at runtime, because all of that was resolved in the single pass that built the queue. That is why many consumers, Xapiand’s query DSL included, only ever walk the RPN queue and never ask for anything more. The parser hands them a ready-to-run sequence.

For the times you do want structure, Parse() consumes that RPN queue and builds an AST: a tree of typed nodes, AndNode, OrNode, NotNode, XorNode, MaybeNode, IdNode, with the operators as internal nodes and the terms as leaves. It is built on demand, from the same queue, so you pay for the tree only if you use it. The grammar it understands is small and practical: the five operators as keywords, with &, | and ! as symbols for AND, OR and NOT, parentheses, single- and double-quoted phrases, and a [a,b,c] bracketed-list syntax, with precedence running from tightest to loosest as NOT, AND, MAYBE, XOR, OR. There is one humane touch that shows it came from a real query box: two terms written next to each other with no operator between them, a b, are joined by a default OR, because that is what a person typing two words almost always means.

Reach for it whenever you need to accept a boolean expression from a human and turn it into something evaluable: a search query language, a filter DSL, a rules string. You get the RPN queue for free and the AST when you ask. Skip it if your inputs are already structured (you have JSON, not a string), or if your expression language is richer than boolean connectives and needs a real grammar and parser generator.

The next familiar drops back down to raw bytes and the oldest trick for making them fewer. Three different ways to compress a buffer, three genuinely incompatible formats, hidden behind one interface so uniform you switch between them by changing a single word.