ASTtypical

The Abstract Syntax Tree

The representation every later phase is written against: `let x = 1 + 2;` stops being ten tokens and becomes a declaration holding an addition holding two literals. The punctuation is gone; the containment is everything.

The question

What is an AST actually, and what does it know that the token stream did not?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A rooted, ordered tree whose nodes are language constructs — declarations, statements, expressions — each carrying the source span it came from. It exists to answer one question the token stream cannot even phrase: *what is applied to what*. Which operand belongs to which operator, which statements sit inside which block, which expression initialises which declaration. A token list is flat, and flatness has no way to say "contains".

What this phase may assume or do

The tree builder is entitled to assume the tokens it consumes form a syntactically valid program under the grammar, because the parser has already rejected everything else. It is entitled to assume nothing beyond that: not that x is a new name, not that 1 + 2 has a type, not that the declaration is reachable. A frontend that rejects let x: int = "hi"; during tree construction has done semantic work one phase early, and pays for it in [[error-recovery]] — it can no longer report the syntax error and the type error in the same run.

Key points

  • The AST answers "what is applied to what". Tokens are flat and cannot express containment at all.
  • It is *abstract* because it drops everything that existed only to guide the parser: parentheses, semicolons, punctuation, grammar-rule nodes.
  • (1 + 2) and 1 + 2 have the same AST. That is a feature for an optimizer and a fatal defect for a formatter.
  • Spans are the only bridge back to the text. A node without a span cannot produce a diagnostic that points anywhere.
  • The tree asserts structure and checks nothing. Everything semantic is the next phase's job, deliberately.
  • It is an ordinary ordered n-ary tree, so ordinary tree algorithms and ordinary tree problems both apply.

Ten tokens, five nodes

Take let x = 1 + 2;. The lexer hands the parser ten tokens: let, x, =, 1, +, 2, ; — seven, in fact, and not one of them says that 1 and 2 are the operands of the + rather than of the =. The grammar says that, and the parser applies the grammar. What comes out is a tree with five interesting nodes and no punctuation at all.

Read the tree below as containment. The VariableDeclaration *contains* its initializer. The BinaryExpression *contains* both literals. Every question a later phase asks — what type does this initializer have, is this name already declared, can this expression be folded — is a question about a subtree, and subtrees are the only thing the AST is made of.

AST for let x = 1 + 2; — immediately after parsing, before any name or type is known
AST — only what later phases match on
VariableDeclaration“let x = 1 + 2;”— The `let` keyword and the `;` have no node of their own. They did their job — they told the parser which production to take — and the tree records the outcome, not the evidence.
├── Identifier x“x”— The declared name, as text. It does not yet refer to anything: creating the binding is `[[name-resolution]]`, one phase later.
└── BinaryExpression +“1 + 2”— The initializer. That it is the initializer is expressed by *where it sits*, not by a field called "initializer" — though most implementations name the field too.
├── NumberLiteral 1“1”
└── NumberLiteral 2“2”

Read it asNothing here is checked. x may already be declared in this scope. 1 + 2 may be an addition the language does not define for these operands. The tree is a well-formed statement of structure and an assertion of nothing else — which is exactly what makes it a good input to a phase whose entire job is checking.

What the tree deliberately forgets

typicalMainstream hand-written frontends (Clang, rustc, the TypeScript compiler) build an AST directly and never materialise a parse tree at all — the parse tree above is a teaching device showing what would have been there. Parser generators such as ANTLR and tree-sitter do the opposite: they produce a full concrete tree and leave the abstraction to you, which is exactly what makes them good for editors and awkward for optimizers.

The word doing the work in "abstract syntax tree" is *abstract*. A parse tree — the tree the grammar literally derives — has a node for every production traversed and every token consumed, punctuation included. For our seven tokens that is a dozen nodes, most of which exist only to record that the parser went through Expression -> Additive -> Primary on its way to the literal.

An AST throws all of that away, and the throwing away is the design. (1 + 2) and 1 + 2 produce the *same* AST, because parentheses exist to tell the parser how to build the tree and have nothing to say once it is built. So do semicolons, so does whitespace, so in most compilers do comments. Every one of those is recoverable from the source text via spans, and unrecoverable otherwise — which is why a formatter cannot be written against an AST and needs a [[concrete-syntax-tree]] instead.

The parse tree for the same input, for contrast
Parse tree — every grammar rule and every token
Statement
├── token 'let'“let”— A node whose entire content is "the keyword was here".
├── token IDENT 'x'“x”
├── token '='“=”
├── Expression
│ └── Additive
│ ├── Primary -> NUMBER 1“1”
│ ├── token '+'“+”
│ └── Primary -> NUMBER 2“2”
└── token ';'“;”

Read it asTen nodes instead of five, and the extra five carry no information a later phase would ever match on. Expression -> Additive is a fact about the grammar, not about the program. [[parse-tree-vs-ast]] is the lesson that argues this properly; the point here is that the AST is the parse tree with the grammar's own bookkeeping deleted.

Why every later phase wants a tree

A tree is the cheapest structure that supports the two operations the rest of the frontend lives on: *recursive descent into subterms*, and *local pattern matching*. Type checking a BinaryExpression means asking its two children for their types and consulting a rule — a purely local operation once the children have answered. Constant folding means matching the shape BinaryExpression(+){NumberLiteral, NumberLiteral} and replacing it. Neither is expressible over a flat list without first reconstructing the nesting, which is to say without first building the tree.

This is the same n-ary tree from the data-structures course, with the same traversals and the same recursion depth problem. [[ast-traversal]] makes that connection concrete; it is worth noticing early, because it means every intuition about tree recursion — including that deep input blows the stack — transfers directly to compilers.

  • Ordered: the children of a BinaryExpression are left and right, and swapping them changes the program.
  • N-ary, not binary: a Block has as many children as it has statements, and a CallExpression has as many argument children as were written.
  • Spans on every node, so any later phase can point at the source — see [[spans-and-ranges]].
  • No back edges. Loops in the *program* are ordinary nodes; the tree itself is acyclic, which is what makes naive recursion terminate.

How it works

The steps, in the order the compiler takes them.

  • The parser consumes tokens against the grammar and, at each completed production, allocates a node of the corresponding kind.
  • Each node records the span covering the tokens it was built from — usually the start of its first token to the end of its last.
  • Operator precedence and associativity decide the *shape*: the loosest-binding operator ends up nearest the root, so let is above = is above +.
  • Tokens that carried only structural information — delimiters, keywords already reflected in the node kind — are consumed and dropped.
  • The completed tree is handed to semantic analysis, which walks it and attaches symbols and types without changing its shape.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • Precedence is wired wrongly, so 1 + 2 * 3 builds as (1 + 2) * 3. Nothing errors, the program compiles, and it returns 9 instead of 7 — the arithmetic is simply wrong, forever, in every program that uses that operator pair.
  • A node is built with the span of the wrong token, and every error message about that construct underlines the following line. Users report "the compiler points at the wrong place" and nobody can reproduce it from the message alone.
  • Comments are dropped with no trivia record, and the formatter built on the same tree silently deletes every comment in the file the first time someone runs it on save.
  • The parser recurses once per nesting level and a generated file with ten thousand nested array literals overflows the stack. The compiler crashes with no diagnostic at all, which reads to the user as "the compiler is broken" rather than "this input is deep".
  • The same source construct is represented by two different node kinds depending on which grammar path reached it, and a later pass handles one and silently ignores the other. The feature works in most files and mysteriously does not in one.

When it helps

  • Any analysis that is naturally recursive over program structure: type checking, scope construction, constant folding, complexity linting.
  • Anything that must match a shape rather than a string — "a call to eval whose argument is not a literal" is a two-node pattern on an AST and an unwinnable regex on text.
  • Refactoring tools, because a rename is a tree query plus a set of span edits, and both halves are exact.

When it hurts

  • Formatting and any other whole-text-fidelity task. The AST has already discarded the things a formatter is being asked to preserve; you need a concrete syntax tree.
  • Flow-sensitive questions. "Is this variable assigned before use on every path" is not a question about a subtree, and answering it on the AST means simulating control flow badly. That is what [[control-flow-graph]] exists for.
  • Anything cross-file. An AST is per-file by construction; whole-program questions need a symbol table or a module graph on top of it.

What it costs

Every one of these is paid by something.

  • Abstracting away punctuation buys every later pass a smaller, cleaner set of shapes to match on, and costs the ability to reproduce the source text. Tools that need both end up maintaining two trees, or one tree with a trivia side-table, and paying the memory for it.
  • Attaching a span to every node buys diagnostics, jump-to-definition and source maps, and costs eight to sixteen bytes on every node in a structure with millions of nodes — as well as the discipline of maintaining spans through every transformation that follows.
  • Making the tree the interface between parser and everything else buys phase independence, and costs a hard compatibility surface: every change to a node kind ripples into every pass, every lint rule and every third-party tool written against it.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Keep the concrete syntax tree and derive views from it. Roslyn and tree-sitter do this: one lossless tree, from which an abstract view is computed on demand. You pay memory and node count; you gain formatters, editors and exact round-tripping — see [[concrete-syntax-tree]].
  • Skip the tree entirely and emit code during parsing. A single-pass compiler generates bytecode as it parses, which is how classic Pascal compilers and Lua's reference implementation work. Extremely fast and small; you give up almost all optimization and most good diagnostics, because you can never look at a construct twice.
  • Go straight from tokens to a graph-shaped IR, as some JIT frontends do, when there is no need for source-level analysis at all and the tree would be built only to be discarded.

See it for yourself

The flag, dump or tool that shows you this directly.

  • C / C++: clang -Xclang -ast-dump -fsyntax-only file.c prints the tree with node kinds, types and source ranges.
  • Python: python -c "import ast,sys; print(ast.dump(ast.parse(open(sys.argv[1]).read()), indent=2))" file.py.
  • JavaScript / TypeScript: paste into astexplorer.net and switch parsers — the same source under acorn, babel and typescript gives visibly different trees for the same program, which is the fastest way to internalise that node design is a choice.
  • Rust: rustc -Z unpretty=ast-tree file.rs on a nightly toolchain.
  • Our AST explorer at /compilers/ast builds the tree for whatever you type using the real AtlasLang parser, with every node linked back to its source span.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The AST is the source code in tree form." It is the source code with everything the parser no longer needs deleted. You cannot print it back out and get your file.
  • "The parser checks the program." The parser checks that the program is *grammatical*. let x = x; and let x: int = "hi"; are both perfectly grammatical and both wrong, and neither is the parser's business.
  • "Every language construct is one node kind." Most frontends have several nodes per surface construct and several surface constructs per node — how many, and which way round, is the subject of [[ast-node-design]].
  • "If the AST is right, the compiler is right." The AST is right about structure. It is silent on names, types, effects, reachability and everything else that makes a program mean something.

Misconceptions

The claim, and what is actually true.

The AST and the parse tree are the same thing with different names.
A parse tree records how the grammar derived the input, including a node per production and per token. An AST records what the program says. The first is what an editor wants; the second is what a compiler wants.
You can regenerate the source file from the AST.
You can generate *a* source file with the same meaning. Comments, formatting, redundant parentheses and the user's choice of x+1 over x + 1 are all gone unless the tree was designed to keep them.
An expression's type is part of its AST node.
Not until something computes it. A freshly parsed tree has no types anywhere; [[annotated-ast]] is the tree after the type checker has been through it.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A token list says which characters group together. It cannot say which groups belong to which. The AST is the structure that says it: a tree whose nodes are program constructs and whose edges mean "contains". let x = 1 + 2; becomes a declaration node holding an addition node holding two number literals, and the semicolon, the equals sign and the let keyword vanish because their only job was to tell the parser which shape to build.

practical

Dump the tree before you theorise about a bug. If the tree for a + b * c has the multiplication under the addition, precedence is right and the bug is later. If a diagnostic points at the wrong line, the node's span is wrong and the bug is in tree construction, not in the diagnostic. clang -Xclang -ast-dump and python -m ast take seconds and settle these questions outright — far faster than reasoning about which phase "should" be responsible.

advanced

The interesting property of an AST is not its shape but its *audience*. A tree built only for a code generator can be as lossy as you like. The moment a formatter, a linter or a language server is written against the same tree, every discarded token becomes a bug report, and retrofitting trivia into an established node type is one of the more painful refactors a compiler team can undertake. This is why frontends that expect to serve editors — Roslyn, rust-analyzer, tree-sitter — start lossless and abstract downward, and it is the whole argument of [[ast-as-shared-infrastructure]].

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThat an AST discards parentheses is true of mainstream compiler frontends, which have no use for them after parsing. It is false of formatter-oriented trees: Roslyn, tree-sitter and Prettier's parsers all retain parentheses (or enough trivia to reconstruct them) precisely because deleting a user's redundant parentheses on save is unacceptable behavior for an editor.
implementationThe node names used here — VariableDeclaration, BinaryExpression, NumberLiteral — follow the ESTree convention that JavaScript tooling standardised on. Clang calls the same things VarDecl, BinaryOperator and IntegerLiteral; rustc calls them Local, ExprKind::Binary and LitKind::Int. The shapes correspond; none of the names do.
simplifiedOur tree shows the declared name as a child Identifier node. Many real implementations store it as a plain string or interned symbol field on the declaration node instead, which saves an allocation and a traversal step at the cost of the name no longer being a uniformly-addressable node that generic tooling can point at.

If you were asked this in an interview

  • What information is in an AST that is not in the token stream, and what is in the token stream that is not in the AST?
  • Two source files differ only in parentheses and produce identical ASTs. Name a tool for which that is correct behavior and a tool for which it is a bug.
  • Where would you store source spans, and what breaks if you decide not to store them?

Connections

DSAn-ary-treebinary-treedfs
Domains that do not exist yet
  • Software Design — Modelling a domain as a closed set of data shapes rather than as behavior
    An AST is the canonical example of a data model designed for exhaustive case analysis — the same instinct behind algebraic data types in application code. The general design argument lives there; the compiler-specific consequences of getting it wrong live in [[ast-node-design]].