I. What Is an Abstract Syntax Tree
An Abstract Syntax Tree (AST) is a tree-shaped data structure used to represent the syntactic structure of a program.
Through lexical analysis and syntax analysis, a compiler converts source code into a Token sequence, and then builds an AST according to the language grammar.
An AST does not directly store every character of the source code; instead, it extracts the information in a program that has structural significance, such as:
- Variable declarations
- Function definitions
- Function calls
- Expressions
- Operators
- Conditional checks
- Loop structures
- Return statements
For example:
int result = a + b * c;
Looking at the source code, this is a variable declaration statement.
From the perspective of the AST, it contains the following structure:
- Variable declaration node:
VariableDeclaration - Variable name:
result - Type information:
int - Initialization expression:
a + b * c - Addition expression:
BinaryExpression - Multiplication expression:
BinaryExpression
Its core structure can be represented as:
flowchart TB
A["VariableDeclaration"]
B["Type: int"]
C["Identifier: result"]
D["BinaryExpression: +"]
E["Identifier: a"]
F["BinaryExpression: *"]
G["Identifier: b"]
H["Identifier: c"]
A --> B
A --> C
A --> D
D --> E
D --> F
F --> G
F --> H
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style F fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
As can be seen from the tree structure, the multiplication expression is the right child node of the addition expression.
This means the AST records not only which Tokens exist, but also the nesting relationships between them and the operator precedence.
II. Why We Need an AST
Source code is essentially a sequence of characters.
For a compiler, processing raw characters directly poses several problems:
- A string structure is not convenient for expressing the hierarchical relationships of a program.
- It cannot directly reflect operator precedence and associativity.
- Program structures such as variables, functions, and expressions are difficult to handle in a unified way.
- Code optimization requires recognizing program structure, not simply substituting characters.
- Semantic analysis needs to know the relationships among variable declarations, function calls, and scopes.
An AST solves these problems through its tree structure.
For example:
int result = a + b * c;
If we look only at the Token sequence:
INT IDENTIFIER ASSIGN
IDENTIFIER PLUS IDENTIFIER MULTIPLY IDENTIFIER
SEMICOLON
all we can tell is which lexical units appear.
An AST, however, can express this explicitly:
VariableDeclaration
└── Initializer
└── Add
├── Identifier(a)
└── Multiply
├── Identifier(b)
└── Identifier(c)
The AST converts a linear Token sequence into a program structure with hierarchical relationships.
The core value of an AST is not to preserve the source code, but to convert the source code into a structured representation that is convenient for program analysis and processing.
III. The Basic Composition of an AST
An AST is usually made up of nodes.
Each node represents a kind of program structure, and the nodes are organized through parent-child relationships.
3.1 Node Types
AST node types differ from one programming language to another, but they usually include the following categories:
| Node Type | Typical Name | Description |
|---|---|---|
| Program node | Program | The entire program or module |
| Declaration node | VariableDeclaration | Variable declaration |
| Function node | FunctionDeclaration | Function definition |
| Parameter node | Parameter | Function parameter |
| Identifier node | Identifier | Variable, function, or type name |
| Literal node | Literal | Numbers, strings, Boolean values, etc. |
| Binary expression | BinaryExpression | Addition, subtraction, multiplication, division, comparison, etc. |
| Unary expression | UnaryExpression | Negation, logical NOT, etc. |
| Function call | CallExpression | Function call |
| Assignment expression | AssignmentExpression | Assignment operation |
| Conditional statement | IfStatement | Conditional branch |
| Loop statement | WhileStatement | Loop structure |
| Return statement | ReturnStatement | Function return |
Node names are not a cross-language unified standard.
For example, the node definitions of JavaScript AST, Python AST, Clang AST, and Rust AST all differ.
3.2 Basic Properties of Nodes
An AST node usually contains the following information:
| Property | Purpose | Example |
|---|---|---|
| Node Type | Node type | BinaryExpression |
| Children | Child nodes | Left operand, right operand |
| Operator | Operator | + |
| Value | Node value | 123 |
| Location | Source code location | Line 1, Column 5 |
| Metadata | Additional information | Type, symbol references, etc. |
For example:
a + b
can be represented as:
BinaryExpression
├── operator: +
├── left
│ └── Identifier(a)
└── right
└── Identifier(b)
Where:
BinaryExpressionrepresents a binary expression.operatorrepresents the operator.leftrepresents the left operand.rightrepresents the right operand.
Note that the specific fields of an AST node are determined by the language specification, compiler implementation, and AST library design; there is no fixed structure that all languages must follow.
3.3 Parent Nodes and Child Nodes
An AST is a tree structure and usually contains:
- Root node (Root): the entry point of the entire tree.
- Parent node (Parent): a node that contains other nodes.
- Child node (Child): a node organized by a parent node.
- Leaf node (Leaf): a node with no child nodes.
For example:
a + b * c
Where:
- The addition expression is the root node.
aand the multiplication expression are child nodes of the addition expression.bandcare child nodes of the multiplication expression.- Identifier nodes are usually leaf nodes.
This structure enables the compiler to process different syntactic structures in a program layer by layer through tree traversal.
IV. How Is an AST Generated?
An AST is usually constructed during the syntax analysis phase of the compiler front end.
The overall process is as follows:
flowchart TB
A["Source code"]
B["Lexical analysis"]
C["Token sequence"]
D["Syntax analysis"]
E["Identify syntax structure"]
F["Create AST nodes"]
G["Organize parent-child relationships"]
H["Generate AST"]
I["Semantic analysis"]
A --> B
B --> C
C --> D
D --> E
E --> F
F --> G
G --> H
H --> I
style A fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#FFF5DE,stroke:#E8D29A,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
Actual compilers usually do not first build a complete concrete syntax tree and then separately convert it to an AST.
Many parsers create AST nodes while recognizing productions, and directly organize parent-child relationships.
4.1 Lexical analysis: Generate Tokens
First, the lexer reads the source code and converts the character sequence into Tokens.
For example:
int result = a + b * c;
This yields:
INT
IDENTIFIER(result)
ASSIGN
IDENTIFIER(a)
PLUS
IDENTIFIER(b)
MULTIPLY
IDENTIFIER(c)
SEMICOLON
At this point it is still a linear sequence, without a complete expression tree structure.
4.2 Syntax analysis: Identify structure
The parser identifies relationships between Tokens based on the language grammar.
For example:
Declaration
Type
Identifier
Initializer
The initializer expression is further recognized as:
AddExpression
Identifier(a)
MultiplyExpression
Identifier(b)
Identifier(c)
The parser thereby determines the node types and the hierarchical relationships between them.
4.3 Build AST nodes
The parser creates nodes based on the recognition results.
For example:
createIdentifier("a")
createIdentifier("b")
createIdentifier("c")
createBinaryExpression("*", b, c)
createBinaryExpression("+", a, multiply)
createVariableDeclaration("result", "int", add)
Ultimately, a complete AST is formed.
This is a conceptual construction process; real compilers usually perform the related operations through parsing functions, node constructors, and memory allocators.
5. Differences Between AST and CST
AST and CST can both represent the syntactic structure of a program, but they focus on different content.
5.1 Concrete Syntax Tree (CST)
CST (Concrete Syntax Tree) is also called the concrete syntax tree.
It more completely reflects the correspondence between the source code and grammar rules, and usually retains more syntactic details.
For example:
a + b * c;
A CST may contain:
- Expression production nodes.
- Operator nodes.
- Identifier nodes.
- Terminals such as semicolons.
- Intermediate nodes generated during grammar derivation.
5.2 Abstract Syntax Tree (AST)
The AST omits some syntactic details that are unnecessary for subsequent program analysis.
For example:
ExpressionStatement
└── Add
├── Identifier(a)
└── Multiply
├── Identifier(b)
└── Identifier(c)
The AST focuses more on the core structure of expressions, rather than fully preserving every syntactic symbol.
5.3 Comparison of CST and AST
| Comparison Dimension | CST | AST |
|---|---|---|
| Full name | Concrete Syntax Tree | Abstract Syntax Tree |
| Focus | Complete syntax structure | Abstract program structure |
| Grammar nodes | Usually more are retained | Some intermediate nodes are usually omitted |
| Punctuation | Usually retained | Usually omitted |
| Parentheses | Usually retained | Usually not retained independently |
| Structural complexity | Relatively high | Relatively streamlined |
| Typical uses | Syntax restoration, code editing | Semantic analysis, optimization, code generation |
Note that an AST does not simply delete all punctuation marks.
For example, although parentheses usually do not need to be retained as independent AST nodes, the expression grouping relationships they determine must be reflected in the AST structure.
a * (b + c)
Even if the AST does not retain parenthesis nodes, it must retain the structure of b + c as the right operand of multiplication.
6. How an AST Expresses Operator Precedence
Operator precedence is one of the most important applications of ASTs.
Consider the expression:
a + b * c - d
Assume multiplication has higher precedence than addition and subtraction, and that addition and subtraction are left-associative.
Its computation structure is:
(a + (b * c)) - d
The corresponding AST:
flowchart TB
A["Subtract"]
B["Add"]
C["Identifier: d"]
D["Identifier: a"]
E["Multiply"]
F["Identifier: b"]
G["Identifier: c"]
A --> B
A --> C
B --> D
B --> E
E --> F
E --> G
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
From the AST, one can directly determine:
b * cfirst forms a multiplication subtree.a + (b * c)forms an addition subtree.- Finally, the entire addition subtree and
dform a subtraction expression.
This shows that operator precedence does not need to be additionally stored in the AST as a simple number.
It is already expressed through the nesting relationships of the tree.
6.1 Effect of Associativity on the AST
Consider:
a - b - c
Subtraction is usually left-associative.
Therefore, the AST is represented as:
Subtract
├── Subtract
│ ├── a
│ └── b
└── c
Rather than:
Subtract
├── a
└── Subtract
├── b
└── c
These two trees represent different evaluation orders.
Therefore, the parser must correctly handle operator associativity; otherwise, it will generate an incorrect AST.
7. AST Traversal Methods
After an AST is built, the compiler needs to traverse it to perform tasks such as semantic analysis, optimization, and code generation.
Common traversal methods include:
- Preorder traversal (Preorder)
- Inorder traversal (Inorder)
- Postorder traversal (Postorder)
- Depth-first traversal (DFS)
- Breadth-first traversal (BFS)
7.1 Preorder Traversal
The visitation order for preorder traversal:
- Visit the current node.
- Traverse the left subtree.
- Traverse the right subtree.
For:
+
/ \
a *
/ \
b c
Preorder traversal result:
+ a * b c
Preorder traversal is often used to generate prefix expressions and in scenarios where parent nodes need to be processed first.
7.2 Inorder Traversal
The visitation order for inorder traversal:
- Traverse the left subtree.
- Visit the current node.
- Traverse the right subtree.
Example result:
a + b * c
Inorder traversal is often used for expression output.
However, when complex operator precedence and parentheses are involved, directly outputting node names is not sufficient—you also need to decide whether to add parentheses based on parent-child relationships and precedence.
7.3 Postorder Traversal
The visit order of postorder traversal:
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the current node.
Example result:
a b c * +
Postorder traversal is often used for:
- Expression evaluation.
- Generating stack-based intermediate code.
- Processing the parent node after its child nodes have been processed.
7.4 Comparison of the Three Traversal Methods
| Traversal Method | Visit Order | Typical Use |
|---|---|---|
| Preorder traversal | Root, left, right | Structural analysis, prefix expressions |
| Inorder traversal | Left, root, right | Expression output |
| Postorder traversal | Left, right, root | Expression evaluation, code generation |
The traversal order is not a fixed compiler execution order. Different compilation tasks choose different traversal methods, and may also use multiple passes or the visitor pattern to accomplish complex processing.
8. The Role of AST in Compilers
The AST is an important data structure that connects syntax analysis with subsequent compilation stages.
8.1 Semantic Analysis
Syntactic correctness does not necessarily mean a program is legal.
For example:
int result = "hello" + 10;
In some languages, this code may have a legal syntactic structure, but whether the expression permits such an operation must be determined by semantic rules.
Semantic analysis traverses the AST to check:
- Whether variables have been declared.
- Whether identifiers can be resolved correctly.
- Whether function calls match function definitions.
- Whether the types on both sides of an operator are compatible.
- Whether return values conform to the function declaration.
- Whether scope and access rules are satisfied.
Semantic analysis may attach information such as type information, symbol references, and implicit type conversions to AST nodes.
Therefore, an AST that has undergone semantic analysis is sometimes also called an Annotated AST.
8.2 The Relationship Between Symbol Tables and the AST
A Symbol Table is used to record information about identifiers in a program.
For example:
int count = 10;
int add(int a, int b) {
return a + b;
}
The symbol table may record:
| Name | Type | Role |
|---|---|---|
| count | int | Global variable |
| add | function | Function |
| a | int | Function parameter |
| b | int | Function parameter |
The AST is responsible for representing the program structure in which these declaration and usage relationships reside, while the symbol table is responsible for recording the definition information corresponding to names.
The two usually work together:
- Declaration nodes in the AST can create symbols.
- Identifier usage nodes in the AST can reference symbols.
- Scope structure determines the range of symbol lookup.
- Type information can be associated with AST nodes.
Symbol tables are not necessarily embedded directly in the AST. Many compilers use separate data structures to manage symbols and their scopes.
8.3 Code Optimization
Compilers can identify expression structure based on the AST and perform certain optimizations.
For example:
int result = 2 * 3 + x;
The compiler can identify the constant expression:
2 * 3
and evaluate it as:
int result = 6 + x;
This optimization is called Constant Folding.
Other optimizations that may be performed based on the AST or its subsequent intermediate representation include:
- Constant propagation.
- Dead code elimination.
- Expression simplification.
- Unreachable code analysis.
- Redundant computation identification.
It should be noted that most complex optimizations in modern compilers usually occur at the intermediate representation (IR) stage rather than directly on the AST.
The AST is better suited to expressing high-level program structure, while IR is usually better suited to optimizations at the control-flow, data-flow, and low-level instruction levels.
8.4 Code Generation
After completing semantic analysis and the necessary transformations, the compiler can generate target code based on the AST or the subsequent IR.
For example: