STAGE 2 · THE PARSER

The Grammar Takes Shape

1 + 2 * 3 is seven tokens but only one shape, and the shape is what carries meaning.

What you're wiring up

The parser reads the token stream and welds it into a tree that mirrors the code's real structure. In 1 + 2 * 3 the multiplication binds tighter, so it sits deeper in the tree. Precedence stops being a rule you memorize and becomes a fact about geometry.

You will build a Pratt parser — top-down operator precedence. Every token type knows two things: what it means at the start of an expression, and what it means in the middle. A precedence table settles every fight. It sounds academic and is about 150 lines that will permanently change how you read code.

The AST itself is a Composite: one Node interface, leaves and branches treated uniformly, expression nodes all the way down. Each node keeps the token that started it, which is how positions survive the trip to Stage 6.

# source        →  blu ast  (canonical parenthesized form)
-a * b            ((-a) * b)
a + b * c         (a + (b * c))
(a + b) * c       ((a + b) * c)
!(x == y)         (!(x == y))

Assembly steps

[ 01 ]

Define the expression node types: integer literal, boolean, identifier, prefix (-x, !x), infix, and grouped expressions.

hint

Give every node a String method that prints itself fully parenthesized. It makes the tree's shape visible and is exactly what the harness diffs.

[ 02 ]

Build the parser skeleton: current and peek tokens, plus prefix and infix parse-function maps keyed by token type.

[ 03 ]

Implement parseExpression(precedence) — parse a prefix, then while the next operator binds tighter than the incoming precedence, hand the tree so far to that operator's infix function.

hint

The whole algorithm is one loop: left = prefixFn(), then for peekPrecedence() > precedence { left = infixFn(left) }. If you write more than that, back up.

hint

Trace 1 + 2 * 3 on paper against your table before debugging code. Nine times in ten the table is wrong, not the loop.

[ 04 ]

Fill the precedence table (equality below comparison below additive below multiplicative below prefix), then add grouped expressions and if/else expressions.

[ 05 ]

Wire blu ast: parse a file and print the parenthesized form; on a bad token, record a parse error carrying a position instead of panicking.

hint

Real recovery arrives in Stage 6. Here it is enough to stop cleanly with a located message.

Go deeper (after it passes)

The AST is a textbook Composite — pair this with HFDP M8 — One Waitress, Many Menus (Iterator and Composite). The eval switch you write next is the hand-rolled alternative to Visitor, covered in HFDP M12 — Patterns in the Wild.