Abstract Syntax Tree
Subject: Computer and Technology noun /ˈæb.strækt ˈsɪn.tæks triː/ 1 definition
- compiler-design
- programming-languages
- static-analysis
- data-structures
-
Definition (noun)
Entry #81 · UpdatedAn Abstract Syntax Tree (AST) is a hierarchical, tree-structured representation of the syntactic structure of source code produced by a parser. Unlike a concrete syntax tree that preserves every punctuation mark, delimiter, and intermediate grammar rule from raw text, an AST omits surface formatting details such as grouping parentheses and semicolons to retain only the essential semantic constructs—such as expressions, statements, operators, and declarations—and their parent-child nesting. Because it captures program structure and operator precedence cleanly in memory, an AST serves as the primary intermediate representation for semantic analysis, type checking, linting, optimization, and code generation.
Common Forms
Untyped AST: The initial syntax tree emitted directly by a parser, capturing structural constructs and source-location spans before identifier resolution or type checking.
Typed (Decorated) AST: An AST enriched during semantic analysis with resolved symbol bindings, scope information, and inferred or verified data types for downstream compilation passes.
Homogeneous AST: An implementation form in which every node shares a single uniform data structure distinguished by a kind tag and child list, simplifying generic tree traversals and serialization.
Heterogeneous AST: A strongly typed implementation form defining distinct node classes or algebraic variants for each language construct—such as
IfStatementorBinaryExpression—to enforce structural validity.
Example
When a JavaScript toolchain such as Babel parses
const total = (a + b) * 2;, it omits the semicolon and parenthesis tokens and constructs an AST in which aVariableDeclarationnode wraps a multiplicationBinaryExpressionwith an addition subtree (a + b) on the left and the literal2on the right. A linter or transpiler can then walk that tree directly to flag unused identifiers, down-level modern syntax, and generate updated source code without relying on fragile text-based regular expressions.