Abstract Syntax Trees & Semantic Analysis

The Cost of Concreteness

A parse tree (also called a concrete syntax tree or CST) is a faithful record of the grammar derivation. Every grammar rule that fired, every token matched, appears as a node. For the expression 3 + 4 * 5 with a grammar that eliminates left-recursion through Expr → Term (('+' | '-') Term)*, the parse tree has nodes for Expr, Term, Factor, and so on — even for the implicit precedence machinery that has no semantic content.

The abstract syntax tree strips all of that scaffolding. It keeps only semantically meaningful structure:

• Parentheses are gone (precedence is encoded in tree shape).
• Intermediate nonterminals like Term, Factor, Expr collapse into operator nodes.
• Keywords like if, while, return become node types, not children.
• Optional punctuation (semicolons, commas) disappears.

For 3 + 4 * 5, the AST is just:

     +
    / \
   3   *
      / \
     4   5

The shape itself encodes that * binds tighter than + — no extra nodes needed.

How Parsers Build ASTs

In a recursive-descent parser, each parsing function returns an AST node:

def parse_add_expr():
    left = parse_mul_expr()          # left subtree
    while current_token() == '+':
        consume('+')                 # discard the operator token
        right = parse_mul_expr()     # right subtree
        left = BinOpNode('+', left, right)  # fold left-associatively
    return left

The key insight: the grammar drives which AST node to create; the token ('+') is captured as a label on the node, not as a separate child.

AST Node Design

AST nodes are typically a class hierarchy (in OO languages) or a tagged union/algebraic data type (in functional languages). A minimal Python example:

from dataclasses import dataclass
from typing import Optional

@dataclass
class IntLiteral:
    value: int

@dataclass
class BinOp:
    op: str           # '+', '-', '*', '/'
    left: 'Expr'
    right: 'Expr'

@dataclass
class IfStmt:
    condition: 'Expr'
    then_branch: 'Stmt'
    else_branch: Optional['Stmt']

@dataclass
class VarDecl:
    name: str
    type_ann: 'TypeExpr'
    init: Optional['Expr']

Each class is an AST node kind. The tree is built bottom-up during parsing and then handed to semantic analysis.

# Building and printing a tiny expression AST
from __future__ import annotations
from dataclasses import dataclass
from typing import Union

@dataclass
class Num:
    value: int
    def __repr__(self): return str(self.value)

@dataclass
class BinOp:
    op: str
    left: Expr
    right: Expr
    def __repr__(self):
        return f'({self.left} {self.op} {self.right})'

Expr = Union[Num, BinOp]

# AST for  3 + 4 * 5
tree = BinOp('+', Num(3), BinOp('*', Num(4), Num(5)))
print(tree)   # -> (3 + (4 * 5))

# Evaluate by recursion
def eval_expr(node: Expr) -> int:
    if isinstance(node, Num):
        return node.value
    if isinstance(node, BinOp):
        l, r = eval_expr(node.left), eval_expr(node.right)
        if node.op == '+': return l + r
        if node.op == '*': return l * r
    raise ValueError(f'Unknown node: {node}')

print(eval_expr(tree))  # -> 23

The Problem: Adding Operations Without Modifying Nodes

Once you have an AST, you need to perform many passes over it: type-checking, constant folding, code generation, pretty-printing. If you put each operation as a method on each AST node class, you get an explosion of responsibilities — every node class grows a typecheck(), codegen(), prettyprint(), constantFold() method. Adding a new pass means modifying every node class. This violates the Open/Closed Principle.

The Visitor pattern inverts the relationship. Each pass is encapsulated in a Visitor class. Each AST node implements a single accept(visitor) method that dispatches to the appropriate visitor method. Adding a new pass means writing a new Visitor class — the AST node classes are untouched.

The Double-Dispatch Trick

The heart of the pattern is double dispatch: the call node.accept(visitor) dispatches first on the type of node, and then visitor.visit_BinOp(node) dispatches on the visitor type. This gives you the behavior of visit(BinOp, TypeCheckVisitor) without needing multiple dispatch in the language.

class Visitor:
    def visit_Num(self, node):   raise NotImplementedError
    def visit_BinOp(self, node): raise NotImplementedError

# Each AST node gets a one-liner accept:
class Num:
    def accept(self, v): return v.visit_Num(self)

class BinOp:
    def accept(self, v): return v.visit_BinOp(self)

# A concrete pass: constant folding
class ConstFold(Visitor):
    def visit_Num(self, node):
        return node  # already constant
    def visit_BinOp(self, node):
        l = node.left.accept(self)
        r = node.right.accept(self)
        if isinstance(l, Num) and isinstance(r, Num):
            ops = {'+': l.value + r.value, '*': l.value * r.value}
            return Num(ops[node.op])
        return BinOp(node.op, l, r)

Visitors in Real Compilers

In Java (ANTLR4 generates these), Go (ast.Walk), Rust (syn crate), and Clang (the RecursiveASTVisitor), the Visitor pattern or a close relative is the standard traversal mechanism. LLVM's InstVisitor uses the same idea for IR passes. Understanding this pattern is essential for reading compiler source code.

# Visitor that pretty-prints an expression AST
class PrettyPrint:
    def visit_Num(self, node):
        return str(node.value)
    def visit_BinOp(self, node):
        l = node.left.accept(self)
        r = node.right.accept(self)
        return f'({l} {node.op} {r})'

class TypeCheck:
    """Returns 'int' or raises TypeError."""
    def visit_Num(self, node):
        return 'int'
    def visit_BinOp(self, node):
        lt = node.left.accept(self)
        rt = node.right.accept(self)
        if lt != rt:
            raise TypeError(f'Type mismatch: {lt} {node.op} {rt}')
        return lt

# Add accept to each node class (or use Python singledispatch)
Num.accept   = lambda self, v: v.visit_Num(self)
BinOp.accept = lambda self, v: v.visit_BinOp(self)

tree = BinOp('+', Num(3), BinOp('*', Num(4), Num(5)))
print(tree.accept(PrettyPrint()))   # ((3 + (4 * 5)))
print(tree.accept(TypeCheck()))     # int

The Compiler's Address Book

A symbol table is the central data structure of semantic analysis. It maps names (identifiers) to their attributes: type, kind (variable, function, parameter, type alias), memory location (in later passes), and any other information needed to compile a use of that name.

When the compiler encounters int x = 5;, it enters x into the symbol table with attributes {kind: variable, type: int, value: 5}. When it later encounters x + 3, it looks up x to find its type so it can typecheck the addition.

What Goes in a Symbol Entry?

A typical entry contains:

• Name (the string key)
• Kind: variable, function, type, constant, label
• Type: int, float, (int, int) → bool, etc.
• Scope level: how deeply nested the declaration is
• Source location: file, line, column (for error messages)
• Other attributes: is it initialized? is it mutable? what is its storage class?

Implementation

The simplest implementation is a hash table from strings to symbol entries. A production symbol table also supports scope nesting (see next concept). Many compilers (GCC, LLVM) use a chained hash table with a per-scope slab allocator for fast reset when a scope exits.

typedef struct Symbol {
    const char *name;
    Kind        kind;    // VAR, FUNC, TYPE
    Type       *type;
    int         scope_level;
    SourceLoc   loc;
    struct Symbol *next; // for chaining in hash bucket
} Symbol;

typedef struct SymbolTable {
    Symbol *buckets[HASH_SIZE];
    int     current_scope;
} SymbolTable;

The Two Core Operations

• define(name, attrs): Insert a new symbol. If the name already exists in the same scope, it is a redeclaration error.
• resolve(name): Look up a name, searching from the innermost scope outward. If not found at any scope level, it is an undeclared identifier error.

# Python dict-based symbol table (single scope for now)
class SymbolTable:
    def __init__(self):
        self._table: dict[str, dict] = {}

    def define(self, name: str, kind: str, typ: str, loc=None):
        if name in self._table:
            raise SemanticError(f"Redeclaration of '{name}' at {loc}")
        self._table[name] = {'kind': kind, 'type': typ, 'loc': loc}

    def resolve(self, name: str) -> dict:
        if name not in self._table:
            raise SemanticError(f"Undeclared identifier '{name}'")
        return self._table[name]

class SemanticError(Exception): pass

st = SymbolTable()
st.define('x', 'var', 'int')
st.define('foo', 'func', 'int->bool')
print(st.resolve('x'))     # {'kind': 'var', 'type': 'int', 'loc': None}
st.define('x', 'var', 'int')  # raises SemanticError: Redeclaration of 'x'

Scoping: Rules for What a Name Means Here

Most languages have lexical (static) scoping: a name refers to the textually enclosing declaration. The alternative — dynamic scoping, used in some Lisps and Bash — looks up names at runtime along the call stack. Almost all modern languages (C, Java, Python, Rust, Go, Haskell) use lexical scope, and that is what we implement here.

The Scope Stack

Lexical scope is naturally modeled as a stack of symbol tables, one table per active scope:

[global scope]  →  [function scope]  →  [inner block scope]

When you enter a new scope (function body, block, for-loop), push a fresh table. When you exit, pop it. When resolving a name, walk from the innermost (top) table outward until found — or error if exhausted.

This gives you shadowing for free: if x is declared in both the inner and outer scope, the inner declaration is found first and shadows the outer one.

class ScopedSymbolTable:
    def __init__(self):
        self.scopes: list[dict] = [{}]   # stack; [0] = global

    def enter_scope(self):
        self.scopes.append({})

    def exit_scope(self):
        self.scopes.pop()

    def define(self, name, attrs):
        current = self.scopes[-1]
        if name in current:
            raise SemanticError(f"Redeclaration of '{name}' in same scope")
        current[name] = attrs

    def resolve(self, name):
        # Walk inward-to-outward
        for scope in reversed(self.scopes):
            if name in scope:
                return scope[name]
        raise SemanticError(f"Undeclared identifier '{name}'")

Scope Rules in Real Languages

Two-Pass Name Resolution

Some languages (Java, C#) allow forward references within a class — a method can call another method declared below it. This requires two passes:

1. First pass: scan the class and enter all member declarations into the symbol table.
2. Second pass: resolve the bodies.

Within a single function in C, no forward references are allowed — declarations must precede use, so one pass suffices.

# Scope stack in action: resolving names in nested blocks
st = ScopedSymbolTable()

# Global
st.define('PI', {'kind': 'const', 'type': 'float', 'value': 3.14})

# Enter function 'area'
st.enter_scope()
st.define('r', {'kind': 'param', 'type': 'float'})

  # Inner block
  st.enter_scope()
  st.define('r', {'kind': 'var', 'type': 'int'})  # shadows outer r
  print(st.resolve('r')['type'])   # int  (inner shadows outer)
  print(st.resolve('PI')['value']) # 3.14 (walks up to global)
  st.exit_scope()

print(st.resolve('r')['type'])     # float (outer r is back)
st.exit_scope()

try:
    st.resolve('r')                # error: r is gone
except Exception as e:
    print(e)   # Undeclared identifier 'r'

Wiring It Together: The First Semantic Pass

The standard way to populate the symbol table is a two-part AST walk:

1. Declaration visitor: Walk the AST; whenever you hit a declaration node (VarDecl, FuncDecl, ClassDecl), enter the symbol into the current scope. Push/pop scopes as you enter/exit block nodes.
2. Resolution visitor: Walk the AST; whenever you hit a name-use node (IdentExpr, CallExpr), call resolve() to look it up and attach the resolved symbol to the node (this is called decorating the AST — adding semantic annotations to nodes).

Some compilers merge these into a single pass (safe for simple languages with no forward references). Others perform them strictly separately.

Decorating the AST

After resolution, each IdentExpr node carries a pointer to its symbol entry:

BinOp('+',
  IdentExpr('x')  ← .symbol = {kind: var, type: int, scope: 1}
  Num(3)
)

This decoration allows later passes (type inference, code generation) to work directly with symbol information without calling back into the symbol table by name. It is an important design decision: the AST becomes a richer, annotated structure as it passes through semantic analysis.

The Full Flow

Source text
  → [Lexer] → tokens
  → [Parser] → raw AST
  → [DeclVisitor] → AST + populated symbol table
  → [ResolveVisitor] → decorated AST (each name node points to its symbol)
  → [TypeCheckVisitor] → decorated AST + type annotations on every node
  → [CodeGen] → IR / assembly

Each arrow is a pass over the AST. Real compilers often merge adjacent passes for performance, but the conceptual separation is clean.

# A minimal declaration + resolution visitor for a tiny language
# AST: Program([VarDecl | AssignStmt | IdentExpr])

from dataclasses import dataclass, field
from typing import Optional, Any

@dataclass
class VarDecl:
    name: str
    typ: str
    init: Optional[Any] = None
    symbol: dict = field(default_factory=dict, repr=False)

@dataclass
class IdentExpr:
    name: str
    symbol: dict = field(default_factory=dict, repr=False)

class DeclVisitor:
    def __init__(self):
        self.st = ScopedSymbolTable()

    def visit_VarDecl(self, node: VarDecl):
        entry = {'kind': 'var', 'type': node.typ}
        self.st.define(node.name, entry)
        node.symbol = entry            # decorate the declaration node too

    def visit_IdentExpr(self, node: IdentExpr):
        node.symbol = self.st.resolve(node.name)  # decorate with resolved symbol

decl_x = VarDecl('x', 'int')
use_x  = IdentExpr('x')

dv = DeclVisitor()
dv.visit_VarDecl(decl_x)
dv.visit_IdentExpr(use_x)

print(use_x.symbol)  # {'kind': 'var', 'type': 'int'}
# use_x.symbol IS THE SAME OBJECT as decl_x.symbol

Types as Contracts

A type is a set of values together with the operations permitted on them. The compiler's job in type checking is to verify, at compile time, that every operation is applied to a value of an appropriate type — without running the program.

There are two broad families:

• Static typing (C, Java, Rust, Haskell): Types are checked at compile time. Errors are caught before the program runs.
• Dynamic typing (Python, JavaScript, Ruby): Type errors are caught at runtime.

Within static typing:

• Nominal typing (Java, C#): Two types are compatible if they have the same name or one is declared to extend the other.
• Structural typing (TypeScript, Go interfaces, OCaml modules): Two types are compatible if they have the same structure (same fields, same method signatures).

The Type Checker Pass

A type checker is a visitor that:

1. For each expression node, computes and records its type (the synthesis rule).
2. For each statement node, checks that sub-expressions have expected types (the checking rule).

A type environment Γ maps variable names to their types (this is effectively your symbol table's type column). The type checking rules are often written as typing judgments:

Γ ⊢ e : τ

read as "in environment Γ, expression e has type τ."

For example:

[T-Int]   Γ ⊢ n : int     (n is an integer literal)
[T-Var]   Γ ⊢ x : τ      if (x : τ) ∈ Γ
[T-Add]   Γ ⊢ e1 : int   Γ ⊢ e2 : int
          ─────────────────────────────────
          Γ ⊢ e1 + e2 : int

Type Coercion and Promotion

Most languages define implicit widening conversions: int → float, char → int. The type checker must apply these rules and insert implicit cast nodes in the AST. An explicit narrowing conversion (float to int) requires the programmer to write a cast, because it may lose information.

Type Errors

Good type error messages are an art. The best compilers (Elm, Rust) explain why the types conflict, show the expected vs. actual type, and point to the relevant source location. Poor compilers cascade a single root error into dozens of misleading messages. The technique to avoid cascading: when a type error occurs, substitute a special ErrorType for the problematic subexpression and continue analysis — ErrorType is compatible with everything, preventing spurious further errors.

# Type checker for arithmetic expressions with float promotion
def typecheck(node, env: dict) -> str:
    if isinstance(node, Num):
        return 'int'
    if isinstance(node, FloatLit):
        return 'float'
    if isinstance(node, IdentExpr):
        if node.name not in env:
            raise TypeError(f"Undeclared: {node.name}")
        return env[node.name]
    if isinstance(node, BinOp):
        lt = typecheck(node.left,  env)
        rt = typecheck(node.right, env)
        if lt == rt:
            return lt   # same type: result is that type
        # Widening: int + float -> float
        numeric = {'int', 'float'}
        if lt in numeric and rt in numeric:
            # Insert implicit cast node in the AST
            if lt == 'int':
                node.left = CastNode('float', node.left)
            else:
                node.right = CastNode('float', node.right)
            return 'float'
        raise TypeError(f"Cannot apply '{node.op}' to {lt} and {rt}")

# Example:
# env = {'pi': 'float'}
# typecheck(BinOp('+', Num(3), IdentExpr('pi')), env)
# -> 'float'  (and wraps Num(3) in CastNode('float', ...))

What the Grammar and Types Cannot Enforce

Even after you have a well-typed program, there are contextual or semantic constraints that require deeper analysis. These are sometimes called context-sensitive rules, and they are the reason semantic analysis is more than just type checking.

Common Semantic Checks

1. Use before initialization In Java and Rust, the compiler verifies that every variable is definitely initialized before use. This requires a form of data-flow analysis (covered in a later module), but a simple approximation is checking whether a VarDecl has an initializer.

2. Break/Continue placement break and continue are only legal inside a loop (or switch). The checker tracks a "loop depth" counter; entering a loop increments it, exiting decrements it. Seeing break when the counter is 0 is an error.

3. Return on all paths A function that declares a non-void return type must have a return statement on every possible execution path. This is a control-flow problem: build a control-flow graph (CFG) of the function body and check that every path from entry to exit passes through a return.

4. Unreachable code Code after a return, break, or continue in the same block is unreachable. Good compilers warn about this.

5. Dead code / unused variables Many compilers and linters track whether a declared variable is ever read. This catches bugs like int result = compute(); return 0; where result is never used.

6. Integer overflow / array bounds (optional) Some compilers (Rust, AdaCore SPARK) perform range analysis to prove at compile time that an array index is always in bounds or that an integer cannot overflow.

7. Duplicate case labels in switch Two case 42: branches in the same switch statement — detectable by scanning the case labels.

Implementation Pattern

For loop-depth checks:

class LoopChecker(Visitor):
    def __init__(self):
        self.loop_depth = 0
    def visit_WhileStmt(self, node):
        self.loop_depth += 1
        node.body.accept(self)
        self.loop_depth -= 1
    def visit_BreakStmt(self, node):
        if self.loop_depth == 0:
            raise SemanticError("'break' outside of loop")

This pattern — a counter or flag that tracks context as you traverse — is the workhorse of context-sensitive checking.

# Return-on-all-paths checker for a simple if-else language
# Returns True if the subtree DEFINITELY returns.
def definitely_returns(node) -> bool:
    if isinstance(node, ReturnStmt):
        return True
    if isinstance(node, IfStmt):
        # Only certain if BOTH branches return AND else exists
        if node.else_branch is None:
            return False
        return (definitely_returns(node.then_branch) and
                definitely_returns(node.else_branch))
    if isinstance(node, Block):
        # Certain if ANY statement definitely returns
        # (subsequent stmts are unreachable but that's a warning, not error)
        return any(definitely_returns(s) for s in node.stmts)
    return False  # assignment, expr-stmt, etc. don't return

# Example use:
# func body:  if (x > 0) { return 1; } else { return -1; }
# definitely_returns -> True
#
# func body:  if (x > 0) { return 1; }
# definitely_returns -> False  => error: missing return

Syntax Sugar and Lowering

Desugaring is the process of transforming complex language constructs into simpler ones. It is typically performed on the AST before or during semantic analysis, making later passes (especially code generation) simpler by reducing the number of node types they need to handle.

The term comes from syntactic sugar — syntactically convenient notation that the compiler secretly transforms into a more primitive form. Classic examples:

Why Desugar?

• Simplifies code generation: codegen only handles the small core language.
• Simplifies semantic analysis: you write type-checking rules for the desugared form once.
• Enables optimization: the optimizer works on the simpler form and the benefit applies to all sugar that maps to it.

Lowering vs. Desugaring

Desugaring happens at the AST level — transforming one AST node into another. Lowering happens later, transforming the AST into an IR. In practice the terms are used loosely. The key principle is: reduce the surface area of the AST that subsequent passes must handle, as early as possible.

In Practice

Haskell's GHC desugars almost everything into a tiny Core language (a typed lambda calculus with case expressions and let bindings). All the syntactic richness of Haskell — where clauses, list comprehensions, do-notation, guards — is eliminated in a single desugaring pass. This is a major reason GHC can perform aggressive optimizations: it only needs to optimize Core.

# Desugar ForIn into While in the AST
@dataclass
class ForIn:
    var: str
    iterable: Expr
    body: Stmt

@dataclass
class WhileStmt:
    cond: Expr
    body: Stmt

@dataclass
class Block:
    stmts: list

def desugar_for_in(node: ForIn) -> Block:
    """
    for x in xs:
        body
    ->
    _iter = iter(xs)
    while True:
        try: x = next(_iter)
        except StopIteration: break
        body
    (Simplified version — just illustrates the idea)
    """
    iter_var = '_iter_' + node.var
    return Block([
        VarDecl(iter_var, 'iter', CallExpr('iter', [node.iterable])),
        WhileStmt(
            cond=BoolLit(True),
            body=Block([
                AssignStmt(node.var, CallExpr('next', [IdentExpr(iter_var)])),
                node.body,
            ])
        )
    ])