An abstract syntax tree (AST) is a tree-shaped representation of the syntactic structure of a program or expression. Its nodes represent constructs such as literals, variable references, operations, declarations, and statements, while its edges represent how those constructs contain or combine with one another. Unlike a representation that records every grammatical step or punctuation mark, an AST omits details that are unnecessary for its intended purpose. ASTs are widely used by compilers, interpreters, and development tools to analyze, transform, and execute source code.
Structure and abstraction
An AST describes a program in terms of the constructs recognized by a programming language. A node generally has a kind, identifying the construct it represents, and fields holding its components. For example:
- A literal node stores a value, such as an integer or a string.
- A variable-reference node stores an identifier.
- A binary-operation node stores an operator and two operand expressions.
- A conditional node stores a condition and its alternative branches.
- A function-declaration node stores parameters, a body, and possibly a return-type annotation.
Children are often ordered or assigned distinct roles. The left and right operands of subtraction cannot be exchanged without potentially changing the expression’s meaning.
Consider the statement:
result = a + 3 * b;
One possible AST is:
Assignment
├── target: Name("result")
└── value: Add
├── left: Name("a")
└── right: Multiply
├── left: IntegerLiteral(3)
└── right: Name("b")
The tree makes the grouping explicit: multiplication is nested within addition. The equals sign becomes the assignment node’s kind, while the semicolon need not appear at all.
“Abstract” is relative to the representation’s purpose. One AST may preserve parentheses, comments, or literal spellings, while another discards them. Some representations include separate nodes for expression statements or argument lists; others store those components directly in fields. There is no single universal AST format.
Relationship to concrete syntax
Parse trees and concrete syntax trees
A parse tree records how an input is derived from the grammar of a formal language. It commonly includes grammar-specific intermediate nodes and terminals such as keywords and punctuation. The term concrete syntax tree, or CST, is often used for a representation close to the written syntax, although exact conventions differ among tools.
An AST instead emphasizes language constructs over the grammar used to recognize them. A grammar might introduce several layers of rules to express precedence; an AST can replace those layers with directly nested operation nodes.
For example, assuming ordinary arithmetic rules, these expressions may produce the same AST:
a + b * c
a + (b * c)
(a) + ((b) * c)
Their redundant parentheses differ, but their grouping is identical. By contrast:
(a + b) * c
has multiplication at the root and addition as one of its children.
This distinction makes ASTs convenient for analysis but can make them unsuitable for exact reproduction of the original text. Whitespace, comments, quote style, and redundant parentheses may have been lost. Tools that require faithful source preservation often use a lossless syntax tree or retain tokens and source text alongside the AST.
Syntax is not full semantics
An AST captures structural relationships, not necessarily the complete meaning of a program. A node containing x + y does not by itself establish:
- Which declarations
xandyrefer to. - Their types.
- Whether
+denotes numeric addition, string concatenation, or an overloaded operation. - Whether evaluating an operand has side effects.
- Whether the expression is valid in its surrounding context.
Those questions require additional analysis and the rules of the language. AST structure also does not imply a particular evaluation order: evaluation order is determined by language semantics, not merely by the order in which children are stored.
Construction
AST construction usually takes place in a compiler or interpreter’s front end.
- Lexical analysis. A lexer groups source characters into tokens such as identifiers, literals, and operators.
- Parsing. A parser recognizes how those tokens form expressions, statements, and larger constructs.
- Tree construction. The parser or a subsequent transformation creates AST nodes representing the recognized constructs.
This is a common organization, not a mandatory pipeline. A parser may construct the AST directly, without creating a complete parse tree first. Scannerless parsers can operate without a separate lexer, and some systems use multiple successive syntax representations.
Precedence and associativity guide tree construction. Under ordinary left-associative subtraction, a - b - c becomes (a - b) - c, not a - (b - c). A language with ambiguous syntax must resolve that ambiguity through grammar rules, parsing conventions, contextual information, or an explicit ambiguity representation before obtaining one definitive AST.
ASTs may also be created programmatically. Code generators, transformation tools, and macro systems can construct trees without first producing textual source code.
Representation and annotations
ASTs are commonly implemented using classes, tagged records, or algebraic data types. Each node kind defines the fields appropriate to that construct. This is an application of data-structure design: the representation should make valid combinations easy to express and invalid combinations difficult to construct.
Nodes often carry additional metadata, including:
- Source-file identifiers and source ranges.
- Resolved declaration references.
- Inferred or declared types.
- Compiler-generated identifiers.
- Diagnostic information.
- Links to comments or tokens.
Source locations allow a tool to connect an internal construct to a position in the original file. They are especially important for error messages and automated edits. Nodes generated by transformations may need synthetic locations or provenance pointing back to the source constructs from which they arose.
Although called a tree, a practical AST may contain parent pointers, shared subtrees, and references to declarations or type objects. The syntactic containment relation can remain tree-shaped even when the complete in-memory structure is a graph.
Untyped and typed ASTs
An untyped AST primarily records syntax. A typed AST additionally records information established through a language’s type system, sometimes using distinct node kinds for constructs that were initially syntactically identical.
Name resolution connects identifier occurrences to declarations. Type checking establishes whether operations and combinations of expressions are permitted. Implementations may attach these results directly to AST nodes or store them in separate tables.
The distinction is not absolute: an untyped tree may still contain explicit type annotations written by the programmer, while a typed tree may also contain inferred types absent from the original source.
Traversal and transformation
Many AST operations use recursive traversal. A traversal visits a node and its descendants, either inspecting them or producing a replacement structure.
Typical operations include:
- Collection: finding declarations, calls, or identifier occurrences.
- Validation: checking structural or language-specific constraints.
- Rewriting: replacing a construct with another representation.
- Pretty-printing: generating readable source text.
- Evaluation: computing the behavior of expressions or statements.
Visitor interfaces and pattern matching are common ways to dispatch behavior according to node kind.
A traversal that visits each of nodes once and performs constant work per node takes time. For a recursive implementation, auxiliary traversal space is typically , where is tree height, excluding the stored tree and any generated output. Very deeply nested input can therefore require an explicit traversal stack or other safeguards.
Correctness of transformations
A structurally valid rewrite is not necessarily a behavior-preserving one. Replacing x * 0 with 0, for example, may be invalid if evaluating x has observable effects or if the language’s arithmetic rules make the results differ.
Transformations that introduce or move variables must also preserve binding relationships. A newly introduced name can accidentally capture an existing reference. Correct rewriting therefore requires attention to scope, types, evaluation order, exceptions, and other semantic properties—not just matching node shapes.
Role in compilers and interpreters
An AST provides a convenient interface between syntax recognition and later processing. It exposes program structure without forcing each subsequent phase to interpret punctuation and grammar productions again.
A compiler may perform semantic checks and simple transformations on an AST before lowering it into another intermediate representation. Lowering often makes implicit behavior explicit or replaces high-level constructs with simpler operations. A loop, for example, may eventually be represented using branches and jumps.
Representations such as a control-flow graph emphasize possible execution paths rather than source nesting. They are often better suited to optimization and analyses involving control flow. An AST can itself serve as an intermediate representation, but the terms are not interchangeable: not every intermediate representation is an AST.
An interpreter may directly evaluate AST nodes, or it may first translate them into virtual-machine instructions or another executable form. Using an AST does not by itself determine whether a language implementation is compiled or interpreted.
Applications in development tools
ASTs support many tasks beyond program execution:
- Static analysis. Static analysis examines program structure without executing the program, often combining AST information with types and control-flow models.
- Refactoring. Renaming or moving a declaration requires understanding syntactic roles and, usually, resolved references.
- Code generation and translation. Tools can construct or transform trees before emitting code in the same or another language.
- Structural search. A query can distinguish a function call from similar-looking text in a comment or string.
- Formatting and linting. Syntax-aware tools can enforce conventions and identify suspicious constructs.
- Formal reasoning. Formal verification systems may translate syntax trees into logical representations.
Widely used examples include the AST exposed by Python’s ast module, the source-oriented AST used by Clang for C-family languages, and AST formats used throughout the JavaScript tooling ecosystem. These representations differ in their node kinds, retained source information, and integration with semantic analysis.
Limitations and design trade-offs
An AST is not automatically a complete model of a program. Runtime-generated code, dynamic dispatch, external components, and configuration-dependent behavior can require information beyond the syntax tree.
Source fidelity is another trade-off. A compact AST is convenient for analysis, but a source-editing tool may need comments, token boundaries, and original formatting. Reconstructing equivalent source from an AST is generally easier than reconstructing the original source exactly.
Interactive tools must also handle incomplete or invalid code. They may retain error nodes or missing-token placeholders so that editing features continue to work before a program becomes syntactically valid. Incremental parsing and persistent tree representations can reduce the cost of rebuilding structure after small edits.
Finally, AST formats are often language- and implementation-specific. New language features can introduce new node kinds or change existing ones. Tools that consume ASTs must therefore account for representation versions and avoid assuming that superficially similar trees from different systems have identical semantics.