Abstract Syntax Trees

An Abstract Syntax Tree (AST) is a tree representation of the syntactic structure of source code. Unlike the raw token stream, an AST captures the hierarchical relationships between language constructs and discards irrelevant details like whitespace and parentheses.

Concrete vs Abstract

A parse tree (concrete syntax tree) includes every token. An AST abstracts away syntactic sugar:

Source:       (1 + 2) * 3
Parse tree:   primary → "(" expression ")" ...
AST:          Multiply(Add(1, 2), 3)

The parentheses are gone from the AST — they did their job during parsing by controlling structure. The tree itself encodes the grouping.

AST Node Types

For our language, we need these expression nodes:

Literal(value)              // 42, "hello", true, nil
Unary(operator, operand)    // -x, !flag
Binary(left, operator, right) // a + b, x == y
Grouping(expression)        // (expr) — only for printing

Each node type is a distinct data structure. In Java, Nystrom uses the Visitor pattern to walk the tree. In Python, you might use classes with a shared base. In Rust, you would use an enum with variants.

Evaluating the AST

A tree-walk interpreter evaluates the AST by recursively visiting each node:

evaluate(node):
    if node is Literal:    return node.value
    if node is Unary:
        val = evaluate(node.operand)
        if node.op == MINUS: return -val
        if node.op == BANG:  return !val
    if node is Binary:
        left = evaluate(node.left)
        right = evaluate(node.right)
        if node.op == PLUS: return left + right
        ...

This is the simplest possible interpreter — no bytecode, no compilation, just tree walking. Ruby's MRI interpreter worked this way for years before switching to a bytecode VM in Ruby 1.9. Python 1.x also used tree-walking before moving to bytecode.

Performance Considerations

Tree-walk interpreters are slow because of:

• Pointer chasing: each node is a heap allocation, causing cache misses
• Recursive overhead: deep expression trees cause deep call stacks
• No optimization: every evaluation re-traverses the tree

We will later build a bytecode compiler and VM that is 10-100x faster. But the tree-walk interpreter is perfect for understanding the semantics of our language.

Your Task

Build AST node types, a tree printer (S-expression format), and an evaluator that computes results by walking the tree.