Abstract Syntax Trees

A parse tree is an honest but exhausting witness. It records every grammar rule the parser fired, every parenthesis it matched, every single-child chain it climbed through the precedence ladder. For the expression a = b + c \times 2 that is dozens of nodes, most of which say nothing the rest of the compiler cares about. The abstract syntax tree (AST) is what you get when you throw away the derivation bureaucracy and keep only the structure: which operator applies to which operands, which statement contains which. It is the data structure on which every later phase — type checking, optimisation, code generation — actually runs.

The word that matters is abstract. A concrete syntax tree (another name for the parse tree) mirrors the grammar exactly, warts and all. An abstract syntax tree mirrors the meaning. Two grammars that describe the same language — one factored to encode precedence, one using explicit parentheses — should, and do, produce the same AST. The AST is the point in the pipeline where the compiler stops caring how you wrote something and starts caring what you wrote.

What we throw away, and why

Compare the two trees for the humble arithmetic expression. A grammar that enforces precedence with the classic E \to E + T \mid T, T \to T \times F \mid F, F \to \mathbf{id} \mid ( E ) forces the parser through a long chain of single-child productions (E \to T \to F \to \mathbf{id}) every time a leaf is just an identifier. The parse tree faithfully records all of them. The AST erases the whole chain and keeps a single leaf.

Kept in the AST	Dropped from the AST
operators & their operand structure	parentheses (structure already encodes grouping)
which node is the root of a subexpression	single-child "chain" productions (E{\to}T{\to}F)
literals, identifiers, their values	separators, semicolons, layout, comments
the shape that determines evaluation order	the particular grammar rules that were fired

The payoff is not merely smaller trees — it is uniformity. Every downstream pass can assume that a Binary node has exactly a left child, an operator, and a right child, with no interleaved precedence scaffolding to skip over. The precedence work was done once, by the parser, and is now baked silently into the tree's shape.

The collapse, drawn

Watch the concrete parse tree for a = b + c \times 2 fold into its AST. On the left, the full derivation, with its assignment, expression, term and factor levels and their single-child chains. On the right, the same expression as an AST: an = at the root, a + and a × beneath, and four leaves. Same meaning, a third of the nodes.

Notice how the × sits below the + on the right subtree — precedence is now purely positional. To evaluate, a post-order walk multiplies c \times 2 first (deeper), then adds b, then assigns to a. No precedence table is consulted; the tree is the precedence.

Designing the node types

An AST is a family of node types, one variant per language construct. In a typed language the natural encoding is a discriminated union (a "sum type"): a tag field says which variant this is, and the rest of the fields are specific to that variant. Traversals switch on the tag; the compiler's exhaustiveness checker then guarantees you handled every kind of node.

// One variant per construct. The `kind` tag discriminates the union. type Expr = | { kind: "num"; value: number } | { kind: "var"; name: string } | { kind: "binary"; op: "+" | "-" | "*" | "/"; left: Expr; right: Expr } | { kind: "assign"; target: string; value: Expr };

Two design instincts guide the shape. First, make illegal states unrepresentable: a binary node always has two operand fields, so you can never build a half-formed +. Second, keep only semantic children: there is no field for the parentheses in (b + c) \times 2 because the tree's shape already records that the addition happens first. Richer languages add variants — if, while, call, lambda — and often a span field carrying the source line/column so later error messages can point back at the original text.

Building the AST while parsing

You do not build the parse tree and then convert it — that would waste the very memory the AST exists to save. Instead each parser routine returns an AST node directly. In a recursive-descent parser this is delightfully natural: the function that recognises a term builds and returns a binary node; the function that recognises a factor returns a num or a var. The precedence encoded in the grammar becomes the nesting of the returned nodes — this is a first taste of syntax-directed translation, where semantic values flow up out of a parse.

// Sketch: each routine returns an Expr, so precedence becomes nesting. function parseExpr(): Expr { // handles +, - (lowest precedence) let node = parseTerm(); while (peek() === "+" || peek() === "-") { const op = next() as "+" | "-"; node = { kind: "binary", op, left: node, right: parseTerm() }; } return node; // left-associative tree, no parse-tree scaffolding }

The loop makes the tree left-leaning for a - b - c, which is exactly the left-associativity we want, and it does so without ever materialising an E \to E + T node. A bottom-up (LR) parser does the same thing through semantic actions attached to each reduction: reducing E \to E + T pops the two operand nodes off the value stack and pushes a fresh binary node.

Walking the tree: the visitor pattern

Once you have an AST, nearly everything you do to it is a traversal. You will want to walk it many times — to type-check, to constant-fold, to emit code, to pretty-print. Rather than scatter that recursion, compilers centralise it in a visitor: one dispatch on the node's tag, one handler per variant. New passes are new visitors; new node kinds add one case to each visitor (and the type checker reminds you where).

type Expr = | { kind: "num"; value: number } | { kind: "var"; name: string } | { kind: "binary"; op: "+" | "-" | "*" | "/"; left: Expr; right: Expr } | { kind: "assign"; target: string; value: Expr }; // A recursive evaluator — a visitor that folds the tree to a number. function evaluate(e: Expr, env: Record<string, number>): number { switch (e.kind) { case "num": return e.value; case "var": return env[e.name] ?? 0; case "binary": { const l = evaluate(e.left, env), r = evaluate(e.right, env); return e.op === "+" ? l + r : e.op === "-" ? l - r : e.op === "*" ? l * r : l / r; } case "assign": return (env[e.target] = evaluate(e.value, env)); } } // A second visitor — pretty-print with minimal, correctness-preserving parens. function show(e: Expr): string { switch (e.kind) { case "num": return String(e.value); case "var": return e.name; case "binary": return `(${show(e.left)} ${e.op} ${show(e.right)})`; case "assign": return `${e.target} = ${show(e.value)}`; } } // AST for: a = b + c * 2 (built as the parser would build it) const ast: Expr = { kind: "assign", target: "a", value: { kind: "binary", op: "+", left: { kind: "var", name: "b" }, right: { kind: "binary", op: "*", left: { kind: "var", name: "c" }, right: { kind: "num", value: 2 } }, }, }; console.log("pretty:", show(ast)); console.log("value: ", evaluate(ast, { b: 10, c: 3 })); // a = 10 + 3*2 = 16

Two visitors, one tree. The same structure that evaluated to 16 pretty-prints with the multiplication correctly nested inside the addition — because the nesting is the precedence. Add an if node tomorrow and TypeScript's exhaustiveness check will flag both switches until you handle it. That safety is why discriminated unions are the AST representation of choice.

Surprisingly close to it. Many production compilers define their AST as the boundary between a language-specific front end and everything after. Clang builds a C/C++/Objective-C AST that its analyses share; Rust and Swift both lower a surface AST into a simpler intermediate form. The trick that makes this work is that the AST already discarded the syntactic quirks — commas, layout, keyword spellings — and kept only the semantic skeleton, and skeletons across imperative languages look remarkably alike. It is why "a expression tree with typed nodes" is one of the most reused ideas in all of compiler engineering.

The classic misunderstanding is to think the AST is "the parse tree, tidied up" — same information, fewer keystrokes. It is not. The AST deliberately discards information the parse tree carried: the exact derivation, the single-child precedence chains, the parentheses. That is a feature, not a lossy accident. What it must preserve is structure — which operator governs which operands, in what order they nest. Get that backwards (drop a needed grouping, or keep the derivation "just in case") and you have either a wrong program or a bloated one. The rule of thumb: if two source texts mean the same computation, they should produce the same AST; if they mean different computations, they must not.