What is an AST?

Why don’t compilers work directly on your source code? Because a tree is better than a string of characters.

Where does this article fit in?

This article is part of the Formal Languages (L) series. It introduces the Abstract Syntax Tree, produced by parsing context-free grammars (L2) described in EBNF (L3). The AST is the central representation in the BP2SC pipeline (processing chain).

---

Why is it important?

You’ve written code. The compiler needs to understand it, verify it, perhaps optimize it, and then translate it. But your code is just a sequence of characters — letters, numbers, symbols. How can it be manipulated intelligently?

The AST (Abstract Syntax Tree) is the answer. It’s a structured representation of your code that captures its meaning without being cluttered by the details of its form. Parentheses, spaces, semicolons — all of that disappears. Only the logical structure remains.

For the BP2SC (BP3-to-SuperCollider) transpiler (source-to-source code translator, see I2 and I3), the AST is the core of the system. Each BP3 file (the musical grammar language of the Bol Processor, see I2) is first parsed into a tree of 12 different node types, then this tree is traversed to generate the equivalent SuperCollider code (sound synthesis environment, see I3).

The idea in one sentence

An AST is a tree-like representation of source code that preserves its logical structure while eliminating non-essential syntactic details.

---

Let’s explain step by step

Parse tree vs AST: the crucial difference

When a parser (syntactic analyzer) analyzes code, it first produces a parse tree (derivation tree, also called a concrete syntax tree) that exactly reflects the rules of the grammar. This tree contains everything, including purely syntactic elements.

Analogy: the script vs the screenplay

Imagine a play:

• The complete script includes all stage directions, page numbers, technical indications (“lights at 50%”). This is the parse tree.
• The stripped-down screenplay keeps only the dialogues and essential actions. This is the AST.

Both represent the same play, but one is faithful to the form, the other to the substance.

Example with 2 + 3:

Parse tree (derivation tree):

Figure 1 --- Parse tree of the expression 2 + 3

This tree contains Expr, Terme, Facteur nodes that correspond to the grammar rules. It’s faithful, but verbose.

AST (abstract tree):

Figure 2 --- AST of the expression 2 + 3

The AST only keeps the essentials: an addition operation with two operands. The intermediate levels have disappeared.

Why this simplification?

• Simpler manipulation: fewer nodes to traverse
• Grammar independence: the syntax can be changed without modifying the AST
• Focus on semantics: the tree represents what the code does, not how it is written

Example 1: the expression 2 + 3 * 4

Let’s build the AST for this expression step by step.

The source code: 2 + 3 * 4

The resulting AST:

Figure 3 --- AST of the expression 2 + 3 * 4 (multiplication priority is encoded in the structure)

Important observations:

1. Priority is encoded: Mul is a child of Add, so multiplication will be evaluated first
2. No parentheses: they are not in the tree, but their effect is
3. Numbers are leaves: they are terminal values

AST evaluation (post-order traversal):

What is a post-order traversal?

A traversal (or walk) is a systematic way of visiting all nodes in a tree. Post-order means: “first the children, then the parent”.

Why post-order for evaluation? Because we must know the result of sub-expressions before we can calculate the parent expression. We cannot calculate 2 + (3*4) without first calculating 3*4.

1. Visit the Add node
2.   Visit left child → 2
3.   Visit right child (Mul)
4.     Visit left child → 3
5.     Visit right child → 4
6.     Evaluate Mul(3, 4) → 12    <-- children evaluated first
7.   Evaluate Add(2, 12) → 14     <-- parent evaluated after

Structure of an AST node

In practice, an AST node is often a class or a data structure:

from dataclasses import dataclass
from typing import Union

@dataclass
class Number:
    value: int

@dataclass
class BinOp:
    op: str          # "+", "-", "*", "/"
    left: 'Expr'
    right: 'Expr'

Expr = Union[Number, BinOp]

The AST of 2 + 3 * 4 in Python:

ast = BinOp(
    op="+",
    left=Number(2),
    right=BinOp(
        op="*",
        left=Number(3),
        right=Number(4)
    )
)

Example 2: The BP3 AST

The BP2SC transpiler defines 12 node types to represent all elements of a BP3 file:

Node	Represents	BP3 Example
BPFile	Complete file	(root)
GrammarBlock	Grammar section	ORD[1]
Rule	Production rule	S --> A B
Weight	Rule weight (see B4)	<50>, <50-12>
Flag	Condition or operation (see B4)	/Ideas/, /Ideas-1/
Note	Musical note	do4, C#5
Rest	Silence	-
NonTerminal	Symbol to expand	S, Phrase
Variable	Variable between pipes	|x|
Polymetric	Polymetric expression (see B5)	{2, A B C}
SpecialFn	Special function	_transpose(3)
HomoApply	Homomorphism (see B6)	(= |x|)

Concrete example — the BP3 rule:

<50> /Ideas/ S --> A _transpose(2) do4 {2, B C}

Its AST:

Figure 4 --- AST of the BP3 rule <50> /Ideas/ S --> A _transpose(2) do4 {2, B C}

Each element of the source code corresponds to a typed node in the tree.

Traversing an AST

To exploit an AST, we traverse (or walk) it: we systematically visit each node to perform an operation. There are several strategies, each adapted to a specific use:

The three depth-first traversal orders

Imagine visiting a multi-story house:

• Pre-order: note each room upon entering, before exploring its sub-rooms
• Post-order: note each room upon exiting, after exploring its sub-rooms
• In-order: for binary trees, alternate left-center-right

Depth-first traversal:

Strategy	Visit Order	Use Case
Pre-order	Node, then children	Copy the tree, serialize
Post-order	Children, then node	Evaluate, calculate properties
In-order	Left, node, right	Display infix expressions

Breadth-first traversal:

• Visit level by level, from top to bottom
• Useful for analyses that depend on the “depth” in the tree

The Visitor pattern:

What is a design “pattern”?

A design pattern is a reusable solution to a recurring problem in programming. These are proven “recipes”.

The Visitor pattern solves this problem: “How to add new operations on an AST without modifying the node classes each time?”

Analogy: Imagine a museum (the AST) with artworks (the nodes). Rather than modifying each artwork to add a new feature (audio guide, braille description…), a specialized “visitor” is created that knows how to interact with each type of artwork.

In object-oriented programming, the Visitor pattern allows adding operations without modifying the node classes:

class ASTVisitor:
    def visit(self, node):
        method_name = f'visit_{type(node).__name__}'
        visitor = getattr(self, method_name, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        raise NotImplementedError(f"No visitor for {type(node)}")

class Evaluator(ASTVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_BinOp(self, node):
        left = self.visit(node.left)
        right = self.visit(node.right)
        if node.op == '+': return left + right
        if node.op == '*': return left * right
        # ... other operations

# Usage
evaluator = Evaluator()
result = evaluator.visit(ast)  # → 14

From AST to target code

The BP2SC transpiler (see B7) uses the AST to generate SuperCollider code. Each node type has a translation rule:

BP3 Node	SuperCollider Code
Rule(lhs=S, rhs=[A,B])	Pdef(\S, Pseq([Pdef(\A), Pdef(\B)]))
Note(do, 4)	Pbind(\midinote, 60, \dur, 0.25)
Rest	Event.silent(0.25)
Polymetric(2, [A,B,C])	Pbindf(Pseq([...]), \stretch, 2/3)
SpecialFn(transpose, 3)	Pbindf(..., \mtranspose, 3)

Translation example:

// BP3
S --> do4 re4 mi4

// AST
Rule(lhs=[NonTerminal("S")], rhs=[Note("do",4), Note("re",4), Note("mi",4)])

// SuperCollider
Pdef(\S, Pseq([
    Pbind(\midinote, 60, \dur, 0.25),
    Pbind(\midinote, 62, \dur, 0.25),
    Pbind(\midinote, 64, \dur, 0.25)
], 1))

Why the AST is central

The AST is the pivot of any compiler or transpiler:

Figure 5 --- Compilation pipeline: from source code to target code, with the AST as the central pivot

The steps of the compilation pipeline

Step	Role	Input	Output
Lexer	Break text into units	"2 + 3"	[NUM:2, PLUS, NUM:3]
Parser	Build the structure	List of tokens	AST
Emitter	Generate target code	AST	Executable code

Lexer (or tokenizer): transforms a string of characters into tokens, the meaningful units of the language. Example: 123 becomes a NUMBER token, if becomes a KEYWORD token.

Tokens: lexical units of the language (numbers, operators, keywords, identifiers). These are the “words” recognized by the lexer before syntactic analysis.

Advantages of this architecture:

1. Separation of concerns: the parser handles syntax, the emitter handles generation
2. Intermediate analyses: the AST can be checked, optimized, and transformed before emission
3. Multi-target: the same AST can generate code for different platforms
4. Testability: the parser and emitter can be tested independently

---

Key takeaways

1. An AST is a tree-like representation of source code, stripped of non-essential syntactic details.
2. Parse tree vs AST: the parse tree is faithful to the grammar, the AST is faithful to the meaning.
3. Nodes are typed: each language construct has its node type (Note, Rule, BinOp…).
4. Traversal enables exploitation: evaluation, code generation, static analysis.
5. The AST is the central point of any compiler: it decouples syntactic analysis from code generation.
6. BP2SC uses 12 node types to represent the entirety of BP3 notation.

---

To go further

• Python ast module: https://docs.python.org/3/library/ast.html (to explore Python ASTs)
• AST Explorer: https://astexplorer.net/ (interactive AST visualization for many languages)
• Dragon Book, chapter 5: Syntax-Directed Translation
• Visitor Pattern: https://refactoring.guru/design-patterns/visitor

---

Glossary

Term	Definition
AST	Abstract Syntax Tree. A tree-like representation of source code that preserves the logical structure by eliminating non-essential syntactic details (parentheses, decorative commas, etc.).
Design pattern	A reusable solution to a recurring problem in software design. The Visitor pattern is a classic example for ASTs.
Emitter	A component of a compiler that generates target code (or object code) from the AST. Also called “code generator”.
Leaf	A terminal node in the tree, with no children. Represents atomic values: numbers, identifiers, strings.
Lexer	The first stage of a compiler. Breaks down source code into tokens (lexical units). Also called “tokenizer” or “lexical analyzer”.
Node	An element of the tree representing a language construct. Each node has a type (BinOp, Note, Rule…) and zero or more children.
Parse tree	A derivation tree faithful to the grammar rules. More detailed than the AST, it includes all syntactic elements. Also called “concrete syntax tree”.
Traversal	Systematic visit of all nodes in a tree according to a defined strategy (pre-order, post-order, in-order, or breadth-first).
Post-order	A traversal strategy where all children of a node are visited first, then the node itself. Ideal for expression evaluation.
Pre-order	A traversal strategy where the node is visited first, then its children. Ideal for copying or serializing a tree.
Token	A lexical unit of the language, produced by the lexer. Examples: number, operator, keyword, identifier. A token has a type and a value.
Walk	Synonym for traversal. The action of systematically visiting all nodes in the tree.
Visitor	A design pattern that allows adding operations to the AST without modifying the node classes. Each type of operation is a distinct “visitor”.

---

Prerequisites: L2 — Context-Free Grammars, L3 — EBNF Reading time: 9 min Tags: #ast #compilation #parsing #trees #transpilation

---

Next article: L5 — The three semantics: giving meaning to formal languages

---

← Back to index