Introduction
Every program you write is read by another program before it runs. A compiler translates source code into another language, usually machine code or bytecode; an interpreter runs it directly. Python, Java, C and JavaScript engines all contain compilers, and so do the tools you meet every day: formatters, linters, database query planners and the template engines behind websites.
Compilers look intimidating, but they are built from a few clear phases, each with a simple job. In this course you build each phase yourself in Python. This first lesson builds a complete, tiny compiler for arithmetic so that you can see the whole shape at once.
How it works
A compiler works in phases, each turning one representation of the program into the next:
phases = ["lexical analysis", "parsing", "semantic analysis", "intermediate code", "optimisation", "code generation"]
for number, phase in enumerate(phases, 1):
print(number, phase)- Lexical analysis (the lexer or scanner) reads characters and groups them into tokens:
2,+,3,*,(. - Parsing checks that the tokens follow the grammar and builds a syntax tree that shows the structure, for example that
*binds tighter than+. - Semantic analysis checks meaning: names are declared, types match, functions get the right arguments.
- Intermediate code is a simple, machine-independent form, such as three-address code.
- Optimisation improves that code without changing what it does: computing constants early, removing dead code.
- Code generation produces the target: machine code, bytecode, or instructions for a virtual machine.
The first three phases make up the front end, which depends on the source language. Code generation is the back end, which depends on the target machine. Between them, the middle end works on intermediate code. Because the parts are separate, one front end can serve many machines, and one back end many languages, as in GCC and LLVM.
An interpreter shares the front end but, instead of generating code, walks the tree or runs the intermediate code at once. Python compiles to bytecode and then interprets that bytecode; Java compiles to bytecode and then compiles hot parts again to machine code while the program runs.
Syntax
tokens = re.findall(r"\d+|[-+*/()]", source) # lexing
tree = expr() # parsing, by recursive descent
code = gen(tree, []) # code generation for a stack machine
# then run: PUSH puts a number on the stack; ADD/SUB/MUL/DIV pop two and push the result
Example
import re
source = "2 + 3 * (4 - 1)"
tokens = re.findall(r"\d+|[-+*/()]", source)
print("tokens:", tokens)
pos = 0
def peek():
return tokens[pos] if pos < len(tokens) else None
def take():
global pos
pos += 1
return tokens[pos - 1]
def expr():
node = term()
while peek() in ("+", "-"):
node = (take(), node, term())
return node
def term():
node = factor()
while peek() in ("*", "/"):
node = (take(), node, factor())
return node
def factor():
if peek() == "(":
take()
node = expr()
take()
return node
return int(take())
tree = expr()
print("tree:", tree)
def gen(node, code):
if isinstance(node, int):
code.append(f"PUSH {node}")
else:
op, left, right = node
gen(left, code)
gen(right, code)
code.append({"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}[op])
return code
code = gen(tree, [])
print("code:", code)
stack = []
for ins in code:
if ins.startswith("PUSH"):
stack.append(int(ins.split()[1]))
else:
b, a = stack.pop(), stack.pop()
stack.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "DIV": a // b}[ins])
print("result:", stack.pop())Line by line
- The lexer is one regular expression: a run of digits, or one operator or bracket. Spaces are simply never matched.
- The parser has one function per precedence level:
exprhandles + and −,termhandles * and /, andfactorhandles numbers and brackets. The tree is a nested tuple. genwalks the tree: for an operator it generates the left side, then the right side, then the operation. That is exactly the order a stack machine needs.- The last loop is the target machine. PUSH adds a number; an operation pops two values and pushes the result.
- The tree shows the grouping 2 + (3 × (4 − 1)), and the machine computes 11.
Expected result
tokens: ['2', '+', '3', '*', '(', '4', '-', '1', ')']
tree: ('+', 2, ('*', 3, ('-', 4, 1)))
code: ['PUSH 2', 'PUSH 3', 'PUSH 4', 'PUSH 1', 'SUB', 'MUL', 'ADD']
result: 11
In the real world
CPython compiles each module to bytecode for a stack machine, which is why you can see .pyc files. The Java compiler produces bytecode for the JVM, and TypeScript is compiled to JavaScript. LLVM provides a shared middle and back end used by Clang, Rust and Swift. Knowing the phases helps you read error messages: "unexpected token" comes from the parser, "undefined name" from semantic analysis.
Common mistakes
- Mixing up phases: a lexer does not know grammar, and a parser does not check types.
- Thinking interpreters have no compiler: most interpreters compile to an internal form first.
- Forgetting that order matters on a stack machine: for a − b, push a, then b, then subtract.
- Testing only the whole pipeline: test each phase separately, it makes errors easy to locate.
Best practices
- Keep each phase in its own function or module, with a clear input and output.
- Print the output of every phase when something goes wrong.
- Start with a tiny language, such as arithmetic, and grow it one feature at a time.
Summary
A compiler turns characters into tokens, tokens into a syntax tree, and the tree into code, checking meaning and improving the code along the way. The front end understands the source language and the back end the target machine. A whole compiler for arithmetic fits in a few dozen lines, and every later lesson deepens one of its phases.
Quick check
Key takeaways
- Each phase turns one representation into the next: characters, tokens, tree, intermediate code, target code.
- The front end understands the source language; the back end knows the target machine.
- Even a tiny compiler has the same shape as a real one.
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.