Abstract Syntax Trees

A parse tree (concrete syntax tree, CST) is the literal derivation history of a string under a grammar: it has one internal node for every grammar rule invoked, including rules that exist purely for disambiguation. Parsing `2 + 3 4` under a standard expression grammar produces a parse tree with nodes for `Expr`, `Term`, `Factor`, and terminal tokens for `+`, ``, parentheses if present, and so on — often five or six levels deep for a two-operator expression. An Abstract Syntax Tree collapses this into the minimal structure that preserves meaning. The AST for the same expression has exactly three internal decisions worth recording: "add these two things," and "multiply these two things," attached to leaves `2`, `3`, `4`. Grammar-level distinctions between `Expr`, `Term`, and `Factor` — which exist only to encode precedence in the grammar — vanish, because precedence is now encoded directly in the shape of the tree (multiplication is nested inside addition, so it evaluates first). Formally, an AST is a tree $T = (V, E, \text{label})$ where each node $v \in V$ is labeled with a syntactic construct (an operator, a statement kind, a literal, an identifier) and its children are the sub-constructs that construct depends on. Two properties define a good AST design: 1. Structural sufficiency — the tree contains everything semantic analysis needs: operator identity, operand order (for non-commutative or side-effecting operators), scoping structure for blocks, and literal values. Nothing about how the parser recognized this survives. 2. Redundancy elimination — no unit-production nodes (a node with exactly one child that adds no information), no explicit parenthesis nodes (grouping is implicit in tree shape), and no grammar nonterminal that exists solely for precedence (`Term`, `Factor`, `Primary`) is materialized as a distinct node kind. This connects directly to what comes immediately after parsing: Semantic Analysis walks the AST to check types and scoping rules, and Symbol Tables are populated by visiting declaration nodes in the AST in a fixed traversal order. The AST is therefore not just a record of parsing — it is the contract between the syntactic front end and everything semantic that follows.

There are two standard strategies for building an AST, and most real compilers use a hybrid.

Strategy 1 — Action-directed construction (bottom-up or top-down, interleaved with parsing). Each grammar production is annotated with a semantic action that builds a tree node from the values (sub-trees) already built for the symbols on its right-hand side. In an LALR parser this is the classic "synthesized attribute" approach: whenever the parser reduces by a production, it pops the child subtrees off a value stack (parallel to the parser's state stack) and pushes a new node built from them. In a recursive-descent parser, each parsing function returns the subtree it built, and the caller assembles a parent node from its children's return values.

Strategy 2 — Post-hoc simplification. Build the full parse tree first, then run a separate tree-transformation pass that deletes unit-production nodes, collapses redundant nonterminals, and re-labels nodes with semantic tags. This is simpler to reason about but wastes memory and time on structure that is immediately discarded, so production compilers almost always prefer Strategy 1. The key technical device that makes Strategy 1 work cleanly for expressions — where precedence and associativity must be reflected in tree shape — is to make tree-shape mirror grammar-derivation-shape only at the points where it matters (operator nesting), while collapsing everything else. Below is a recursive-descent AST builder for arithmetic expressions with `+ - /`, correctly handling precedence and left-associativity, followed by pseudocode for the reduce-time construction used in LALR-style parsers. ``` // Grammar (already left-factored and precedence-layered // exactly as produced when preparing for recursive descent): // Expr -> Term (('+' | '-') Term) // Term -> Factor (('' | '/') Factor) // Factor -> NUMBER | '(' Expr ')' function parseExpr(tokens): left = parseTerm(tokens) while peek(tokens) in {'+', '-'}: op = consume(tokens) right = parseTerm(tokens) left = makeNode(op, left, right) // left-associative nesting return left function parseTerm(tokens): left = parseFactor(tokens) while peek(tokens) in {'', '/'}: op = consume(tokens) right = parseFactor(tokens) left = makeNode(op, left, right) return left function parseFactor(tokens): if peek(tokens) == NUMBER: tok = consume(tokens) return makeLeaf(NUM, tok.value) // no "Factor" node survives else if peek(tokens) == '(': consume(tokens) // '(' is discarded, not stored e = parseExpr(tokens) expect(tokens, ')') // ')' is discarded, not stored return e // parens leave no trace in the AST else: error("unexpected token") function makeNode(op, left, right): return TreeNode(kind = op, children = [left, right]) function makeLeaf(kind, value): return TreeNode(kind = kind, value = value, children = []) ``` Notice three deliberate design choices that make this an AST builder rather than a parse-tree builder: the `Factor` and `Term` nonterminals never become tree nodes (only their semantic content — a number or an operator application — becomes a node); parentheses are consumed by the parser but never stored, because grouping is already encoded by where `parseExpr` was called; and the `while` loops build <strong>left-leaning</strong> trees, which is what correctly encodes left-associativity for `-` and `/` (getting this wrong is the single most common AST bug, discussed below). For LALR/LR parsing, tree construction attaches to reductions instead of recursive calls: ``` // Parallel value stack: valueStack[i] holds the AST subtree // associated with parserStack[i]. On shift, push a leaf. // On reduce by production A -> X1 X2 ... Xk, pop k values, // apply the production's semantic action, push the result. function onShift(token): push(valueStack, makeLeaf(token.kind, token.value)) function onReduce(production): k = length(production.rhs) children = pop(valueStack, k) // pops k values, in order result = production.action(children) // builds AST node (or passes one through) push(valueStack, result) // Example semantic actions: // Expr -> Expr '+' Term : action(c) = makeNode('+', c[0], c[2]) // Expr -> Term : action(c) = c[0] // unit production: pass through, no new node // Factor -> '(' Expr ')' : action(c) = c[1] // parens discarded // Factor -> NUMBER : action(c) = makeLeaf(NUM, c[0].value) ``` The unit-production action `Expr -> Term : action(c) = c[0]` is the mechanism that erases grammar-only distinctions: it simply forwards the child subtree without wrapping it, so no `Expr`-vs-`Term`-vs-`Factor` node kind ever appears in the final tree — only `+`, ``, and `NUM` node kinds do.

Time. Building an AST alongside parsing costs $O(1)$ additional work per token in a grammar with a bounded number of productions per symbol, and $O(1)$ amortized work per reduction in an LALR parser (each reduction pops a bounded number of stack values and pushes one). Since parsing itself is $O(n)$ for recursive descent on an $LL(1)$ grammar and $O(n)$ for $LR(1)$/LALR(1) parsing, AST construction adds only a constant factor: total time remains

for input of $n$ tokens. This is not an accident: every token is shifted exactly once and every production is reduced exactly once in a deterministic bottom-up parse (or recursively descended into exactly once), so the number of `makeNode`/`makeLeaf` calls is bounded by the number of grammar symbols processed, which is itself $O(n)$.

Space. A naive parse tree has size proportional to the number of grammar-rule applications, which can be $\Theta(n)$ but with a constant factor equal to the grammar's derivation depth per token (often 3–6× for a typical expression grammar with precedence layering). An AST has size bounded by the number of semantically meaningful constructs, which is always $\leq$ the parse-tree size and typically much smaller — every unit production and every parenthesis pair is eliminated. So AST space is still $O(n)$, but with a smaller hidden constant, and — crucially — the constant does not grow when the grammar is refactored to add more precedence levels (adding a `Shift`, `BitOr`, `BitAnd` layer to disambiguate `<<`, `|`, `&` adds parse-tree nodes but adds zero AST nodes, since each layer collapses via unit-production pass-through).

Correctness. The correctness claim for an AST builder is a structural invariant, not just "it doesn't crash": > Invariant: for every subexpression $e$ that the source grammar assigns evaluation order $O$ (via precedence and associativity), the constructed tree nests $e$'s AST node at a depth, and on a side, consistent with $O$ — specifically, an operator of higher precedence appears strictly deeper than an adjacent lower-precedence operator that it is an operand of, and for a left-associative operator sequence $a \odot b \odot c$, the tree is $(a \odot b) \odot c$, not $a \odot (b \odot c)$. Proof sketch. By induction on the grammar layering. The base case is a single `Factor`/`Primary`, which becomes a leaf trivially satisfying the invariant (no operators, nothing to nest). For the inductive step, consider `Expr -> Term (('+'|'-') Term)`: each iteration of the loop in `parseExpr` takes the already-built left subtree (which by the inductive hypothesis correctly nests all higher-precedence `Term` structure) and wraps it as the <strong>left child</strong> of a new `+`/`-` node, with the next `Term` as the right child. Because this wrapping happens iteratively — the previous result becomes the new left child on each pass — a sequence `a - b - c` builds `(a-b)` first, then wraps it as `((a-b) - c)`, which is exactly left-associative nesting. Precedence correctness follows because `parseTerm` (handling ``/`/`) is only ever called as a subroutine of `parseExpr`, so a `` node can never end up as a parent of a `+` node — it can only appear as a child, i.e., strictly deeper, matching the invariant. $\blacksquare$ This same inductive argument, run in reverse (starting from the innermost reduction and working outward), justifies the LALR-style semantic-action construction: because the parser reduces the innermost, highest-precedence handle first (a structural fact guaranteed by the LALR(1) parsing algorithm itself, established when studying <a class="wiki-link" href="/wiki/cs-pl-lr-lalr-parsing" data-track="wiki_article.body.wiki_link">LR and LALR Parsing</a>), the subtree for a higher-precedence operator is always built and pushed onto the value stack before* the lower-precedence node that consumes it, guaranteeing the same depth ordering.

Tradeoffs. Building a fully separate, redundancy-free AST costs implementation complexity: every grammar production needs an explicit semantic action, and unit-production pass-through actions are easy to forget (silently producing a parse tree wearing an AST's name). The alternative — skip AST construction and interpret/compile directly from the parse tree or even during parsing (a "syntax-directed one-pass" compiler) — saves a data structure but tightly couples every later phase to the grammar's shape, making the front end far harder to extend or retarget. Nearly all serious compilers accept the AST's modest construction and memory cost for this decoupling.

Trace the recursive-descent builder above on `8 - 2 - 3 4`, tokenized as `NUM(8) '-' NUM(2) '-' NUM(3) '' NUM(4)`.

The resulting tree: ``` - / \

• *

/ \ / \ 8 2 3 4 ``` Two correctness facts are visible directly in this trace and matter for grading a student's implementation: 1. Left-associativity of `-` is preserved: `8 - 2 - 34` means `(8 - 2) - (34) = 6 - 12 = -6`, not `8 - (2 - 12) = 18`. The tree shape gives the right answer only because the loop in `parseExpr` nests the running `left` value on the left at every iteration (step 3 → step 6), never on the right. 2. Precedence is preserved without any explicit "precedence number" stored anywhere in the tree: `` is structurally a child of the second `-` node (depth 2), never a parent of any `-` node, purely because `parseTerm` is a sub-call of `parseExpr` and never the reverse. A second, smaller trace exposes a subtlety students often miss: parenthesized input `(8 - 2) - 3`. When `parseFactor` sees `(`, it consumes it, calls `parseExpr` recursively (building `(8-2)` exactly as in steps 1–3 above), and then consumes `)` — but <strong>neither parenthesis becomes a node</strong>. The returned subtree is identical in shape to what an unparenthesized `8 - 2` would produce inside a larger expression. This confirms the design claim from the overview: grouping is encoded by when `parseExpr` is called and where* its result is plugged in as a child, never by a dedicated parenthesis node — the AST for `(8-2)-3` and a hypothetical grammar variant that made grouping the default left-to-right order would be structurally indistinguishable, exactly as intended, since both mean the same thing.

The AST as a distinct compiler artifact emerged from the formalization of syntax-directed translation in the 1960s and 1970s, growing out of work on formal grammars, parsing theory, and denotational semantics that made it natural to separate "recognizing" a program from "interpreting" its structure.

Every mainstream compiler and interpreter uses an AST (or a close variant) as its front-end output. Clang/LLVM builds a rich AST with full source-location and type-annotation fields, which downstream tools (static analyzers, refactoring engines, IDE tooling like `clangd`) traverse directly without re-parsing. javac builds an AST that survives, largely unmodified, as the input to Java's annotation processors and to bytecode generation. V8 and other JavaScript engines build an AST as the direct input to their baseline interpreters and JIT tier-up decisions — the same tree structure discussed here is what V8's Ignition interpreter walks. Linters, formatters (`clang-format`, `Prettier`, `gofmt`), refactoring tools, and static analyzers (ESLint, SonarQube) all operate by parsing source into an AST, transforming or querying it, and — for formatters — pretty-printing it back to text, which is only tractable because the AST is compact and free of grammar noise. Database query planners similarly parse SQL into an AST-like expression tree before optimization. In every one of these systems, the AST is the boundary artifact: everything before it is grammar and tokens; everything after it — Semantic Analysis, type checking, Symbol Tables construction, optimization, code generation — is meaning.

:::quiz[Why is unit-production pass-through (e.g., `Expr -> Term : action(c) = c[0]`) essential for LALR-style AST construction?]

• It improves parsing speed by skipping tokens
• It resolves shift-reduce conflicts in the LALR table
• Without it, every grammar-only nonterminal would materialize as its own tree node, turning the AST back into a parse tree ✓
• It is only needed for right-associative operators

Ask the tutor: How would you extend this AST design to represent short-circuit boolean operators (`&&`, `||`) so that evaluation order and skipped side effects are preserved correctly?