Recursive Descent — The Simplest Parser

From Tokens to Structure

The scanner gives you a flat list of tokens. But 1 + 2 * 3 isn't flat — multiplication binds tighter than addition, so this really means "1 plus (2 times 3)". Parsing is the process of recovering that nested structure from the linear token stream, producing a tree that reflects how the expression should actually be evaluated.

Recursive descent is the most direct way to write a parser by hand: one function per grammar rule, where each function calls the functions for the rules "below" it (higher precedence), and returns up to the rules "above" it (lower precedence). It mirrors the grammar so closely that once you have the grammar right, the parser almost writes itself.

The Grammar, Read as a Precedence Ladder

expression → equality
equality   → comparison ( ("!=" | "==") comparison )*
comparison → term ( (">" | ">=" | "<" | "<=") term )*
term       → factor ( ("-" | "+") factor )*
factor     → unary ( ("/" | "*") unary )*
unary      → ("!" | "-") unary | primary
primary    → NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"

Read this top-to-bottom as loosest-binds-first: equality (==, !=) is the loosest, unary and primary are the tightest. Each rule calls down to the next-tighter rule for its operands. This ordering is exactly how precedence gets encoded — you never have to write an explicit "precedence table," because the call structure of the parser itself is the precedence table.

The Left-Recursion-Free Loop Pattern

Each binary-operator rule follows an identical shape — parse one operand at the next level down, then loop consuming (operator operand)* pairs:

Notice this builds a left-associative tree: 1 - 2 - 3 becomes ((1 - 2) - 3), because each new operator wraps the previously built expression as its left operand. This is why the loop, not recursion, is used for the repeated * in the grammar rule — true left recursion (equality → equality "==" comparison) can't be implemented directly as a recursive function call (infinite loop), so the while loop is the standard trick to handle it.

Core Parser Utilities

Every recursive descent parser needs a small set of helpers around a tokens list and a current index:

• peek() — look at the current token without consuming it
• check(type) — is the current token of this type?
• advance() — consume and return the current token, move current forward
• match(*types) — if the current token is one of these types, consume it and return true

Output: S-Expressions as a Debugging Lens

For this exercise, the parser's output is rendered as an S-expression — (+ 1.0 (* 2.0 3.0)) for 1 + 2 * 3. This isn't the final representation you'll use inside the interpreter (that's a proper AST of node objects, coming next lesson), but it's an invaluable way to see the tree your parser actually built, which makes precedence bugs immediately visible: if 1 + 2 * 3 prints as (* (+ 1.0 2.0) 3.0), you know precedence is inverted before you ever try to evaluate anything.