Abstract syntax tree

An abstract syntax tree is a hierarchical data structure that represents the syntactic structure of source code in a way that reflects the grammar of the programming language, but abstracts away from the concrete syntax. Unlike a parse tree (or concrete syntax tree), which contains every token and punctuation mark, an AST retains only the essential constructs, such as expressions, statements, and declarations, and their relationships. This makes it a central intermediate representation in compilers and interpreters, used for semantic analysis, optimization, and code generation.¹

The AST is typically produced by the parser, which builds it from the token stream generated by the lexer. The structure of the AST is defined by the grammar of the language, often using a formal specification such as a context-free grammar. For example, the expression a + b * c would be represented as a tree with the multiplication node as a child of the addition node, reflecting operator precedence. This tree is then traversed by later compiler phases, such as type checking and code generation.

ASTs are constructed by parsers, which can be hand-written recursive descent parsers or generated by parser generators like Yacc or ANTLR. The construction process involves applying grammar rules to the token stream and building tree nodes accordingly. The resulting tree is typically immutable in functional languages or mutable in imperative ones, and it can be traversed using various algorithms, such as depth-first search, to perform analyses or transformations.²

Manipulation of ASTs is a common task in tools like linters, formatters, and refactoring tools. For instance, a code formatter might traverse the AST to reprint the code with consistent indentation, while a refactoring tool might modify the AST to rename a variable or extract a method. In many modern development environments, ASTs are also used to power features like syntax highlighting, code completion, and error detection.³

Beyond compilers, ASTs are used in a wide range of software tools. Static analysis tools, such as linters and security scanners, analyze ASTs to detect potential bugs, security vulnerabilities, or style violations. For example, ESLint for JavaScript uses an AST to identify problematic patterns. Similarly, code metrics tools compute complexity measures like cyclomatic complexity from the AST.⁴

ASTs are also fundamental in program transformation systems, such as those used for code generation, code migration, and domain-specific language (DSL) implementation. In IDEs, ASTs enable features like go-to-definition, find-references, and safe automated refactoring. Additionally, ASTs are used in research on program comprehension and software evolution, where they serve as a basis for comparing code versions or detecting code clones.

One lesser-known aspect is the distinction between ASTs and other tree representations, such as the concrete syntax tree (CST) and the directed acyclic graph (DAG) used in some compilers. CSTs retain all syntactic details, while DAGs are used to represent expressions with shared subexpressions, enabling common subexpression elimination. Another subtlety is that some languages, like Lisp, have a syntax that is almost directly an AST, making the parse step trivial.⁵

Historically, the concept of the AST can be traced back to the early days of compiler construction, with John McCarthy's work on Lisp in the late 1950s, where S-expressions served as both syntax and internal representation. Later, the term "abstract syntax" was formalized in the context of the ALGOL 60 report, which distinguished between the concrete syntax (how programs are written) and the abstract syntax (the underlying structure).⁶

One challenge in AST-based tooling is handling language evolution and multiple dialects. As languages gain new features, AST structures must be updated, and tools must be adapted. For example, the introduction of async/await in JavaScript required changes to the AST used by tools like Babel and ESLint. Another challenge is the size and complexity of ASTs for large codebases, which can impact performance of analysis tools.⁷

Future directions include the use of machine learning on ASTs for tasks like code generation and bug prediction. Researchers have developed neural models that operate on ASTs, such as tree-based neural networks, to learn representations of code. Additionally, the rise of language servers and the Language Server Protocol (LSP) has standardized how editors interact with ASTs, enabling cross-language tooling.⁸

Parse tree

A concrete syntax tree that includes all tokens and syntactic details, as opposed to an abstract syntax tree.

Parser

A component that reads source code and builds an AST according to the grammar of the language.

Semantic analysis

The phase of compilation that checks the meaning of the program, often using the AST to verify type correctness and other semantic rules.