Back to series
· 9 min read

Abstract Syntax Tree (AST)


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:

  1. A string structure is not convenient for expressing the hierarchical relationships of a program.
  2. It cannot directly reflect operator precedence and associativity.
  3. Program structures such as variables, functions, and expressions are difficult to handle in a unified way.
  4. Code optimization requires recognizing program structure, not simply substituting characters.
  5. 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:

  • BinaryExpression represents a binary expression.
  • operator represents the operator.
  • left represents the left operand.
  • right represents 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.
  • a and the multiplication expression are child nodes of the addition expression.
  • b and c are 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 * c first forms a multiplication subtree.
  • a + (b * c) forms an addition subtree.
  • Finally, the entire addition subtree and d form 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:

  1. Visit the current node.
  2. Traverse the left subtree.
  3. 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:

  1. Traverse the left subtree.
  2. Visit the current node.
  3. 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:

  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. 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: