ASTs: Structure, Traversal, and Practical Manipulation

Compilers Compilers 8 min read 1542 words Beginner ExcellentWiki Editorial Team

An Abstract Syntax Tree (AST) is a tree representation of source code that strips away concrete syntax details like parentheses, semicolons, and whitespace, retaining only the structural and semantic essence of the program. Every compiler and interpreter begins serious work only after constructing an AST from the token stream produced during lexing and parsing. The AST is the bridge between a program’s surface form and its meaning — it is what the compiler analyzes, transforms, and ultimately uses to generate executable code. Understanding AST structure, traversal, and manipulation is essential for anyone building compilers, linters, static analyzers, or language tooling.

What Is an Abstract Syntax Tree?

An AST differs fundamentally from a Concrete Syntax Tree (CST), also called a Parse Tree. A CST preserves every detail of the grammar, including terminals like keywords, operators, and punctuation. The expression 3 + 4 * 5 produces a CST with nodes for every token and every production rule, including intermediate nodes for nonterminals like <expression>, <term>, and <factor>. An AST collapses these into a clean hierarchy: a BinaryOp node with operator + and two children — a literal 3 and another BinaryOp for * with children 4 and 5. Parentheses, precedence-encoding intermediary nodes, and syntactic noise are discarded.

Aho, Lam, Sethi, and Ullman devote significant attention to AST construction in the Dragon Book (Compilers: Principles, Techniques, and Tools, 2nd ed.), describing how syntax-directed translation schemes can build an AST during parsing. The typical approach attaches semantic actions to grammar productions that construct tree nodes rather than emitting code directly. For example, an LR parser can build an AST bottom-up by pushing subtree pointers onto its value stack alongside grammar symbols.

Node Types and Structure

AST nodes typically form a disjoint union (tagged union or sum type) where each variant corresponds to a language construct. A minimal expression language might define nodes for:

Literal nodes — integer constants, string literals, boolean values
Binary operator nodes — arithmetic, comparison, logical operators
Unary operator nodes — negation, logical not, address-of
Identifier nodes — variable and function references
Control flow nodes — if-else, while, for, switch, return
Declaration nodes — variable declarations, function definitions, type definitions

A statically typed AST often carries a type field on each node that gets populated during semantic analysis, while an untyped AST is sufficient for early parsing stages. Modern compilers like GCC and Clang define dozens of node kinds; Clang’s AST for C++ has over 400 node types in its RecursiveASTVisitor hierarchy.

Building an AST During Parsing

AST construction happens incrementally as the parser recognizes grammar productions. There are two dominant strategies:

AST Construction in Recursive Descent Parsers

In a recursive descent parser, each parse method returns a pointer to a newly allocated AST node. The method for a binary expression, for instance, parses the left operand, parses the operator, parses the right operand, then allocates and returns a BinaryExprNode. This straightforward approach maps one-to-one with grammar rules and produces trees that mirror the grammar’s structure.

Recursive descent is the most common technique for hand-written parsers. The Cfront C++ compiler, GCC’s earlier versions, and many production compilers use recursive descent with AST construction interleaved. The pattern is simple enough that parser generators from ANTLR to Bison support AST construction through embedded actions.

AST Construction in Generated LR Parsers

LR parsers (Yacc, Bison, Menhir) build trees bottom-up. When a reduction fires, the semantic action pops the right-hand-side symbols’ values from the parser stack and assembles them into a new node, which is pushed as the left-hand-side nonterminal’s value. The Bison documentation demonstrates this pattern using $$ = make_node($1, $2, $3).

The Dragon Book provides a detailed example of an infix-to-postfix translator extended to build an AST: each action allocates a node, wires children from stack values, and returns the node pointer. This works seamlessly with LALR(1) parsing and produces a complete AST after the final reduction to the start symbol.

Tree Traversal Patterns

Once an AST is built, the compiler must traverse it multiple times. Each traversal performs a different task: type checking, constant folding, control flow analysis, or code generation. The fundamental challenge is separating traversal logic from node structure.

The Visitor Pattern

The Visitor pattern decouples algorithms from the AST data structure. A base Visitor class declares a visit method for each node type. Concrete visitors override selected visit methods to implement specific analyses. The Gang of Four Design Patterns book describes this pattern, and it is ubiquitous in compiler infrastructure.

Clang’s RecursiveASTVisitor demonstrates the visitor pattern at scale. It provides pre-order and post-order visit hooks for each AST node kind, along with automatic traversal of child nodes. A Clang-based linter subclasses RecursiveASTVisitor, overrides VisitBinaryOperator to check for suspicious patterns, and lets the framework handle tree navigation. This keeps analysis code focused on the logic rather than traversal mechanics.

Iterators and Tree Walking

Not every traversal needs a full visitor. Simple passes — like renaming all variables in a scope — can use explicit tree iterators or recursive functions that match patterns with switch or pattern matching. Languages like Rust (with enum and match) and OCaml (with algebraic data types) make direct tree walking elegant. In Rust, a function that folds constants might look like:

fn fold_constants(node: &Expr) -> Expr {
    match node {
        Expr::BinaryOp(op, l, r) => {
            let lf = fold_constants(l);
            let rf = fold_constants(r);
            match (&lf, &rf) {
                (Expr::Literal(a), Expr::Literal(b)) => Expr::Literal(a op b),
                _ => Expr::BinaryOp(op.clone(), Box::new(lf), Box::new(rf)),
            }
        }
        _ => node.clone(),
    }
---

This style is concise, type-safe, and avoids the visitor boilerplate.

Tree Transformations

Compiler optimizations are tree transformations. The AST is rewritten, node by node, into an equivalent but more efficient form. Common AST transformations include:

Constant folding — replacing 2 + 3 with 5 at compile time
Algebraic simplification — rewriting x * 0 to 0 and x + 0 to x
Dead code elimination — removing unreachable subtrees after if-statements with constant conditions
Inlining — replacing a call node with the callee’s AST body, with appropriate variable renaming

These transformations are applied in optimization passes that traverse the AST, match patterns, and rebuild subtrees. The Dragon Book dedicates an entire chapter to machine-independent optimizations that operate on intermediate representations, but many of these optimizations are equally applicable at the AST level before lowering to IR.

Copying vs. Mutating ASTs

A design decision every compiler faces: should transformations mutate the AST in place or produce a new tree? Mutation is faster and uses less memory, but makes it harder to reason about correctness because a node’s children may be transformed by a later pass that invalidates earlier assumptions. Immutable transformations — building a new tree from the old one — enable sharing unchanged subtrees (persistent data structures) and simplify debugging. Clang’s AST is immutable after construction; analyses produce annotations rather than mutating nodes. LLVM’s IR, by contrast, is explicitly mutable and uses a pass manager that runs transformations sequentially.

AST-Based Tools Beyond Compilers

The AST is not only for compilers. Modern developer tooling relies on AST access for:

Linters (ESLint, Clang-Tidy, Pylint) — pattern-match against AST nodes to enforce coding standards
Formatters (Prettier, clang-format) — reformat source by pretty-printing the CST or AST
Refactoring engines (Roslyn for C#, SwiftSyntax for Swift) — perform safe, automated code transformations
Code search (Semgrep, Comby) — match structural patterns across large codebases
Documentation generators (Doxygen, Javadoc) — extract comments and signatures from AST nodes
TypeScript’s language server — provides completions, go-to-definition, and rename refactoring through AST traversals

FAQ

What is the difference between a CST and an AST? A Concrete Syntax Tree (parse tree) preserves every token and grammar production from the source. An AST discards punctuation, grouping parentheses, and intermediate grammar nodes, keeping only the semantically meaningful structure. The expression (1 + 2) has a CST node for the parentheses; the AST has just a BinaryOp(+, 1, 2).

How is an AST represented in memory? Most compilers define a discriminated union (tagged enum or sum type) where each variant corresponds to a language construct. Nodes contain child pointers (for binary ops, control flow) or linked lists (for declaration sequences). Some implementations use arena allocation for performance.

Can ASTs be serialized? Yes. Clang can dump ASTs as JSON or YAML. Many compilers provide -ast-dump flags. Serialized ASTs are useful for debugging, tool integration, and incremental compilation.

What role does the AST play in semantic analysis? The AST is the primary input for semantic analysis. The type checker, scope resolver, and name binder all traverse the AST, annotating nodes with type information and symbol table entries. Some compilers build a separate High-Level IR after semantic analysis, while others annotate the AST directly.

Do all compilers use an AST? Most modern compilers do, but some simple compilers generate code directly from the parser’s semantic actions without ever materializing a full AST. The tradeoff is compile speed vs. optimization potential — skipping the AST saves memory but makes many transformations harder to implement.