Abstract Syntax Trees and Semantic Analysis

Learning Objectives

Design AST node types for literals, unary, binary, variable, assignment and call expressions, statements and blocks; traverse them with visitors or tagged unions.

Perform name binding and scope resolution; detect undefined identifiers and duplicate declarations; distinguish static type checking from dynamic checks and static from runtime semantics.

Apply constant folding, desugaring and lowering; serialise, visualise and test ASTs.

Plain-Language Explanation

The AST is the program's skeleton. Before running it, a compiler can walk the skeleton to check things that do not depend on run-time values — "is this name declared?", "is this variable declared twice in the same block?", "is return used outside a function?" — and to simplify it, for example replacing 2 * 3 with 6.

Precise Technical Explanation

Why ASTs exist They decouple syntax from everything after parsing: checkers, optimisers, interpreters and code generators all work on the same structured representation without re-reading text.

AST node types MiniLang's AST has expression nodes (Literal, Variable, Assign, Unary, Binary, Logical, Grouping, Call) and statement nodes (Let, Print, Expression, Block, If, While, Fun, Return). Every node has an id and a span.

Literal(value) for numbers, strings, true, false and nil — the value is already decoded by the lexer.

Unary and binary expressions Unary(op, right); Binary(op, left, right). Logical(and/or) is separate from Binary because it does not always evaluate its right operand.

Variable(name) — a *use* of a name, to be resolved to a declaration.

Assign(name, value) — an expression (its value is the assigned value), so a = b = 5 works. Only a variable is a valid target; 1 = 2 is rejected ("Invalid assignment target").

Call(callee, args) — the callee is any expression (f(1)(2) calls the result of f(1)).

Statements and blocks Statements are executed for effect; Block(body) introduces a scope.

The visitor pattern puts one method per node type in a visitor object (visitBinary, visitCall…) so new passes can be added without modifying node classes — common in Java and C# compilers.

Pattern matching / tagged unions for AST nodes In languages with sum types or tagged unions, a pass is a switch/match on the node tag. MiniLang uses a TypeScript discriminated union (k: "Binary"), and the compiler checks that every case is handled.

Source locations and diagnostics Spans connect every later error back to source text, including runtime errors (Runtime error [line 3:7]).

Each identifier use is bound to a declaration. MiniLang's compiler binds locals to stack slots, captured variables to upvalue indices and everything else to global names.

Statically scoped languages with closed global scopes report them at compile time (Java). MiniLang, like Python and JavaScript, allows late-bound globals, so an undefined global is a runtime error — the function might be called only after the global is defined.

Redeclaring a local in the same block is a compile error in MiniLang; redeclaring a global is allowed (useful in a REPL).

A pass with a stack of scopes: entering a block pushes, leaving pops; a use resolves to the innermost declaration. Also detects reading a local in its own initializer (let a = a; inside a block).

Type checking versus dynamic type checks Static type checking proves operand types before running (Java rejects 1 + true); dynamic checks inspect tags at run time (MiniLang reports Operands of '+' must be two numbers or two strings).

Static semantics versus runtime semantics Static: scope rules, "no return at top level", arity limits. Runtime: evaluation order, values, errors such as division by zero.

Evaluating operations on constants at compile time: 2 * 3 + 1 → 7. Safe only when it cannot change behaviour (no side effects, same overflow and floating-point semantics, no error that should happen at run time).

Rewriting convenient syntax into core forms: a for loop into while, a += 1 into a = a + 1, >= into !(<) — MiniLang's compiler emits LESS, NOT for >=.

Lowering AST to IR Translating the tree into a lower-level form — bytecode (Module 8) or a control-flow graph of three-address instructions (Module 10).

AST serialization and inspection ASTs can be printed (MiniLang's printAst), dumped as JSON, or inspected with built-in modules (Python's ast).

Tree diagrams linked to source spans — the AST explorer in this course highlights the source range of a selected node.

Golden tests of printed ASTs, property tests (pretty-print then re-parse gives the same AST), and pass-specific tests (folding never changes results).

Example AST for 1 + 2 * 3:

Multiplication is nested as the right operand because of precedence.

Binary(+)
├── Number(1)
└── Binary(*)
    ├── Number(2)
    └── Number(3)

Why It Matters in Real Systems

Every linter, formatter, refactoring tool, type checker and compiler is a set of passes over an AST. Catching errors statically saves users from run-time failures.

Key Terms

Object with one method per node type Connecting each use to its declaration

Computing constant expressions at compile time Rewriting syntax into core constructs

Translating to a lower-level representation

Diagram, Execution Trace or State Transition

Text equivalent: after parsing, passes resolve names, run static checks, optionally simplify the tree and finally lower it to bytecode or another IR.

flowchart LR
  P[Parser: AST] --> R[Resolver: scopes, bindings]
  R --> T[Checks: duplicates, return placement, types]
  T --> F[Optimise: folding, desugaring]
  F --> L[Lower: bytecode / IR]

Syntax or Instruction Format

MiniLang AST node shapes (TypeScript discriminated union, abridged):

Binary    { k: "Binary", op, left: Expr, right: Expr, span, id }
Variable  { k: "Variable", name, span, id }
Let       { k: "Let", name, init: Expr, span, id }
Fun       { k: "Fun", name, params: string[], body: Stmt[], span, id }

Complete Example

Static checks in MiniLang — each program is rejected before any code runs (the build runs each on both back ends; they report the same error):

An undefined global is a *runtime* error — the program prints first, then fails:

Python exposes its AST and folds constants in its compiler (CPython 3.13.1 — the bytecode listing is version-specific):

{ let a = 1; let a = 2; }

Compile error [line 1:14]: Already a variable named 'a' in this scope.

{ let total = total + 1; }

Compile error [line 1:15]: Can't read local variable 'total' in its own initializer.

return 42;

Compile error [line 1:1]: Can't return from top-level code.

print("before");
print(notDeclared);

before
Runtime error [line 2:7]: Undefined variable 'notDeclared'.

import ast, dis

tree = ast.parse("y = 1 + 2 * 3")
print(ast.dump(tree.body[0].value))

def f():
    return 2 * 3 + 1          # folded at compile time

dis.dis(f)

BinOp(left=Constant(value=1), op=Add(), right=BinOp(left=Constant(value=2), op=Mult(), right=Constant(value=3)))
  6           RESUME                   0

  7           RETURN_CONST             1 (7)

Line-by-Line Explanation

Duplicate local, self-referencing initializer and top-level return are static-semantics errors: MiniLang's checker reports them with positions before execution.

The undefined global passes the static checks (globals are late-bound), so before is printed and the error happens at run time.

Python: ast.dump shows the nested BinOps; dis shows RETURN_CONST 7 — CPython's compiler folded 2 * 3 + 1 (instruction names are those of CPython 3.13).

Step-by-Step Runtime Behavior

Static checks run once per compilation, before any output; runtime checks run each time the operation executes.

Common Misconceptions

"Dynamic languages have no static checks." They still check syntax and some scope rules (MiniLang, Python's SyntaxError for return outside functions).

"Constant folding is always safe." Not if it changes errors, overflow or floating-point results.

Common Bugs and Failure Modes

Resolving a name against the wrong scope (shadowing bugs), forgetting to visit a child node, folding expressions with side effects, losing spans in desugared nodes.

Corrected or Safer Patterns

Exhaustive switch over node kinds (the TypeScript compiler checks it), keep spans on synthesised nodes, fold only pure constant expressions.

Debugging and Inspection Techniques

Print the AST after each pass; diff ASTs before and after an optimisation.

Performance Considerations

Each pass is linear in tree size; merging passes saves traversals; folding reduces run-time work.

Security Considerations

ASTs of untrusted code can be huge or deeply nested — limit size and depth; never eval reconstructed source.

Portability and Version Caveats

AST shapes are implementation APIs: Python's ast node classes change between versions (ast.Num was removed in 3.12 in favour of ast.Constant).

Real-World Use Cases

ESLint rules, Black/Prettier formatters, refactoring tools, macro systems, static analysers, code generators.

Best Practices

Keep the AST small and explicit; add passes rather than complicating the parser; test passes in isolation.

Exercises

E1 · Beginner. Which of these are static errors in MiniLang: (a) print(1 / 0); (b) { let x = 1; let x = 2; } (c) print(y);?

Answer: Only (b). (a) is a runtime error (division by zero); (c) is a runtime error (late-bound global).

E2 · Intermediate. Write a constant-folding rule for Binary nodes in MiniLang. Which operator needs special care?

Answer: If both children are number literals, replace the node with the computed literal — except / with a zero divisor, which must still raise "Division by zero" at run time (leave it unfolded). String + can also fold.

E3 · Advanced challenge. Desugar for (let i = 0; i < n; i = i + 1) body into MiniLang's existing constructs.

Answer: { let i = 0; while (i < n) { body i = i + 1; } } — the outer block scopes i to the loop.

Quiz

? Why is `print(notDeclared);` a runtime error in MiniLang rather than a compile-time error?
+ Globals are late-bound: the name might be defined before the code runs. :: The check happens when the variable is read.
- MiniLang has no compiler. :: It has both a compiler and an interpreter.
- The lexer cannot see identifiers. :: It produces IDENTIFIER tokens.
- Printing is not checked. :: Unrelated.

? What does constant folding do?
+ Computes constant expressions at compile time. :: E.g. 2 * 3 + 1 → 7.
- Removes all constants. :: Constants remain, already computed.
- Converts strings to numbers. :: No.
- Runs the program twice. :: No.

? Which belong to static semantics? (select all that apply)
+ Redeclaring a local in the same scope :: Checked before running.
+ `return` outside a function :: Checked before running.
- Division by zero with run-time values :: A runtime error.
+ Reading a local in its own initializer :: Checked before running.

Summary and Key Takeaways

ASTs carry the program's structure and source spans into a series of passes: name binding, scope checks, type checks, folding, desugaring and lowering. Static semantics are checked once before execution; runtime semantics are checked as the program runs.