The Anatomy of a Compiler

A compiler is a program that takes source code written in one language (the source language) and produces equivalent code in another language (the target language), usually at a lower level of abstraction. The key word is equivalent: the behavior of the output must faithfully represent the intent of the input.

It is helpful to distinguish related tools:

• A compiler translates source → target (often native machine code), where translation happens before execution. The user runs the compiled binary.
• An interpreter reads source and executes it directly, without generating a separate target program. Python's CPython is primarily an interpreter.
• A transpiler (source-to-source compiler) translates between languages at similar abstraction levels: TypeScript → JavaScript, or C++ → C.
• A JIT (Just-In-Time) compiler compiles at runtime, after observing which paths are hot; Java's HotSpot and V8 for JavaScript use JIT.

Despite these variations, all of them share the same core pipeline structure. The distinction is mostly about when the compilation happens and what the target looks like.

The pipeline is traditionally split into three major sections:

1. Front end — understands the source language. Language-specific.
2. Middle end (optimizer) — transforms the program for efficiency, working on a language-neutral Intermediate Representation (IR).
3. Back end — generates code for a specific target machine. Machine-specific.

This three-part split is why LLVM can support dozens of languages (each with its own front end) and dozens of hardware targets (each with its own back end) by sharing a single optimizer. It is a brilliant application of the interface-segregation principle.

# The pipeline in pseudocode
source_text = read_file("hello.c")
tokens      = lex(source_text)          # front end
ast         = parse(tokens)             # front end
ast         = semantic_analysis(ast)    # front end
ir          = generate_ir(ast)          # front end → middle
ir          = optimize(ir)             # middle end
machine     = codegen(ir)              # back end
write_file("hello.o", machine)

The first phase of compilation is lexical analysis, performed by the lexer (also called a scanner or tokenizer). Its job is to convert the raw stream of characters in the source file into a flat sequence of meaningful units called tokens.

A token is a pair (kind, value). For example, the C source fragment int x = 42; produces:

KEYWORD("int")  IDENT("x")  EQ("=")  NUMBER(42)  SEMI(";")

The lexer also discards whitespace and comments, which are irrelevant to meaning.

Lexers are almost universally described by regular expressions and implemented as deterministic finite automata (DFAs). A tool like flex takes a list of regex → action rules and generates a DFA-based C function. Modern hand-written lexers (like Clang's) are also essentially DFAs, unrolled for speed.

Why a DFA? Because regular languages are exactly the class of patterns that can be recognized by scanning left-to-right with finite memory — precisely what lexing requires. You do not need to remember where you were three tokens ago; you only need your current state.

Common token categories: keywords (if, while, return), identifiers, integer/float literals, string literals, operators, punctuation.

Error recovery: if the lexer encounters a character that does not start any valid token, it must report an error. Good lexers try to recover and continue scanning so the user sees all their errors at once rather than just the first one.

Maximal munch rule: when multiple tokens could match starting at the current position, the lexer always takes the longest one. This is why == is parsed as EQ_EQ, not EQ followed by EQ.

import re

TOKEN_SPEC = [
    ('NUMBER',   r'\d+(\.\d*)?'),   # integer or decimal
    ('IDENT',    r'[A-Za-z_]\w*'),  # identifier
    ('OP',       r'[+\-*/=<>!]+'),  # operators
    ('LPAREN',   r'\('),
    ('RPAREN',   r'\)'),
    ('SEMI',     r';'),
    ('SKIP',     r'[ \t\n]+'),      # whitespace — discard
    ('MISMATCH', r'.'),             # anything else → error
]

def tokenize(code):
    pattern = '|'.join('(?P<%s>%s)' % pair for pair in TOKEN_SPEC)
    for mo in re.finditer(pattern, code):
        kind = mo.lastgroup
        value = mo.group()
        if kind == 'SKIP':
            continue
        elif kind == 'MISMATCH':
            raise SyntaxError(f'Unexpected character {value!r}')
        yield (kind, value)

for tok in tokenize('x = 42 + y;'):
    print(tok)

Given the token stream, the parser reconstructs the hierarchical structure of the program. It is answering the question: which tokens are arguments to which operators? Which statements are inside which loops? The output is a tree called the Abstract Syntax Tree (AST).

Why a tree? Because programs have nested structure (expressions inside statements inside functions inside modules), and trees are the natural data structure for hierarchical containment.

Parsers are described by context-free grammars (CFGs). A CFG is a set of production rules, e.g.:

expr  → expr '+' term  |  term
term  → term '*' factor  |  factor
factor → NUMBER | '(' expr ')'

Note that this grammar encodes operator precedence (multiplication binds tighter than addition) through the grammar structure itself — a beautiful trick.

Two major families of parsers:

• Top-down (recursive descent): write one function per nonterminal. Easy to write by hand, predictable, used in GCC and Clang. LL(k) grammars.
• Bottom-up (LR/LALR): shift-reduce automaton. More powerful (can handle left-recursive grammars), generated by tools like yacc/bison. LALR(1) grammars.

The AST is abstract (as opposed to a Concrete Syntax Tree) because it discards tokens that are structurally unimportant (parentheses, semicolons, commas) while keeping everything semantically significant.

For 2 + 3 * 4, the AST is:

    Add
   /   \
  2    Mul
      /   \
     3     4

Evaluating the AST in post-order gives the correct result because multiplication naturally ends up deeper in the tree.

# Tiny recursive-descent parser for additive/multiplicative exprs
# Grammar:
#   expr   -> term (('+' | '-') term)*
#   term   -> factor (('*' | '/') factor)*
#   factor -> NUMBER | '(' expr ')'

from dataclasses import dataclass
from typing import Union

@dataclass
class BinOp:
    op: str
    left: 'Expr'
    right: 'Expr'

@dataclass
class Num:
    value: float

Expr = Union[BinOp, Num]

class Parser:
    def __init__(self, tokens):
        self.tokens = list(tokens)
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self, expected=None):
        tok = self.tokens[self.pos]
        if expected and tok[0] != expected:
            raise SyntaxError(f'Expected {expected}, got {tok}')
        self.pos += 1
        return tok

    def parse_factor(self):
        tok = self.peek()
        if tok[0] == 'NUMBER':
            self.consume()
            return Num(float(tok[1]))
        elif tok[0] == 'LPAREN':
            self.consume('LPAREN')
            node = self.parse_expr()
            self.consume('RPAREN')
            return node
        raise SyntaxError(f'Unexpected token {tok}')

    def parse_term(self):
        node = self.parse_factor()
        while self.peek() and self.peek()[1] in ('*', '/'):
            op = self.consume()[1]
            node = BinOp(op, node, self.parse_factor())
        return node

    def parse_expr(self):
        node = self.parse_term()
        while self.peek() and self.peek()[1] in ('+', '-'):
            op = self.consume()[1]
            node = BinOp(op, node, self.parse_term())
        return node

Parsing only checks syntax — whether the tokens form a valid parse tree according to the grammar. Semantic analysis checks meaning: are the types correct? Is every variable declared before use? Are function calls passing the right number of arguments? Does a return statement appear inside a function?

Semantic analysis is divided into two sub-phases:

1. Name resolution (scope analysis): Every identifier in the program must be bound to a specific declaration. This is done by traversing the AST and maintaining a symbol table — a scoped data structure mapping names to their declarations. When you enter a new scope (e.g., a { in C), you push a new frame; when you leave, you pop it. Unresolved names become errors.

2. Type checking: After names are resolved, the compiler walks the AST again and assigns a type to every expression. The rules are defined by the language's type system. For example, in a statically typed language: you cannot add a string to an integer (unless the language defines that overload), you cannot call a non-function value, you cannot assign a float* to an int* without a cast.

The symbol table stores, for each name: its type, its storage class (local, global, parameter), its scope level, and sometimes its memory layout.

Type checking can be local (each expression node's type depends only on its children) or global (may require solving constraint systems — used in Hindley-Milner type inference for ML/Haskell).

Decorated AST: the output of semantic analysis is the same tree, but with type annotations attached to each node. This annotated tree is passed to the IR generator.

Semantic errors are the ones you most often see as a programmer: TypeError: unsupported operand type(s), use of undeclared identifier 'x', too many arguments to function call.

# Simplified symbol table with lexical scoping
class SymbolTable:
    def __init__(self, parent=None):
        self.table = {}          # name -> {type, kind, ...}
        self.parent = parent     # enclosing scope

    def define(self, name, info):
        if name in self.table:
            raise NameError(f"Redefinition of '{name}'")
        self.table[name] = info

    def lookup(self, name):
        if name in self.table:
            return self.table[name]
        if self.parent:
            return self.parent.lookup(name)  # walk up scopes
        raise NameError(f"Undefined name '{name}'")

# Usage:
global_scope = SymbolTable()
global_scope.define('x', {'type': 'int', 'kind': 'var'})

func_scope = SymbolTable(parent=global_scope)
func_scope.define('y', {'type': 'float', 'kind': 'param'})

print(func_scope.lookup('x'))  # found in parent scope
print(func_scope.lookup('y'))  # found locally

After the front end, the compiler translates the AST into an Intermediate Representation (IR) — a lower-level, language-neutral representation that is still above machine code. The IR is the lingua franca of the middle end.

Why have an IR at all? Without it, you need N×M translators for N source languages and M targets. With an IR, you need N front ends and M back ends. LLVM has ~30 front ends (C, C++, Rust, Swift, …) and ~10 back ends (x86, ARM, RISC-V, WebAssembly, …), all sharing one IR and one optimizer.

Three-Address Code (TAC): The most common IR style. Each instruction has at most one operator and at most three operands (two sources, one destination). Every complex expression is broken into a sequence of simple assignments using temporary variables:

x = a + b * c  →   t1 = b * c
                    t2 = a + t1
                    x  = t2

This looks like assembly but is still abstract (unbounded registers, no calling convention).

Static Single Assignment (SSA) form: A refinement of TAC where every variable is assigned exactly once. If a variable is assigned in two branches of an if, a special φ (phi) function merges them at the join point. SSA makes many optimization algorithms dramatically simpler because each use has exactly one definition. LLVM IR, GCC's GIMPLE, and most modern IRs are in SSA form.

Control Flow Graph (CFG): The IR is organized not as a flat list but as a CFG: a directed graph where nodes are basic blocks (maximal sequences of instructions with no branches except at the end) and edges represent possible control flow. Optimizations operate on this graph.

LLVM IR example for int add(int a, int b) { return a + b; }:

define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}

This is typed, explicit about bit widths, and already in SSA form.

# Naive AST-to-TAC lowering for arithmetic expressions

class TACGenerator:
    def __init__(self):
        self.instructions = []
        self.temp_count = 0

    def new_temp(self):
        self.temp_count += 1
        return f't{self.temp_count}'

    def emit(self, instruction):
        self.instructions.append(instruction)
        return instruction

    def generate(self, node):
        if isinstance(node, Num):
            return str(node.value)
        elif isinstance(node, BinOp):
            left  = self.generate(node.left)
            right = self.generate(node.right)
            t = self.new_temp()
            self.emit(f'{t} = {left} {node.op} {right}')
            return t

# Example: generate TAC for (2 + 3) * 4
gen = TACGenerator()
expr = BinOp('*', BinOp('+', Num(2), Num(3)), Num(4))
result = gen.generate(expr)
for instr in gen.instructions:
    print(instr)
# Output:
# t1 = 2.0 + 3.0
# t2 = t1 * 4.0

The optimizer (middle end) applies a sequence of passes to the IR, each of which rewrites the program to be faster, smaller, or both, while preserving semantics. This is where compilers earn their reputation for intelligence.

Passes are typically organized as a pipeline over the CFG. Each pass has a fixed-point loop: it keeps iterating until no more changes can be made.

Key classical optimizations:

• Constant folding: replace an expression whose operands are all compile-time constants with its result. 3 + 4 → 7. Trivial but very common.

• Constant propagation: if a variable is assigned a constant and never reassigned, replace all uses with the constant. Enables further folding.

• Dead code elimination (DCE): remove instructions whose results are never used. After constant propagation, many branches become if (false) and their bodies are dead.

• Common subexpression elimination (CSE): if the same computation appears twice and its operands have not changed between occurrences, reuse the first result instead of recomputing.

• Loop-invariant code motion (LICM): move computations whose value does not change across loop iterations to before the loop. E.g., if n is not modified inside a loop, x = a * n can be hoisted out.

• Inlining: replace a function call with the body of the called function. Removes call overhead and enables more optimization across the call boundary. Aggressive inlining can increase code size, so there is a cost-benefit analysis.

• Loop unrolling: replicate the loop body multiple times to reduce branch overhead and expose instruction-level parallelism.

• Strength reduction: replace expensive operations with cheaper equivalents. i * 4 → i << 2. In loops, i*stride can be replaced by an accumulator.

Optimizations interact and compose. Inlining followed by constant propagation followed by DCE is a standard chain that often eliminates whole computations that were opaque across a function boundary.

Optimization levels: -O0 (no optimization, fast compile), -O1 (basic), -O2 (most safe opts), -O3 (aggressive, may increase size), -Os (optimize for size), -Oz (aggressively minimize size).

# Demonstrating constant folding + dead code elimination
# BEFORE optimization:
x = 3 + 4      # constant fold → x = 7
y = x * 2      # constant prop → y = 7 * 2 → y = 14
if False:      # dead branch (after folding)
    z = expensive_computation()   # dead code — eliminated
return y

# AFTER optimization (what the compiler effectively produces):
return 14

Many optimizations require knowledge that cannot be determined by looking at a single instruction in isolation. Dataflow analysis is the framework for computing program-wide properties by propagating information along the CFG.

The key idea: associate a lattice with each program point. A lattice is a partially ordered set with join (⊔) and meet (⊓) operations. Information flows from predecessors to successors (forward analysis) or from successors to predecessors (backward analysis), and we iterate until a fixed point is reached.

Liveness analysis (backward): a variable is live at a point if it may be used before being redefined. Used for register allocation (only live variables need registers) and DCE (a definition of a dead variable is useless).

• LIVE_IN[B] = USE[B] ∪ (LIVE_OUT[B] − DEF[B])
• LIVE_OUT[B] = ∪ LIVE_IN[S] for each successor S of B

Reaching definitions (forward): a definition of variable x at point d reaches a later point p if there is a path from d to p with no other definition of x. Used for constant propagation and copy propagation.

Available expressions (forward): an expression is available at a point if it has been computed on every path to that point and its operands have not been redefined. Used for CSE.

All three are instances of the same framework: choose the domain (sets of variables/definitions/expressions), the transfer functions (how a basic block changes the set), and the direction. The worklist algorithm efficiently computes the fixed point by only re-processing blocks whose inputs have changed.

Dataflow analysis is a profound connection between compiler optimization and abstract interpretation — a formal theory of approximating program semantics with computable abstractions.

# Worklist algorithm for liveness analysis (backward dataflow)
def liveness_analysis(blocks, successors, use, defs):
    """
    blocks: list of basic block names
    successors: dict block -> list of successor blocks
    use[b]: set of vars used in b before any def
    defs[b]: set of vars defined in b
    Returns: live_in, live_out dicts
    """
    live_in  = {b: set() for b in blocks}
    live_out = {b: set() for b in blocks}
    worklist = set(blocks)

    while worklist:
        b = worklist.pop()
        # live_out[b] = union of live_in of all successors
        new_out = set().union(*(live_in[s] for s in successors[b]))
        # live_in[b]  = use[b] U (live_out[b] - def[b])
        new_in  = use[b] | (new_out - defs[b])
        if new_in != live_in[b] or new_out != live_out[b]:
            live_in[b]  = new_in
            live_out[b] = new_out
            # predecessors may need updating — add them
            # (omitted for brevity; tracked via pred dict)
    return live_in, live_out

The back end translates IR into actual machine code for a specific target. This is where the abstract world of IR meets the concrete reality of CPUs with fixed registers, memory hierarchies, and instruction encodings.

Code generation has three major sub-problems:

1. Instruction selection: Choose which machine instructions implement each IR operation. A single IR instruction may map to zero, one, or several machine instructions. This is typically done by pattern matching on IR trees (the BURG algorithm, or hand-written peephole matching in LLVM's SelectionDAG).

2. Register allocation: CPUs have a small, fixed number of registers (x86-64 has 16 general-purpose registers; ARM64 has 31). The IR uses an unlimited number of virtual registers. Register allocation assigns virtual registers to physical registers, spilling (writing to memory on the stack) when the demand exceeds supply. This is equivalent to graph coloring: build an interference graph where two virtual registers are connected if they are simultaneously live, then try to color the graph with K colors (K = number of physical registers). Graph coloring is NP-complete in general, but linear-time heuristics (Chaitin-Briggs, Linear Scan) work well in practice.

3. Instruction scheduling: Modern CPUs can execute multiple instructions per clock and have deep pipelines with data hazards. The scheduler reorders instructions (without violating data dependencies) to maximize pipeline utilization and hide memory latency. This is a topological sort of the dependency graph, heuristically optimized.

After these three passes, the back end emits machine code bytes (or an assembly .s file that is then assembled by as). The linker then combines multiple object files, resolves symbol references, and produces the final executable.

# Pseudocode: naive register allocator (linear scan)
def linear_scan_allocate(intervals, num_regs):
    """
    intervals: list of (start, end, vreg) sorted by start
    Returns: assignment dict vreg -> physical_reg (or 'spill')
    """
    active    = []          # list of (end, vreg, preg)
    free_regs = list(range(num_regs))
    assignment = {}

    for (start, end, vreg) in intervals:
        # Expire old intervals that ended before this one starts
        active = [(e, v, r) for (e, v, r) in active if e > start]
        freed  = [r for (e, v, r) in active if e <= start]
        free_regs.extend(freed)

        if free_regs:
            preg = free_regs.pop()
            assignment[vreg] = preg
            active.append((end, vreg, preg))
            active.sort()               # keep sorted by end
        else:
            # Spill: evict the interval that ends latest
            spill_end, spill_v, spill_r = active[-1]
            if spill_end > end:
                assignment[vreg]     = spill_r
                assignment[spill_v]  = 'spill'
                active[-1] = (end, vreg, spill_r)
                active.sort()
            else:
                assignment[vreg] = 'spill'
    return assignment

The symbol table is a central data structure used across multiple compiler phases (semantic analysis, IR generation, codegen). It is a mapping from identifiers to their properties: type, storage class (local/global/static), memory layout, linkage, etc.

In languages with lexical scoping (C, Java, Python, Rust, …), the symbol table is organized as a stack of hash maps — one per scope. When you enter a new scope ({), push a new map; when you exit (}), pop it. Name lookup walks the stack from top (innermost) to bottom (global).

For object-oriented languages, symbol tables also store class hierarchies and method tables (vtables in C++ / Java). A method call obj.foo() is resolved by looking up obj's type in the symbol table, then finding foo in that class's method table.

The symbol table bridges front end and back end: the front end populates it with type and scope information, while the back end queries it to determine how to allocate and address each variable (stack slot, global address, or register).

In many compilers, the symbol table is logically part of the decorated AST: each AST node that introduces or references a name has a pointer into the symbol table. This makes type information instantly available to all later passes without re-doing name resolution.

The word pass refers to a single traversal of (some representation of) the program to accomplish a specific task. Each phase of the compiler is typically implemented as one or more passes.

Passes compose: the output of one pass is the input of the next. This composability is not accidental — it follows from the single-responsibility principle applied to program transformation. A pass that inlines small functions does not need to know about register allocation; a register allocator does not need to know about loop-invariant code motion.

In modern compiler frameworks like LLVM, passes are first-class objects. The PassManager chains them in a defined order. Users can add custom passes (e.g., a sanitizer pass that inserts bounds checks) without touching the rest of the compiler. The pass infrastructure also supports pass managers within pass managers: a loop pass manager can run multiple loop-level passes for each loop without re-scanning the whole module.

Passes are further classified by the scope at which they operate:

• Instruction-level passes: look at one instruction at a time (peephole optimization).
• Basic-block passes: look at one basic block at a time.
• Function passes: look at one function at a time (most optimizations).
• Module passes: look at the entire compilation unit (interprocedural optimizations, link-time optimization).

Link-time optimization (LTO) is an extreme example: the entire program is compiled to bitcode (LLVM IR), linked into a single IR module, and then all interprocedural passes (including inlining across translation units) are applied before final codegen. This can produce dramatic speedups for programs whose hot paths cross file boundaries.