Crafting a parser, part 3: designing the AST

Recursive descent tells us when to build a node. This post is about what the node is. A well-shaped abstract syntax tree (AST) makes every later pass — precedence, resolution, type-checking — pleasant or painful.

Enums all the way down

Rust's enums are a perfect fit: one variant per syntactic form, recursion behind Box (a tree node cannot contain itself by value).

ast.rs

1pub enum Expr {2    Literal(Literal),3    Unary { op: UnOp, rhs: Box<Expr> },4    Binary { lhs: Box<Expr>, op: BinOp, rhs: Box<Expr> },5    Group(Box<Expr>),6}78pub enum Stmt {9    Let { name: Ident, value: Expr },10    Expr(Expr),11}

Spans belong on nodes too

The lexer attached spans to tokens; carry them onto AST nodes. A node without a span is a diagnostic you can't print and a go-to-definition you can't serve.

Concrete vs abstract

A parse tree records every token, paren, and semicolon. An AST keeps only what later passes need. Most compilers build the AST directly; IDE-grade tools keep a lossless tree and derive the AST — more on that in part seven.

Don't bake semantics into syntax

Tempting mistakes: storing a resolved variable slot on a name node, or a type on an expression. The parser knows neither yet. Keep the AST purely syntactic; attach analysis results in side tables keyed by node id.

🦀

Ferris' hot tip

Give every node a NodeId (a u32 you bump as you build). Side tables (HashMap<NodeId, Type>) then layer semantics on without mutating the tree or fighting the borrow checker.

Visiting the tree

You'll walk this tree constantly. A hand-written Visitor trait beats macros early on — it is explicit and debuggable.

Owned tree

owns: simplicity

`Box` childrenmoved and consumed by passes

Best for a batch compiler that runs once.

Arena + ids

owns: cross-references

nodes in a `Vec`, referenced by indexcheap to share, no borrow fights

Best when many passes revisit the same nodes.

Takeaways

One enum variant per form; recurse through Box.
Spans and a NodeId on every node; semantics live in side tables.
Choose owned tree vs arena by how many passes touch it.

Next: Pratt parsing and precedence.