Skip to content
STIMSMITH

Abstract Syntax Tree

Concept WIKI v2 · 8/4/2026

An Abstract Syntax Tree (AST) is a tree-structured representation of the syntactic form of source code or formal artifacts. ASTs serve as an intermediate form between parsing and downstream analysis, transformation, and code generation; they are also a building block for syntactic filtering, machine-learning models on code, and declarative AST description tools.

Abstract Syntax Tree

An Abstract Syntax Tree (AST) is a hierarchical, tree-shaped data structure that represents the syntactic structure of a program, expression, or other formal artifact. Each node in the tree corresponds to a construct (e.g., an expression, statement, or instruction), and child nodes represent the operands or sub-constructs of their parent.

Role in Compilation and Code Generation

ASTs are a canonical intermediate representation in compilers and related tools. After a front-end parser produces an AST, subsequent phases (semantic analysis, optimization, code generation) operate on that tree rather than on raw text. The reverse operation — serializing an AST back to source text — is performed by an unparser (also called a pretty printer), which is the conceptual opposite of a parser.

Using an AST together with an unparser offers two important benefits over alternative code-construction strategies such as string concatenation:

  • Syntactic correctness of the emitted code is structurally guaranteed by construction.
  • Language portability is easier: the same AST can be unparsed to multiple target languages by swapping the unparser, which simplifies supporting backends written in different programming languages.

ASTs as a Syntactic Validity Filter

Parsers construct ASTs from source text, and the success of that construction is itself a useful oracle for syntactic validity. In the ChiGen tool for generating Verilog designs to fuzz EDA (Electronic Design Automation) tools, ASTs serve as the front-end filter of a two-sieve data curation pipeline:

  1. Syntactic sieve. The Verible syntactic analyzer parses each candidate .v file. If Verible cannot build an abstract syntax tree for the file, the file is discarded as syntactically invalid. This step is fast and rejects files that are, for example, still under development or contain simple errors such as a missing semicolon.
  2. Semantic sieve. Files that pass the syntactic sieve are then passed to Jasper's HDL analyzer for semantic checking. Jasper also rejects invalid syntax, but it is more computationally expensive than Verible because it enforces semantic constraints of the Verilog language standard.

Because building an AST is the parsing step, the syntactic sieve is essentially "did Verible's parser succeed?" The two-stage design — cheap AST-build check first, expensive semantic check second — is justified by the large gap in cost between the two analyzers.

Use in the formal-iss Code Generation Tool

In the minimally invasive RISC-V ISS (Instruction Set Simulator) generation approach described in Minimally Invasive Generation of RISC-V (FDL 2023), the formal-iss code generation tool builds a C/C++ abstract syntax tree directly from the formal instruction semantics of the LIBRISCV Haskell library. The pipeline is:

  1. The code generator derives the formal semantics of each RISC-V instruction from LIBRISCV.
  2. It constructs an AST in which one C function is represented per RISC-V instruction, parameterized over a void * processor abstraction (core), the program counter (instrPC), and a void * instruction abstraction (instr).
  3. The AST is handed to the language-c Haskell library, which acts as the unparser and serializes the tree into C/C++ source code.

By emitting code through this AST + unparser pipeline, the tool guarantees that the generated C/C++ implementation of the LB (load byte) and other instructions is syntactically correct and can be readily adapted to a variety of existing RISC-V simulators (e.g., Spike, RISC-V VP) without manual rewriting.

ASTs in Machine Learning on Code

Beyond compilation, ASTs have become a standard representation for machine-learning methods that operate on source code, such as code summarization. The BASTS (Block-wise Abstract Syntax Tree Splitting) method, for example, splits a method's code along dominator-tree blocks of its Control Flow Graph, produces a split AST per block, and encodes each split AST with a Tree-LSTM. The resulting local syntactic encodings are then combined with token-level code encodings and fed into a Transformer to generate natural-language code summaries. This illustrates that the AST's tree structure is well suited both to classical static analysis and to neural sequence/transduction models.

Declarative Description of ASTs

Tools such as Gom (described in Canonical Abstract Syntax Trees) are domain-specific languages dedicated to describing ASTs and generating a typed implementation (e.g., in Java) for them. A distinguishing capability of Gom is the option to maintain the internal representation in canonical form with respect to a user-specified rewrite system, so that client programs manipulate only normal forms — a property that is often present implicitly in hand-rolled AST implementations but rarely guaranteed by construction.

See Also

  • ChiGen — Uses Verible's ability to build an AST as the syntactic-validity sieve when curating Verilog corpora for fuzzing EDA tools.
  • Hindley-Milner Type Inference — A constraint-generation-and-unification technique for type checking that operates on syntactic structures such as ASTs.
  • formal-iss code generation tool — Uses ASTs as the intermediate representation between formal RISC-V semantics (from LIBRISCV) and generated C/C++ simulator code (unparsed via the language-c library).

LINKED ENTITIES

2 links
ChiGen USES
Hindley-Milner Type Inference USES

CITATIONS

5 sources
5 citations
[1] ASTs are produced by front-end parsers and serve as the canonical intermediate representation that subsequent compiler phases (semantic analysis, optimization, code generation) operate on. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[2] In ChiGen, the Verible syntactic analyzer builds an abstract syntax tree for each candidate Verilog file; if it cannot, the file is discarded as syntactically invalid, and only survivors are sent to Jasper's more expensive semantic analyzer. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[3] ChiGen uses a Hindley-Milner-style type inference pipeline that creates type variables for each identifier, generates equality and conditional constraints (including Verilog bit-width extension rules), and solves them via unification; a unification failure (e.g., bitvector(8) vs bitvector(16)) causes the current Verilog skeleton to be discarded. Bottom-Up Generation of Verilog Designs for Testing EDA Tools
[4] Gom is a language for describing abstract syntax trees and generating a Java implementation for those trees, with the option to maintain the internal representation in canonical form with respect to a rewrite system so that client programs manipulate only normal forms. Canonical Abstract Syntax Trees
[5] BASTS (Block-wise Abstract Syntax Tree Splitting) splits code along dominator-tree blocks of its Control Flow Graph, produces a split AST per block, encodes each with a Tree-LSTM, and combines the resulting encodings with code encodings inside a Transformer to generate code summaries. Improving Code Summarization with Block-wise Abstract Syntax Tree Splitting

VERSION HISTORY

v2 · 8/4/2026 · minimax/minimax-m3 (current)
v1 · 6/9/2026 · minimax/minimax-m3