Introduction
The parser's job is not only to say "yes, this is valid". It must also hand the rest of the compiler a structure it can work with. That structure is the abstract syntax tree (AST). Every later phase, from type checking to code generation, reads the AST instead of the source text. Python itself does this: its ast module returns the same kind of tree the interpreter uses, and tools such as linters and code formatters are built on it.
How it works
A parse tree records every step of the grammar. For (rate + 2) * hours it would contain nodes for the brackets, and long chains such as expression → term → factor for every single number. An abstract syntax tree drops all of that and keeps only the meaning:
- a
BinOpnode with an operator and two children, - a
Numnode for a number, - a
Namenode for a variable.
Brackets disappear because the grouping is now in the shape of the tree: in (rate + 2) * hours, the + node is a child of the * node, so it is computed first.
The parser builds the tree as it goes. Where the recursive-descent parser of the earlier lesson returned strings or tuples, it now returns node objects: BinOp(take(), node, term()).
Once the tree exists, each task is a tree walk: a recursive function that looks at the kind of node and handles it. To print the tree, print the node and then its children one level deeper. To evaluate it, evaluate the children and combine the results. The same pattern gives a type checker, an optimizer and a code generator. Many compilers organise these walks as visitors, with one method per kind of node.
Syntax
@dataclass
class BinOp:
op: str
left: object
right: object
def evaluate(node, env):
if isinstance(node, Num): return node.value
if isinstance(node, Name): return env[node.id]
a, b = evaluate(node.left, env), evaluate(node.right, env)
...
Example
import re
from dataclasses import dataclass
@dataclass
class Num:
value: int
@dataclass
class Name:
id: str
@dataclass
class BinOp:
op: str
left: object
right: object
def parse(text):
tokens = re.findall(r"\d+|\w+|\S", text)
pos = 0
def peek():
return tokens[pos] if pos < len(tokens) else None
def take():
nonlocal pos
pos += 1
return tokens[pos - 1]
def expr():
node = term()
while peek() in ("+", "-"):
node = BinOp(take(), node, term())
return node
def term():
node = atom()
while peek() in ("*", "/"):
node = BinOp(take(), node, atom())
return node
def atom():
token = take()
if token == "(":
node = expr()
take()
return node
return Num(int(token)) if token.isdigit() else Name(token)
return expr()
def show(node, depth=0):
pad = " " * depth
if isinstance(node, BinOp):
print(f"{pad}BinOp {node.op}")
show(node.left, depth + 1)
show(node.right, depth + 1)
elif isinstance(node, Num):
print(f"{pad}Num {node.value}")
else:
print(f"{pad}Name {node.id}")
def evaluate(node, env):
if isinstance(node, Num):
return node.value
if isinstance(node, Name):
return env[node.id]
a = evaluate(node.left, env)
b = evaluate(node.right, env)
if node.op == "+":
return a + b
if node.op == "-":
return a - b
if node.op == "*":
return a * b
return a // b
tree = parse("(rate + 2) * hours - 5")
print(tree)
show(tree)
print("value:", evaluate(tree, {"rate": 10, "hours": 3}))Line by line
- Three small
dataclasstypes are the node kinds:Num,NameandBinOp. - The parser is the recursive-descent parser from before, but it returns nodes instead of strings.
- Printing the root shows the whole tree as nested objects. No node stands for the brackets of the source: the
+node simply sits inside the*node. showwalks the tree and indents each level by two spaces, which makes the shape easy to see.evaluatewalks the same tree with values forrateandhours: (10 + 2) × 3 − 5 = 31.
Expected result
BinOp(op='-', left=BinOp(op='*', left=BinOp(op='+', left=Name(id='rate'), right=Num(value=2)), right=Name(id='hours')), right=Num(value=5))
BinOp -
BinOp *
BinOp +
Name rate
Num 2
Name hours
Num 5
value: 31
In the real world
Python's ast.parse returns an AST with classes such as BinOp, Name and Constant, and ast.unparse turns it back into code. Black, Ruff and pylint read code through syntax trees, and so do refactoring tools in editors: renaming a variable safely means changing the right Name nodes, not every matching piece of text. Babel and the TypeScript compiler do the same for JavaScript.
Common mistakes
- Keeping brackets as nodes: the shape of the tree already records the grouping.
- Forgetting a kind of node in a tree walk, so some programs crash only when that node appears.
- Mixing parsing and evaluating in one pass, which makes it hard to add type checking or code generation later.
- Building the tree with the wrong associativity, so 8 − 3 − 2 is stored as 8 − (3 − 2).
Best practices
- Give each node kind its own small class with named fields.
- Write a function that prints the tree first; it makes every other bug easier to find.
- Keep each phase as a separate tree walk with one job.
Summary
An abstract syntax tree keeps the structure and meaning of a program and drops punctuation such as brackets. The parser builds it, and each later phase is a recursive walk over it that handles every kind of node: printing, evaluating, checking or generating code.
Quick check
Key takeaways
- An AST keeps the structure of the program; grouping is in the shape of the tree, so brackets are not needed.
- The parser builds the AST; every later phase walks it.
- One recursive function per task (print, evaluate, check, generate code) keeps a compiler organised.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.