vault

Go Abstract Syntax Tree

12 min read

Go Abstract Syntax Tree

An Abstract Syntax Tree (AST) is the in-memory tree-shaped representation of a program’s source code, stripped of surface syntax like parentheses, whitespace, and the exact spelling of tokens, but retaining every structural fact the rest of the compiler needs. In Go there are two distinct ASTs to keep straight: the compiler’s internal syntax tree, produced by cmd/compile/internal/syntax and consumed by the gc toolchain; and the standard library’s go/ast, produced by go/parser, which powers tools like gofmt, go vet, gopls, and golang.org/x/tools/go/analysis. They are structurally similar but separate codebases — the compiler does not use go/ast. The parser builds the AST directly from the token stream (compiler README); the AST is then the substrate on which type checking runs before the program is lowered to the compiler IR.

Mental Model

Think of source text as a flat sequence of bytes, the token stream as that sequence chunked into meaningful words (func, (, x, +, 1), and the AST as those words reassembled into their grammatical structure. The expression a + b * c is just seven tokens in a line, but the AST captures the precedence the language grammar implies: a BinaryExpr for + whose right operand is itself a BinaryExpr for *. Once that structure exists, no later phase ever has to re-parse — operator precedence, statement nesting, and scope boundaries are all encoded as tree shape.

“Abstract” is the load-bearing word. A concrete syntax tree (parse tree) would have a node for every grammar production, including the parentheses in (a + b) and the semicolons Go inserts automatically. The AST throws those away: (a + b) and a + b produce the same BinaryExpr — the parentheses only mattered for parsing, not for meaning. The go/ast package keeps a ParenExpr node for tools that need to reproduce source faithfully (gofmt), but the compiler’s tree discards even that.

graph TD
    SRC["Source bytes:<br/>func f() int { return a + b*c }"]
    TOK["Token stream:<br/>func IDENT ( ) IDENT { return IDENT + IDENT * IDENT }"]
    AST["AST (tree)"]
    SRC -->|lexer| TOK
    TOK -->|parser| AST
    AST --> FD["FuncDecl 'f'"]
    FD --> BODY["BlockStmt"]
    BODY --> RET["ReturnStmt"]
    RET --> ADD["BinaryExpr '+'"]
    ADD --> LA["Ident 'a'"]
    ADD --> MUL["BinaryExpr '*'"]
    MUL --> LB["Ident 'b'"]
    MUL --> LC["Ident 'c'"]

Diagram: source bytes become a flat token stream, then a tree. The insight: precedence (* binds tighter than +) is not stored as data — it is the nesting of BinaryExpr nodes. Every later phase walks this tree instead of re-reading text.

Mechanical Walk-through

The compiler’s syntax tree

The gc compiler’s first phase, per the compiler README, is: “Source code is tokenized (lexical analysis), parsed (syntax analysis), and a syntax tree is constructed for each source file.” This work lives in cmd/compile/internal/syntax. The package defines node types in nodes.go, a recursive-descent parser in parser.go, and a scanner in scanner.go. The node names differ deliberately from go/ast’s: the top-level syntax.File holds PkgName *Name and DeclList []Decl (not go/ast’s Name / Decls); declarations are ImportDecl, ConstDecl, TypeDecl, VarDecl, FuncDecl; the call node is CallExpr with Fun Expr and ArgList []Expr; and, as noted below, both binary and unary operators collapse into a single Operation node (all verified against syntax/nodes.go at go1.26).

The parser is hand-written recursive descent: each grammar production becomes a method (parser.fileOrNil, parser.funcDeclOrNil, parser.expr, parser.binaryExpr). Recursive descent maps naturally onto Go’s grammar because Go was deliberately designed to be parseable with bounded lookahead — there is no need for a parser generator. Operator precedence is handled by precedence climbing inside binaryExpr, whose signature is func (p *parser) binaryExpr(x Expr, prec int) Expr (verified against syntax/parser.go at go1.26). The prec argument is a minimum-precedence floor: the loop body for (p.tok == _Operator || p.tok == _Star) && p.prec > prec consumes an operator only if it binds strictly more tightly than the floor, allocates a new Operation node, then recurses with p.binaryExpr(nil, tprec) passing the just-consumed operator’s precedence as the new floor. That recursion is exactly what nests Operation nodes for * inside the Operation for + in the diagram. A binary Operation has fields Op Operator and X, Y Expr; a unary operation reuses the same struct with Y == nil (verified against syntax/nodes.go at go1.26) — so the compiler’s tree has no separate UnaryExpr type the way go/ast does.

Each node carries a Pos (a compact position value indexing into the file’s line table) so that diagnostics can point at the exact source location, and the tree faithfully records enough to reconstruct the program. Crucially, at this stage the tree is untyped — an Ident node knows its spelling (x) but not yet what x is; resolving that is the job of Go Type Checking.

The standard library’s go/ast

Outside the compiler, the public AST is go/ast, produced by go/parser.ParseFile. Every node implements the Node interface — Pos() token.Pos and End() token.Pos, giving the half-open source range [Pos, End) (go/ast docs). Nodes fall into three families:

  • Expressions (ast.Expr): Ident, BasicLit, BinaryExpr, UnaryExpr, CallExpr, SelectorExpr (x.Y), IndexExpr, StarExpr (*x), CompositeLit ([]int{1,2}), FuncLit, and the type-expression nodes ArrayType, MapType, StructType, InterfaceType, FuncType, ChanType.
  • Statements (ast.Stmt): AssignStmt, IfStmt, ForStmt, RangeStmt, SwitchStmt, TypeSwitchStmt, SelectStmt, DeferStmt, GoStmt, ReturnStmt, BlockStmt, BranchStmt (break/continue/goto), DeclStmt.
  • Declarations (ast.Decl): FuncDecl for functions and methods, and GenDecl for import/const/type/var, which contains Spec nodes (ImportSpec, ValueSpec, TypeSpec).

An entire file is an ast.File, whose Decls []Decl holds the top-level declarations, Name *Ident the package name, Imports the import specs, and Comments all comments in source order (go/ast docs). The GoVersion field carries the minimum Go version parsed from a //go:build line.

Positions and the FileSet

Positions are not file offsets — they are opaque token.Pos values that index into a token.FileSet. A FileSet packs many files into one linear address space so a single token.Pos uniquely identifies a (file, line, column) triple across an entire build. You translate back with fset.Position(pos), which yields a printable file:line:column. This indirection is why every tool that parses Go threads a *token.FileSet everywhere — the AST nodes alone cannot tell you where they came from.

Comments are not in the tree

A subtle and frequently misunderstood point: comments are not child nodes of the statements they sit next to. They live in File.Comments, a flat list, and their association with code is positional — a comment is “doc” for a declaration if it ends on the line just before the declaration starts. The Doc and Comment fields on declaration nodes are convenience pointers populated by the parser, but if you rewrite the tree (move a function), those positions go stale. The remedy is ast.NewCommentMap, which rebuilds the comment-to-node mapping after edits (go/ast docs).

Code and Traversal Examples

Parsing and printing an AST

package main
 
import (
	"go/ast"
	"go/parser"
	"go/token"
)
 
func main() {
	src := `package p
func f(a, b, c int) int { return a + b*c }`
 
	fset := token.NewFileSet()                          // 1
	file, err := parser.ParseFile(fset, "p.go", src, 0) // 2
	if err != nil {
		panic(err)
	}
	ast.Print(fset, file) // 3
}

Line 1 creates the FileSet — the position registry every later call needs. Line 2 runs the lexer and parser; the final 0 is a parser.Mode bitmask (set parser.ParseComments to retain comments, parser.SkipObjectResolution to skip the deprecated scope-resolution pass for speed). On success file is an *ast.File. Line 3 pretty-prints the whole tree with positions resolved through fset — the canonical way to see what the parser built.

Walking the tree

ast.Inspect(file, func(n ast.Node) bool { // 1
	switch x := n.(type) {                 // 2
	case *ast.BinaryExpr:                  // 3
		fmt.Printf("binary op %s at %s\n",
			x.Op, fset.Position(x.Pos()))
	case *ast.Ident:                       // 4
		fmt.Printf("ident %q\n", x.Name)
	}
	return true                            // 5
})

Line 1: ast.Inspect does a depth-first pre-order walk, calling the function once per node. Line 2 type-switches on the dynamic node type — the AST is a heterogeneous tree, so a type switch is the idiomatic dispatch. Lines 3–4 handle the cases of interest; everything else falls through. Line 5 returns true, telling Inspect to descend into this node’s children; returning false prunes the subtree (useful to skip, say, the bodies of nested function literals). Since Go 1.23, ast.Preorder exposes the same walk as an iter.Seq[Node] so you can use a plain for ... range.

A real rewrite: from AST to compiler IR

After Go Type Checking runs, the gc compiler does not keep the syntax tree. The “noding” phase (cmd/compile/internal/noder) converts the typed syntax tree into the compiler’s own IR node form (cmd/compile/internal/ir). Per the compiler README, modern Go does this through Unified IR — the type-checked code is serialized to a compact byte stream and re-read to build IR nodes, which means the same serialized form doubles as the export data used to compile dependent packages. So in the compiler, “the AST” is a transient intermediate: parse → type-check → serialize → IR. The standalone go/ast tree, by contrast, is the durable representation that external tooling keeps and mutates.

Common Misunderstandings

“There is one Go AST.” There are at least two production trees — cmd/compile/internal/syntax (compiler) and go/ast (tooling) — plus historical ones. They have different node names (syntax.Operation vs ast.BinaryExpr), different position encodings, and different design priorities (the compiler’s is tuned for speed and discarded early; go/ast is tuned for fidelity and reuse). Code written against one does not work against the other.

“The AST knows types.” A freshly parsed AST is purely syntactic. ast.Ident for x does not know whether x is an int, a function, or a package name — that information comes only after running go/types (or the compiler’s types2), which produces a separate types.Info map keyed by AST nodes. Mistaking a parsed-but-not-checked tree for a typed one is the single most common beginner error in Go tooling.

“gofmt reformats by editing text.” gofmt parses to an ast.File (with comments), then re-prints the tree with go/printer. Formatting is therefore not regex surgery — it is “parse, then render canonically.” This is why gofmt can never produce syntactically invalid output and why it silently normalizes things like a +b to a + b.

“Editing the AST is enough; comments follow.” As covered above, comments are positionally attached. Insert a node and the comment offsets are wrong. Tools that rewrite Go (gopls refactorings, dst — the “decorated syntax tree” library) exist specifically because raw go/ast makes comment-preserving edits painful.

“Parentheses are lost.” The compiler’s tree drops them, but go/ast keeps a ParenExpr precisely so source-faithful tools can round-trip. “Abstract” is a spectrum, not a binary.

Alternatives and When to Choose Them

For analyzing Go code outside the compiler, the choice is between raw go/ast + go/parser, the higher-level golang.org/x/tools/go/analysis framework (used by go vet and staticcheck — gives you the AST plus type info plus a driver), and dave/dst when you need comment-faithful rewrites. Use raw go/ast for read-only inspection and quick scripts; use analysis for anything resembling a linter; use dst for code generation that must preserve formatting and comments.

You would never reach for the compiler’s cmd/compile/internal/syntax package directly — it is an internal package, unstable across releases, and not meant for external consumption. The boundary is firm: tooling uses go/ast, the compiler uses its own tree.

For producing code, text/template or string concatenation is often simpler than building ast nodes, because constructing a valid AST by hand is verbose. The usual pattern is: emit text, then gofmt it.

Production Notes

The AST is the foundation of the entire Go tooling ecosystem. gopls, the language server behind editor integrations, parses every file in a workspace into go/ast trees and keeps them incrementally updated; “go to definition” is an AST + go/types lookup. go vet’s dozens of checks (printf-format mismatches, lost defer, copied locks) are AST walks paired with type information. Code generators — stringer, mockgen, protobuf’s Go plugin — parse input with go/parser and emit output that they then gofmt.

A practical performance note: parser.ParseFile with parser.SkipObjectResolution is meaningfully faster because it skips building the deprecated per-file Scope/Object graph; modern tools resolve identifiers with go/types instead and should always set that flag. For large monorepos, the cost of re-parsing files dominates many tool runs, which is why gopls invests heavily in caching and incremental reparsing.

In the compiler itself, the syntax tree’s lifetime is deliberately short: it exists only long enough to be type-checked and noded into IR, then is garbage-collected. This keeps the compiler’s peak memory down — the durable representation is the compact Unified IR byte stream, not the tree. The cmd/compile/internal/noder package is even described in the compiler overview as the step that “create[s] compiler AST” — but note that what it creates is the IR node form, fed from the serialized type-checked program, not the syntax tree being re-walked.

A point-in-time note as of Go 1.26 (the current stable line; Go 1.26.3 was released 2026-05-07, per the release history): go/ast is a stable, compatibility-promised package and its core shape has not changed, but Go 1.26 added a few surface APIs worth knowing — ast.ParseDirective, which parses directive comments such as //go:generate into a structured form so tools stop hand-rolling that parsing, and token.File.End plus a corrected BasicLit.ValueEnd field that fixes BasicLit.End() for multi-line raw strings in Windows source (Go 1.26 release notes). None of these alter the model above; they sharpen the edges. Separately, the go/types note that the gotypesalias GODEBUG will be removed in Go 1.27 (making types.Alias unconditional) is a tooling detail relevant to anyone pairing go/ast with go/types.

See Also

Graph View

Backlinks