An abstract syntax tree (AST) is a tree data structure used in computer science to represent the abstract syntactic structure of text, often source code, written in a formal language. Each node of the tree denotes a construct occurring in the text. It is sometimes called simply a syntax tree.^[1]

The syntax is "abstract" in the sense that it does not represent every detail of the concrete syntax, but instead represents the essential structural information of the text. For example, grouping parentheses need not be represented as separate nodes because their effect is implicit in the tree structure. Similarly, punctuation and delimiters such as braces, semicolons, and parentheses may be omitted from an AST.^[1]

This distinguishes an abstract syntax tree from a concrete syntax tree, traditionally called a parse tree. During syntax analysis, a parser may construct an AST representing the syntactic structure of the input program.^[1] The AST can then serve as an intermediate representation for subsequent compiler phases, which may use information in the AST, annotate it with additional information, or transform it.^[1]

Abstract syntax trees are also used in program analysis and program transformation systems.^[2]

An AST represents the structure of an expression or program independently of many details of its concrete syntax. For example, the expression

a + b * c

can be represented by a simplified AST such as:

      +
     / \
    a   *
       / \
      b   c

In this representation, the structure of the tree captures the order in which the operations are grouped: the multiplication of b and c forms a subtree that is an operand of the addition. The precedence of multiplication over addition is therefore represented by the tree structure rather than by an explicit precedence rule once the AST has been constructed.^[1]

An AST differs in this respect from a concrete syntax tree. A concrete syntax tree reflects the grammatical structure used to parse the source text and may contain nodes corresponding to grammar productions or syntactic elements that are not needed for later processing. An AST instead retains the structure considered significant for subsequent processing while omitting some details of the concrete syntax.^[3]

This structured representation allows software to inspect and manipulate a program in terms of constructs such as expressions, statements, declarations, and identifiers rather than treating the source solely as a sequence of characters. ASTs can therefore be traversed and processed by compilers and by other software-development tools.^[1]

The development of abstract syntax is closely connected with early work on the formal description and implementation of programming languages. John McCarthy, who developed Lisp and coined the term Artificial Intelligence, introduced the idea of abstract syntax in work published in the early 1960s.^[4][5]

McCarthy's motivation was to describe the structure of programming-language expressions independently of the notation used to represent them. For example, a sum might be written in infix notation as a+b, in prefix or postfix notation, or as the Lisp S-expression (PLUS A B), while representing the same underlying syntactic operation. In this view, the important properties are the ability to recognize a construct and to identify its constituent parts rather than the particular sequence of symbols used to write it.^[4][6]

Tree-based representations of syntax subsequently became part of practical compiler construction. The TREE-META compiler-compiler system, documented in 1969, used grammar rules with embedded tree-building directives and provided tree-scanning and code-generation facilities for processing the resulting structures.^[7]

Abstract syntax trees are data structures widely used in compilers to represent the structure of program code. An AST is commonly constructed during the syntax analysis phase and can serve as an intermediate representation through which information is conveyed between subsequent compiler phases.^[1]

An AST provides a structured representation of a program that can be used by subsequent phases of a compiler. Compared with a concrete syntax tree, an AST generally omits syntactic details that are not needed for later processing while retaining the essential structure of the program.^[8] It can therefore serve as an intermediate representation through which information is conveyed between compiler phases.^[1]

Later compiler passes may associate additional information with the program represented by the AST. For example, symbol processing can associate uses of names with their declarations and record attributes of those names in a symbol table; this information can subsequently be used for tasks such as type checking.^[9]

Some properties of a program cannot be determined from its context-free syntax alone. In particular, semantic constraints such as whether an identifier refers to an appropriate declaration or whether an expression has a valid type depend on information about declarations and the surrounding program. These constraints are typically checked during semantic analysis, using information represented by the AST together with structures such as symbol tables.^[9]

The structure of an AST depends on the constructs of the source language and on the requirements of the compiler or other tool that uses it. In general, an AST preserves the essential hierarchical structure of the program while omitting syntactic details that are unnecessary for subsequent processing.^[1]

Different kinds of language constructs are typically represented by different kinds of AST nodes. For example, a binary expression can be represented by a node containing an operator and two operand subtrees, while constructs such as statement or argument lists may contain a variable number of child nodes. The particular representation is an implementation choice and varies among AST designs.^[3]

An AST may also contain or be associated with information used by later compiler phases. For example, nodes may record source locations, while semantic analysis may associate identifiers with declarations and determine information such as types.^[9] The exact information retained in or alongside the AST depends on the compiler's implementation.

Some AST implementations support unparsing, in which a source-code representation is generated by traversing the tree. Because an AST normally omits details of the concrete syntax, the resulting source need not reproduce the original text exactly; formatting, comments, punctuation, or redundant parentheses may differ.^[10]

During semantic analysis, the AST can be used together with information such as symbol tables to check semantic constraints including scope and type rules.^[9] After semantic analysis, a compiler may translate the program represented by the AST into another intermediate representation for optimization or code generation, although some compilers generate target code without a separate IR.^[11]

Beyond their role in compiler construction, abstract syntax trees are used by software-development tools that need to inspect, analyze, or transform source code according to its structure. Applications include static analysis, linting, automated refactoring, source-to-source transformation, code generation, and program comparison.

Static-analysis and linting tools can traverse a program's syntax tree and identify particular kinds of constructs or structural patterns. ESLint, for example, parses source code into a syntax tree that is exposed to linting rules. Rules can respond to particular node types, inspect the surrounding tree and scope information, report problems associated with AST nodes, and in some cases provide automatic fixes.^[12]

ASTs are also used by development environments and refactoring tools because they allow source-code changes to be described in terms of program constructs rather than solely as textual replacements. Clang provides facilities for matching patterns in its C and C++ AST and using those matches in source-analysis and transformation tools. Clang deliberately preserves some source-level constructs in its AST that other compiler representations may discard, which its documentation identifies as useful for refactoring.^[13]

The Eclipse Java Development Tools similarly provide a Java DOM/AST model and an ASTRewrite API for describing changes to AST nodes and applying those changes back to source code.^[14]

Source-to-source transformation tools can parse source code into an AST, modify the resulting tree, and generate source code from the modified representation. Babel, for example, provides separate components for parsing JavaScript into an AST, traversing and updating AST nodes, and generating JavaScript source from an AST.^[15][16][17] Because details such as whitespace and line breaks are not necessarily represented in the AST, generated source code need not reproduce the formatting of the original input.^[17]

Some programming languages expose their AST representations directly to programmers. Python's standard library, for example, includes the ast module, which can parse Python source into objects representing nodes of Python's abstract syntax grammar. The resulting AST can be inspected or transformed and can subsequently be compiled into a Python code object.^[18]

Representative modern uses of ASTs include:

AST differencing, or for short tree differencing, consists of computing the list of differences between two ASTs.^[19][20] This list of differences is typically called an edit script. The edit script directly refers to the AST of the code. For instance, an edit action may result in the addition of a new AST node representing a function.

An AST is a powerful abstraction to perform code clone detection.^[21]

One formal treatment of abstract syntax represents ASTs using multiple sorts corresponding to different syntactic categories. In this formulation, the categories of syntax are represented by sorts, while language constructs are represented by operators whose arities specify the number and sorts of their arguments. ASTs are then defined inductively from variables and applications of these operators.^[22]

The following gives this construction explicitly.

Let ${\displaystyle S}$ be a set of sorts, an arity is a tuple ${\displaystyle (s_{1},\dots ,s_{n},s)}$, for ${\displaystyle s_{1},\dots ,s_{n},s\in S}$, also written as ${\displaystyle (s_{1},\dots ,s_{n})s}$. More precisely, ${\displaystyle \mathrm {Arity} (S):=\coprod _{n\in \mathbb {N} }S^{n+1}}$.

Let ${\displaystyle {\mathcal {O}}=\{{\mathcal {O_{\alpha }}}\}_{\alpha \in \mathrm {Arity} (S)}}$ be an ${\displaystyle \mathrm {Arity} (S)}$-indexed family of disjoint sets of operators. If ${\displaystyle o}$ is an operator arity ${\displaystyle (s_{1},\dots ,s_{n})s}$ we say that ${\displaystyle o}$ has sort ${\displaystyle s}$ and has ${\displaystyle n}$ arguments of sorts ${\displaystyle s_{1},\dots ,s_{n}}$.

Fix ${\displaystyle S}$ be a finite set of sorts, and ${\displaystyle {\mathcal {O}}}$ an ${\displaystyle \mathrm {Arity} (S)}$-indexed family of disjoint sets of operators. Let ${\displaystyle {\mathcal {X}}=\{{\mathcal {X}}_{s}\}_{s\in S}}$ be an ${\displaystyle S}$-indexed family of disjoint sets of variables. The family ${\displaystyle {\mathcal {A}}[{\mathcal {X}}]=\{{\mathcal {A}}[{\mathcal {X}}]_{s}\}_{s\in S}}$ of abstract syntax trees, or ASTs, is the smallest ${\displaystyle S}$-indexed family of disjoint sets closed under the following conditions:

1. Variables are ASTs: if ${\displaystyle x\in {\mathcal {X}}_{s}}$, then ${\displaystyle x\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.
2. Operators combine ASTs: If ${\displaystyle o}$ is an operator of arity ${\displaystyle (s_{1},\dots ,s_{n})s}$, and ${\displaystyle a_{i}\in {\mathcal {A}}[{\mathcal {X}}]_{s_{i}}}$ for all ${\displaystyle 1\leq i\leq n}$, then ${\displaystyle o(a_{1};\dots ;a_{n})\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.^[22]

• Jones, Joel. "Abstract Syntax Tree Implementation Idioms" (PDF). Archived from the original (PDF) on 21 July 2024. Retrieved 9 November 2011. (overview of AST implementation in various language families)
• Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (17 May 2005). Understanding Source Code Evolution Using Abstract Syntax Tree Matching. MSR '05: Proceedings of the 2005 International Workshop on Mining Software Repositories. Saint Louis, Missouri: ACM. pp. 1–5. doi:10.1145/1082983.1083143.
• Würsch, Michael. Improving Abstract Syntax Tree based Source Code Change Detection (Diploma thesis).
• Lucas, Jason (16 August 2006). "Thoughts on the Visual C++ Abstract Syntax Tree (AST)".
• Robert Harper (2016). Practical Foundations for Programming Languages (Second Edition). Cambridge University Press.

Wikimedia Commons has media related to Abstract syntax trees.

• AST View: an Eclipse plugin to visualize a Java abstract syntax tree
• "Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE". eclipse.org.
• "CAST representation". cs.utah.edu.
• eli project: Abstract Syntax Tree Unparsing
• "Architecture-Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM". (OMG standard).
• JavaParser: The JavaParser library provides you with an Abstract Syntax Tree of your Java code. The AST structure then allows you to work with your Java code in an easy programmatic way.
• Spoon: A library to analyze, transform, rewrite, and transpile Java source code. It parses source files to build a well-designed AST with powerful analysis and transformation API.
• AST Explorer: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.