Compiler Design Tutorial: Learn Compilers from Scratch (2026)
Compilers are the translators that convert human-readable source code into machine-executable instructions. Writing a compiler is a profound educational experience — it forces you to understand programming languages at a depth that mere usage never reveals. This tutorial follows the classic compiler pipeline: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimization, and code generation.
We will build a complete front-end for a small subset of C and a back-end targeting x86-64 assembly. Along the way, we will explore LL(1) parsing, abstract syntax trees, type checking, three-address code, and register allocation via graph coloring. Each stage transforms the program representation from a string to executable code.
Lexical Analysis
The lexer (or scanner) reads the input character stream and groups characters into tokens: keywords, identifiers, numbers, operators, and delimiters. Tokens are defined using regular expressions, and the lexer is typically generated by tools like Lex or implemented manually via a deterministic finite automaton (DFA). The lexer also handles whitespace skipping, comment removal, and line/column tracking for error messages. A well-designed lexer produces a clean token stream that simplifies parser implementation.
import re
TOKEN_RE = [
('NUMBER', r'\d+'),
('IDENT', r'[A-Za-z_][A-Za-z0-9_]*'),
('PLUS', r'\+'), ('MINUS', r'-'),
('STAR', r'\*'), ('SLASH', r'/'),
('LPAREN', r'\('), ('RPAREN', r'\)'),
('SEMI', r';'), ('SKIP', r'[ \t\n]+'),
]
def tokenize(source):
tokens = []
pos = 0
while pos < len(source):
for kind, pat in TOKEN_RE:
m = re.match(pat, source[pos:])
if m:
if kind != 'SKIP':
tokens.append((kind, m.group(0)))
pos += len(m.group(0))
break
else:
raise SyntaxError(f"Unexpected char at {pos}")
return tokensSyntax Analysis and Parse Trees
The parser consumes the token stream and builds a parse tree (concrete syntax tree) according to a context-free grammar. Top-down parsing (recursive descent) is straightforward to write by hand: each nonterminal becomes a function that predicts which production to apply based on the current token. Bottom-up parsing (LR, LALR) is more powerful but harder to implement manually — tools like Yacc/Bison are typically used. The grammar must be free of left recursion and ambiguity. An abstract syntax tree (AST) strips unnecessary punctuation, keeping only the essential structure.
# Recursive descent parser for arithmetic
def parse_expr(tokens, pos):
left, pos = parse_term(tokens, pos)
while pos < len(tokens) and tokens[pos][0] in ('PLUS', 'MINUS'):
op = tokens[pos][0]
right, pos = parse_term(tokens, pos + 1)
left = ('BinOp', op, left, right)
return left, pos
def parse_term(tokens, pos):
left, pos = parse_factor(tokens, pos)
while pos < len(tokens) and tokens[pos][0] in ('STAR', 'SLASH'):
op = tokens[pos][0]
right, pos = parse_factor(tokens, pos + 1)
left = ('BinOp', op, left, right)
return left, pos
def parse_factor(tokens, pos):
if tokens[pos][0] == 'NUMBER':
return ('Num', int(tokens[pos][1])), pos + 1
if tokens[pos][0] == 'LPAREN':
expr, pos = parse_expr(tokens, pos + 1)
assert tokens[pos][0] == 'RPAREN'
return expr, pos + 1
raise SyntaxError("Expected number or (")Semantic Analysis and Type Checking
Semantic analysis verifies that the AST conforms to language rules that a context-free grammar cannot express: type compatibility, scope resolution, variable declaration before use, and function arity checking. The symbol table maps identifiers to their types, scopes, and memory locations. Type checking traverses the AST and ensures operations receive operands of compatible types — for example, rejecting the addition of a string and an integer. Attribute grammars attach semantic rules to grammar productions.
class TypeChecker:
def __init__(self):
self.symbols = {}
self.errors = []
def check_binop(self, op, left_type, right_type):
if left_type != right_type:
self.errors.append(f"Type mismatch: {left_type} vs {right_type}")
return 'error'
if op in ('PLUS', 'MINUS', 'STAR', 'SLASH'):
if left_type != 'int':
self.errors.append(f"Arithmetic on non-int {left_type}")
return 'int'
return 'error'
def check_assignment(self, name, expr_type):
if name not in self.symbols:
self.errors.append(f"Undefined variable {name}")
elif self.symbols[name] != expr_type:
self.errors.append(f"Cannot assign {expr_type} to {self.symbols[name]}")Intermediate Code Generation (Three-Address Code)
Three-address code (TAC) is a linear intermediate representation where each instruction has at most one operator and three operands: result = operand1 OP operand2. TAC decomposes complex expressions into simple atomic operations, making optimization and code generation easier. Temporary variables hold intermediate results. Control flow is represented by labeled instructions and conditional/unconditional jumps. For example, the expression a + b * c becomes t1 = b * c; t2 = a + t1.
class TACGen:
def __init__(self):
self.temps = 0
self.instructions = []
def new_temp(self):
self.temps += 1
return f"t{self.temps}"
def gen_expr(self, ast):
if ast[0] == 'Num':
return ast[1]
if ast[0] == 'BinOp':
left = self.gen_expr(ast[2])
right = self.gen_expr(ast[3])
result = self.new_temp()
op_map = {'PLUS': '+', 'MINUS': '-', 'STAR': '*', 'SLASH': '/'}
self.instructions.append(f"{result} = {left} {op_map[ast[1]]} {right}")
return resultCode Optimization
Optimization improves code performance without changing semantics. Optimizations are classified as machine-independent (applied to IR) or machine-dependent. Common techniques include constant folding (2 + 3 -> 5 at compile time), dead code elimination (removing unreachable or unused computations), common subexpression elimination (recomputing the same value), loop invariant code motion (moving invariant computations outside loops), and strength reduction (replacing expensive operations with cheaper ones).
# Constant folding and propagation
def fold_constants(tac):
optimized = []
known = {}
for instr in tac:
parts = instr.split()
if len(parts) == 5 and parts[1] == '=':
left, _, op1, op, op2 = parts
if op1.lstrip('-').isdigit() and op2.lstrip('-').isdigit():
val = eval(f"{op1} {op} {op2}")
known[left] = val
continue
op1 = str(known.get(op1, op1))
op2 = str(known.get(op2, op2))
optimized.append(f"{left} = {op1} {op} {op2}")
else:
optimized.append(instr)
return optimizedCode Generation and Register Allocation
The final phase translates optimized IR into target machine code (e.g., x86-64 or ARM). The code generator maps TAC instructions to assembly, manages registers through allocation, and handles calling conventions. Register allocation via graph coloring builds an interference graph where nodes are virtual registers and edges connect registers that are simultaneously live. Coloring the graph with K colors (where K is the number of physical registers) assigns registers; registers that cannot be colored are spilled to memory.
# x86-64 code generation for TAC
def generate_x86(tac):
asm = [".globl main", "main:", "push %rbp", "mov %rsp, %rbp"]
for instr in tac:
parts = instr.split()
if len(parts) == 5:
_, _, op1, op, op2 = parts
if op == '+':
asm.append(f" mov ${op1}, %eax")
asm.append(f" add ${op2}, %eax")
asm.append(f" mov %eax, _{parts[0]}")
elif op == '*':
asm.append(f" mov ${op1}, %eax")
asm.append(f" imul ${op2}, %eax")
asm.append(f" mov %eax, _{parts[0]}")
asm.append(" mov %eax, %eax")
asm.append(" pop %rbp")
asm.append(" ret")
return '\n'.join(asm)Frequently Asked Questions
What is the difference between a compiler and an interpreter?
A compiler translates source code to machine code before execution, producing a standalone binary. An interpreter executes source code directly without producing a separate binary, typically using a runtime environment. Compilers offload analysis upfront; interpreters enable dynamic behavior like eval().
What is a context-free grammar and why is it important?
A context-free grammar (CFG) defines the syntax structure of a programming language using production rules (e.g., expr -> term + expr). It is the foundation for parsers because it describes recursive structure without depending on context, enabling automated parser generation.
How does a just-in-time (JIT) compiler work?
A JIT compiler sits between interpretation and ahead-of-time compilation. It converts bytecode or IR into native machine code at runtime, often profiling execution to optimize hot code paths. The JVM's C2 compiler and V8's TurboFan are prominent examples.
What is SSA form and why is it used in optimization?
Static Single Assignment (SSA) form ensures each variable is assigned exactly once, with phi functions at control-flow merge points. SSA simplifies data-flow analysis because definitions and uses are explicit, enabling efficient constant propagation, dead code elimination, and loop optimization.
Originally published on Ayodhyyya. Last updated June 1, 2026.