Grammars & Recursive Descent Parsing

Writing a Compiler/Interpreter: Fundamentals

Chapter 2 · Grammars & Recursive Descent Parsing

Chapter 1 turned Wisp source text into a flat stream of tokens. A parser's own job is to recover the structure that flat stream implies — which operations happen before which, and how they nest. This chapter defines Wisp's expression grammar formally, then builds a real recursive descent parser that implements it correctly.

The Grammar, as a Precedence Ladder

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

This is a context-free grammar — each rule describes a category of expression purely in terms of what it's built from, with no reference to surrounding context. The key design choice is the order of the rules: each level only calls down into the level below it, never back up. That ordering is what encodes precedence directly into the grammar's own shape, before a single line of parser code exists.

Precedence, Verified

def term(self):       # handles + and -, calls factor() for each operand
    expr = self.factor()
    while self.match('PLUS', 'MINUS'):
        ...

def factor(self):     # handles * and /, one level HIGHER precedence than term()
    expr = self.unary()
    while self.match('STAR', 'SLASH'):
        ...
    

Verified directly — the parser correctly gave multiplication priority over addition

Parsing "2 + 3 * 4" produces the tree (2.0 PLUS (3.0 STAR 4.0)) — the multiplication is nested inside the addition, exactly as required. Evaluating it gives 14.0, the mathematically correct answer.

Verified directly — a flat, precedence-free parser silently computed the wrong answer

A deliberately buggy parser with no separate precedence levels — every binary operator handled at one single level, left to right — evaluates "2 + 3 * 4" as 20.0, treating it as (2 + 3) * 4. No error, no crash — a silently, confidently wrong answer, produced by a parser that accepts exactly the same input and looks superficially reasonable.

This is why the grammar's own layering isn't optional structure — it's the actual mechanism

Nothing about the flat parser above is buggy in an obvious way; every function is syntactically valid and every token gets consumed. The bug is purely structural: collapsing every operator into one precedence level throws away the information the grammar was supposed to encode. This is the parser equivalent of Chapter 1's own maximal-munch finding — a subtly wrong structural decision that produces confidently wrong output rather than an error.

Associativity, Verified

Verified directly — the parser correctly enforced left-associativity for subtraction

Parsing "10 - 3 - 2" produces ((10.0 MINUS 3.0) MINUS 2.0) — the left operand groups first. Evaluating gives 5.0, matching how subtraction is actually meant to associate. A right-associative bug — grouping as 10 - (3 - 2) instead — would silently produce 9 for the exact same input.

The while loop, not recursion, is what makes this left-associative

Each precedence-level function calls itself only for the next tighter level's operand — never for another operator at its own level. Looping (while self.match(...)) rather than recursing at the same level is exactly what makes the tree grow leftward, one operation nested inside the next, instead of rightward.

Parentheses and Unary Minus

Verified directly — parentheses correctly override the grammar's own default precedence

"(2 + 3) * 4" evaluates to 20.0 — the parenthesized addition is forced to happen first, exactly overriding the default precedence that gave "2 + 3 * 4" its own correct 14.0 above. primary()'s own handling of ( recurses all the way back up to parse_expression(), letting any full expression appear inside parentheses, regardless of precedence level.

Verified directly — the same MINUS token correctly parsed as unary in one position and binary in another

"5 - -3" parses as (5.0 MINUS (MINUS3.0)) and evaluates to 8.0 — the first - is binary subtraction, the second is unary negation. "-5 + 3" parses as ((MINUS5.0) PLUS 3.0) and evaluates to -2.0 — the leading - is unary. The lexer never disambiguates this; both are identical MINUS tokens. The parser resolves it purely from position — unary() only treats a leading - as negation because it's checked before falling through to primary().

Where This Connects

This chapter's finding	What it connects to
A collapsed grammar silently computing the wrong answer	Chapter 1's own maximal-munch finding — both are cases where a structurally wrong decision produces confident, silent wrong output rather than a visible error
Nested tuples like `('binary', 'PLUS', left, right)` as a working parse tree	Chapter 3's own Abstract Syntax Tree chapter, which formalizes these tuples into real, typed node classes

Hands-On Exercises

Exercise 1

Add a new precedence level between factor and unary for exponentiation, using ^ as the operator, and make it right-associative (the mathematically standard convention: 2 ^ 3 ^ 2 should mean 2 ^ (3 ^ 2), not (2 ^ 3) ^ 2). Verify both the tree shape and the evaluated result.

📄 View solution

Exercise 2

Using this chapter's own parser, parse and evaluate "1 == 1 == 1". Determine what the equality operator's own left-associativity produces, and explain why the result might surprise someone expecting normal mathematical equality chaining.

📄 View solution

Exercise 3

Feed this chapter's own parser the deliberately malformed input "(2 + 3" (a missing closing parenthesis). Verify it raises the expected SyntaxError rather than crashing with an unrelated exception or silently accepting incomplete input, and explain which specific line of the parser catches this.

📄 View solution

Chapter 2 Quick Reference

Precedence via grammar layering: each level only calls down into the next tighter level — the ordering IS the precedence
Verified: "2 + 3 * 4" correctly gave 14.0; a flat, precedence-free parser silently gave 20.0 for the identical input
Left-associativity via a while loop: looping (not recursing) at the same precedence level grows the tree leftward
Verified: "10 - 3 - 2" correctly evaluated to 5.0; a right-associative bug would silently give 9
Verified: the identical MINUS token correctly parsed as unary or binary depending purely on position, not on any lexer-level distinction
Next chapter: Building an Abstract Syntax Tree — formalizing this chapter's own nested tuples into real, typed node classes