Building an Abstract Syntax Tree

Writing a Compiler/Interpreter: Fundamentals

Chapter 3 · Building an Abstract Syntax Tree

Chapter 2's parser already produced a correctly-shaped tree — but it built that tree out of raw nested tuples like ('binary', 'PLUS', left, right). That works, but nothing stops a typo like 'PLSU' from silently producing a tuple that looks fine until something tries to read it. This chapter replaces those tuples with real, typed node classes, then confronts the maintenance problem that immediately creates: how do you add a new operation over a tree of several different node types without a giant, duplicated type-check in every single function that walks it? The answer is the Visitor pattern — introduced here from scratch, verified against the same "2 + 3 * 4" example this course has used since Chapter 2.

From Tuples to Typed Nodes

class Expr:
    def accept(self, visitor):
        raise NotImplementedError

@dataclass
class Literal(Expr):
    value: Any
    def accept(self, visitor):
        return visitor.visit_literal(self)

@dataclass
class Binary(Expr):
    left: Expr
    operator: str
    right: Expr
    def accept(self, visitor):
        return visitor.visit_binary(self)

# Grouping and Unary follow the identical shape
    

Each node is now a real, typed class instead of an anonymous tuple — Literal, Grouping, Unary, and Binary, matching the grammar rules Chapter 2 already defined. Every node also carries one extra method, accept(), whose only job is to call back into whatever visitor is walking the tree. Nothing about that method looks like it does much yet — its actual purpose only becomes clear once there's more than one thing that needs to walk the tree.

Verified directly — the parser now produces a real, typed tree instead of a nested tuple

Parsing "2 + 3 * 4" with the node classes above produces:

Binary(left=Literal(value=2.0), operator='+', right=Binary(left=Literal(value=3.0), operator='*', right=Literal(value=4.0)))

— structurally identical to Chapter 2's own tuple tree, but every node is now a real class instance with named fields, not a positional tuple that a typo could silently corrupt.

The Naive Way: One Type-Check Chain Per Operation

Before reaching for accept(), it's worth building the obvious first approach and seeing exactly where it breaks down. A function that evaluates a tree, and a separate function that prints one as a readable string, each need to ask "what kind of node is this?" — the obvious way is isinstance:

def evaluate_isinstance(node):
    if isinstance(node, Literal):
        return node.value
    elif isinstance(node, Grouping):
        return evaluate_isinstance(node.expression)
    elif isinstance(node, Unary):
        ...
    elif isinstance(node, Binary):
        ...
    raise TypeError(f"no case for {type(node).__name__}")

def stringify_isinstance(node):
    if isinstance(node, Literal):
        return str(node.value)
    elif isinstance(node, Grouping):
        ...
    # ...the SAME four-way type check, written a second time
    

Verified directly — both isinstance-chain functions correctly reproduce Chapter 2's own results

On the typed tree for "2 + 3 * 4": evaluate_isinstance(tree) returns 14.0, and stringify_isinstance(tree) returns (+ 2.0 (* 3.0 4.0)) — both exactly matching what Chapter 2's tuple-based approach already produced. The type-check chain works. The problem is what happens next.

A New Node Type Arrives

Suppose a fifth node type shows up — Variable, a forward reference to Chapter 5's own variable lookups. Adding it means finding every function that walks the tree and adding a matching branch to each one's own type-check chain. It's easy to update one and genuinely forget the other — nothing forces you to touch both.

Verified directly — a real, reproduced maintenance slip: one function updated, one forgotten

evaluate_isinstance_v2 (updated with a Variable case) correctly evaluates Variable('x') + 5 as 15.0 for x = 10.0. The original, unmodified stringify_isinstance — called on the exact same tree — raises TypeError: stringify_isinstance: no case for Variable. One function knows about the new node type. The other doesn't, and there is nothing in the language that would have caught this before it actually ran.

This TypeError only happened because the chain ends with an explicit raise

That final raise TypeError(...) at the bottom of each function isn't automatic — it's a line someone has to remember to write, in every single type-check function, forever. Exercise 3 at the end of this chapter shows what happens to a chain that omits it.

The Visitor Pattern: Double Dispatch

A note on where this sits relative to the rest of the site: this course's own Design Patterns course covers 16 of the classic Gang-of-Four patterns in depth, but names Visitor explicitly as one of the 7 left out of scope in its own opening chapter. So rather than a cross-reference, here is a compact, from-scratch introduction — because Visitor happens to be the standard, textbook answer to exactly the problem the last two sections just ran into.

The mechanism is called double dispatch. A visitor object implements one method per node type — visit_literal, visit_grouping, visit_unary, visit_binary. To evaluate a node, you don't ask "what type is this node" at all — you call node.accept(visitor), and the node's own accept() method (defined once, back when the node class was written) already knows which visit_ method to call back. Two dispatches: first to the node's own type via accept(), then to the visitor's matching method.

class Evaluator:
    def visit_literal(self, node):
        return node.value
    def visit_binary(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        ops = {'+': left + right, '-': left - right, '*': left * right, '/': left / right}
        return ops[node.operator]
    # visit_grouping, visit_unary follow the same shape

class AstPrinter:
    def visit_literal(self, node):
        return str(node.value)
    def visit_binary(self, node):
        return f"({node.operator} {node.left.accept(self)} {node.right.accept(self)})"
    # ...

tree.accept(Evaluator())   # 14.0
tree.accept(AstPrinter())  # "(+ 2.0 (* 3.0 4.0))"
    

Verified directly — the Visitor-based evaluator and printer reproduce the isinstance-chain results exactly

tree.accept(Evaluator()) returns 14.0. tree.accept(AstPrinter()) returns (+ 2.0 (* 3.0 4.0)) — identical to both the tuple-based approach from Chapter 2 and the isinstance chains earlier in this chapter. Nothing about the observable behavior changed. What changed is where the type-dispatch logic lives.

Adding an Operation Without Touching a Single Node Class

The real test: add a third operation — a NodeCounter that tallies how many nodes of each type appear in a tree — and see what each approach actually requires.

Verified directly — both approaches produce the correct count, but cost genuinely different amounts of new code

Both an isinstance-chain count_nodes_isinstance() and a Visitor-based NodeCounter class correctly report {'Binary': 2, 'Literal': 3} for the "2 + 3 * 4" tree. The isinstance-chain version required writing a third full four-way type check from scratch. The Visitor version required zero new accept() methods on any node class — those were already written, back in the first section of this chapter, and never touched again.

Verified directly — counting the actual dispatch logic across the whole file

Across all three isinstance-chain functions (evaluate_isinstance, stringify_isinstance, count_nodes_isinstance), there are 13 separate isinstance(node, ...) checks — the same four-way type distinction, re-written by hand three times. Across every node class's own accept() method, there are exactly 4 dispatch points, defined once, that every current and future visitor reuses without modification. This is the actual, measurable shape of the Visitor pattern's benefit — it doesn't reduce total code, it moves the type-dispatch logic to one place per type instead of duplicating it once per operation.

This is the classic Gang-of-Four framing for when Visitor is the right tool

Visitor trades one axis of flexibility for another. Adding a new operation (a new visitor) becomes cheap — write one class, touch nothing else. Adding a new node type becomes more expensive — every existing visitor now needs a new method, or it fails the moment it meets that type. For an AST, that tradeoff is usually the right one: this course will add plenty of new operations over these same four-ish node types (an evaluator in Chapter 4, a resolver, a compiler in Course 2's own bytecode chapters) — but the node types themselves change rarely.

Failing Loud vs. Failing Silent

One more property falls out of the Visitor pattern for free, without anyone writing a single extra line to get it. Build an EvaluatorWithEnv that correctly implements visit_variable, and an AstPrinter that — realistically — hasn't been updated yet:

Verified directly — the missing visit method fails immediately and specifically, with no fallback code required

var_tree2.accept(EvaluatorWithEnv({'x': 10.0})) correctly returns 15.0. Calling var_tree2.accept(AstPrinter()) — where AstPrinter has no visit_variable method — immediately raises AttributeError: 'AstPrinter' object has no attribute 'visit_variable'. Nobody wrote that error. It's just what happens when Python tries to look up a method that was never defined.

Where This Connects

This chapter's finding	What it connects to
Nested tuples formalized into typed `Expr` subclasses with `accept()`	Chapter 2's own raw `('binary', 'PLUS', left, right)` tuples, now replaced with real node classes carrying the same shape
The `Evaluator` visitor built in this chapter	Chapter 4's own tree-walking evaluator, which extends exactly this class with statements, scope, and control flow
Visitor missing a method fails loudly with `AttributeError`	Chapter 9's own error-handling chapter, which distinguishes this kind of implementation bug from a genuine Wisp-program runtime error
Design Patterns' own Chapter 1 named Visitor as explicitly out of scope	This chapter fills that specific, honestly-flagged gap rather than falsely claiming a cross-reference that doesn't exist

Hands-On Exercises

Exercise 1

Add a new Ternary node type for a conditional expression (cond ? then : else), including its own accept() method. Implement matching visit_ternary methods on both Evaluator and AstPrinter, and verify a tree for 1 ? 2 : 3 evaluates to 2.0 and prints as (ternary 1.0 2.0 3.0).

📄 View solution

Exercise 2

Write a new visitor, MaxDepth, that computes the maximum nesting depth of a tree (a Literal alone has depth 1) without modifying Literal, Grouping, Unary, or Binary at all. Verify it against the "2 + 3 * 4" tree from this chapter, and against a deeper tree like "((1 + 2) * (3 + 4))".

📄 View solution

Exercise 3

Write an isinstance-chain function contains_division(node) that checks whether a tree contains a division operator — but deliberately omit the final raise for unhandled node types. Run it on a tree containing a Variable node and determine exactly what it returns. Explain, in terms of Python's own truthiness rules, why the result is wrong rather than an error — and how the equivalent Visitor-based version would have failed instead.

📄 View solution

Chapter 3 Quick Reference

Typed AST nodes: Literal, Grouping, Unary, Binary replace Chapter 2's raw tuples, each with an accept(visitor) method
Verified: the typed tree for "2 + 3 * 4" is structurally identical to Chapter 2's tuple tree, just now a real, typed object
Verified: a new node type updated in one isinstance-chain function but forgotten in another raised a real TypeError — a genuine, reproduced maintenance slip
Double dispatch: node.accept(visitor) calls back visitor.visit_X(node) — no type-checking anywhere
Verified: adding a third operation (NodeCounter) needed zero new accept() methods; the isinstance-chain equivalent needed a full new type check, bringing the total to 13 dispatch checks across 3 functions vs. 4 defined once, ever
Verified: a visitor missing a method fails immediately with AttributeError — no fallback code required, unlike an isinstance chain's easy-to-omit final raise
Honest gap: this course's own Design Patterns course names Visitor as out of scope — this chapter is the from-scratch introduction that fills it
Next chapter: Tree-Walking Evaluation — extending this chapter's own Evaluator into a full interpreter for statements, not just expressions