What compilers do and how they are built

A compiler translates a program written in one language, the source language, into an equivalent program in another, the target language, usually a lower-level one that a machine can execute. That one sentence hides a remarkable amount of engineering. A production compiler such as GCC or Clang is millions of lines of code, accepts programs that are themselves millions of lines long, must never change what a correct program means, reports helpful errors for incorrect ones, and still produces machine code that is often faster than what a skilled person would write by hand. This course is about how that is done. We build, lesson by lesson, a compiler for a small language called Tern, and along the way meet the theory that makes each phase reliable: regular expressions and automata for scanning, context-free grammars for parsing, type systems for checking, graphs and lattices for optimization, and graph colouring for register allocation.

You have met parts of this story before. CMPUT-325 (lessons 2, 7, 8 and 10) introduced grammars, recursive-descent parsing, type inference and garbage collection from the point of view of language design, and its capstone built an interpreter for a language called Mini. CMPUT-229 (lessons 5, 7 and 8) showed RISC-V machine code, calling conventions and the four stages of the C toolchain from the hardware side. This course sits between them: it is about the translator itself, and about doing translation well. Where an earlier course already explains an idea, we cite it and build on it rather than repeating it.

Translators: compilers, interpreters and hybrids

An interpreter executes a program directly, reading its representation and carrying out each operation as it goes. A compiler translates the whole program ahead of time and leaves execution to something else. The distinction is less sharp than textbooks once suggested, because almost every modern implementation is a hybrid. CPython compiles source code to bytecode and then interprets the bytecode. Java compiles source to JVM bytecode ahead of time; the JVM interprets that bytecode at first, then compiles the frequently executed parts to machine code while the program runs. JavaScript engines such as V8 parse source, interpret a bytecode, and recompile hot functions with progressively more aggressive optimizing compilers. A just-in-time (JIT) compiler is simply a compiler that runs during execution, so it can use information, such as the actual types flowing through a function, that an ahead-of-time compiler cannot see.

Why compile at all, when interpreting is simpler? Speed is the obvious answer: an interpreter pays a dispatch cost on every operation, decoding what to do next, while compiled code simply does it. A compiler can also analyse the whole program, find errors before it runs, and transform it in ways an interpreter has no time for. Interpreters win on start-up time, portability and simplicity, and they make debugging and dynamic features easy. The hybrids above exist because each approach is best for part of a program's life.

The phases of a compiler

Compilers are organized as a pipeline of phases, each transforming one representation of the program into another. The classic division, which goes back to the first FORTRAN compiler (1957) and was codified in the textbooks of the 1970s and 1980s, has three parts. The front end understands the source language: it reads characters, groups them into tokens, recognizes the grammatical structure, and checks that the program obeys the language's rules. The middle end, or optimizer, improves the program in a form independent of both source and target. The back end maps the improved program onto a particular machine, choosing instructions, assigning registers and laying out memory.

Lexical analysis (scanning) turns a stream of characters into a stream of tokens: identifiers, keywords, numbers, operators and punctuation, with whitespace and comments discarded. Syntax analysis (parsing) checks that the tokens form a grammatically valid program and builds a tree that records its structure. Semantic analysis checks the rules that grammars cannot express conveniently: every name is declared before use, types match, functions are called with the right number of arguments. The output of the front end is an annotated abstract syntax tree. The middle end lowers that tree into an intermediate representation (IR), typically a sequence of simple instructions grouped into a control-flow graph, and runs optimization passes over it. The back end selects machine instructions, allocates the unlimited temporaries of the IR to a handful of physical registers, and emits assembly or an object file.

The program below is a complete compiler for arithmetic expressions in about fifty lines. It has a scanner, a recursive-descent parser, a code generator for a stack machine, and the stack machine itself, so we can watch an expression pass through every phase.

# A complete (tiny) compiler for arithmetic: source text -> tokens -> AST ->
# stack-machine code -> execution. Every real compiler has these same phases.
import re
SRC = "2 + 3 * (10 - 4) / 2"

def lex(src):                                   # phase 1: characters -> tokens
    toks = []
    for num, op, bad in re.findall(r"\s*(?:(\d+)|([-+*/()])|(\S))", src):
        if bad: raise SyntaxError(f"unexpected character {bad!r}")
        toks.append(("NUM", int(num)) if num else ("OP", op))
    return toks + [("EOF", None)]

def parse(toks):                                # phase 2: tokens -> tree
    pos = 0
    def peek(): return toks[pos]
    def take():
        nonlocal pos; pos += 1; return toks[pos - 1]
    def expr():                                 # expr := term (('+'|'-') term)*
        node = term()
        while peek() in (("OP", "+"), ("OP", "-")):
            node = (take()[1], node, term())
        return node
    def term():                                 # term := atom (('*'|'/') atom)*
        node = atom()
        while peek() in (("OP", "*"), ("OP", "/")):
            node = (take()[1], node, atom())
        return node
    def atom():
        kind, val = take()
        if kind == "NUM": return val
        if val == "(":
            node = expr(); assert take() == ("OP", ")"), "expected )"; return node
        raise SyntaxError(f"unexpected {val!r}")
    tree = expr(); assert peek()[0] == "EOF"; return tree

def gen(node, code):                            # phase 3: tree -> instructions
    if isinstance(node, int):
        code.append(("PUSH", node))
    else:
        op, a, b = node
        gen(a, code); gen(b, code)
        code.append(({"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}[op],))
    return code

def run(code):                                  # the "machine"
    st = []
    for ins in code:
        if ins[0] == "PUSH": st.append(ins[1]); continue
        b, a = st.pop(), st.pop()
        st.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "DIV": a // b}[ins[0]])
    return st.pop()

toks = lex(SRC); tree = parse(toks); code = gen(tree, [])
print("tokens:", " ".join(str(v) for k, v in toks if k != "EOF"))
print("tree:  ", tree)
print("code:  ", "; ".join(" ".join(map(str, i)) for i in code))
print("result:", run(code))

tokens: 2 + 3 * ( 10 - 4 ) / 2
tree:   ('+', 2, ('/', ('*', 3, ('-', 10, 4)), 2))
code:   PUSH 2; PUSH 3; PUSH 10; PUSH 4; SUB; MUL; PUSH 2; DIV; ADD
result: 11

The parser has already resolved precedence: the tree multiplies 3 by the parenthesized difference before dividing and adding, and the generated code reflects that order. Even this toy shows two properties of every real compiler. First, each phase has a narrow interface, a list of tokens, a tree, a list of instructions, so phases can be written, tested and replaced independently. Second, meaning is preserved: the code computes exactly what the expression denotes. Note too what is missing: there are no variables, so no symbol table; one type, so no type checker; no control flow, so no graph; and a stack machine, so no register allocation. The rest of the course adds each of these.

Why the structure matters: m front ends and n back ends

Separating the front, middle and back ends is not just tidy; it changes the economics of building compilers. Without a shared intermediate representation, supporting m source languages on n processors would need m × n separate compilers. With one, it needs m front ends and n back ends that meet in the middle, and every optimization written once for the IR benefits every pair. This is the design of GCC, whose front ends for C, C++, Fortran, Ada, Go and others share the GIMPLE and RTL representations, and above all of LLVM, begun by Chris Lattner and Vikram Adve at the University of Illinois in 2000. LLVM's IR is a well-documented, typed, static single assignment language (lesson 8) that front ends for C, C++, Rust, Swift, Julia, Zig and many others generate, and that back ends for x86-64, AArch64, RISC-V, WebAssembly, GPUs and more consume. Its success is why building a credible compiler for a new language is now a project for a small team rather than a large company.

The Tern language

Tern is the language we compile in this course. It is deliberately small, but it has the features that make real compilation interesting: integer and boolean types, arrays, local variables, functions with parameters and recursion, if and while statements, and the usual operators with conventional precedence. Its syntax is in the C family, with types written after names as in Rust, Go and TypeScript. Here is a complete Tern program.

fn fact(n: int) -> int {
    var r: int = 1;
    while n > 1 {
        r = r * n;
        n = n - 1;
    }
    return r;
}

fn main() -> int {
    var a: [int] = array(5);
    var i = 0;
    while i < len(a) {
        a[i] = fact(i + 1);
        i = i + 1;
    }
    print(a[4]);       // 120
    return 0;
}

Tern's rules are those you would expect. Every variable is declared with var before use, either with an explicit type or with an initializer from which the type is inferred, as in var i = 0. Conditions of if and while must be booleans; there is no automatic conversion from integers as in C. The built-ins array(n), len(a) and print(x) create an integer array of length n, return its length and print a value. Every function declares its return type, and the program starts at main. Unlike CMPUT-325's Mini, which was expression-oriented and functional, Tern is imperative: it has mutable variables and loops, because those are what make control-flow graphs, SSA form and register allocation worth studying.

A short history

The first compilers were written when most experts doubted that machine-generated code could compete with hand-written assembly. Grace Hopper's A-0 system (1952) linked subroutines automatically, and she argued tirelessly that programs should be written in something closer to English. John Backus's team at IBM delivered the FORTRAN I compiler in 1957 after some 18 person-years of work; its optimizer was so good that it won over sceptics and established high-level languages. The 1960s brought formal grammars, with Backus–Naur Form introduced for ALGOL 60, and parsing theory: Donald Knuth defined LR parsing in 1965. In the 1970s, Frances Allen and John Cocke at IBM laid the foundations of program optimization with control-flow graphs and data-flow analysis; Allen became the first woman to receive the Turing Award, in 2006, for this work. Tools such as lex and yacc (Bell Labs, 1975) made scanners and parsers routine, and GCC (1987) gave the world a free, retargetable compiler. Static single assignment form (IBM, late 1980s, published 1991), the LLVM project (2000 onward) and JIT compilers for Java and JavaScript define the modern era.

Compilers are also a remarkable example of theory paying off in practice. Regular languages and finite automata, context-free grammars and pushdown automata, lattices and fixed points, and graph colouring were all studied as mathematics before, or alongside, their use in compilers. CMPUT-474 treats the theory of automata and formal languages rigorously; here we use those results as tools.

Bootstrapping and self-hosting

A compiler is itself a program, so it must be written in some language and compiled by some compiler. A compiler written in its own source language is called self-hosting: GCC is written in C and C++, rustc in Rust, the Go compiler in Go. The obvious puzzle, how the first one was compiled, is solved by bootstrapping. One writes a minimal compiler for a subset of the language in an existing language, uses it to compile a better compiler written in the subset, and repeats until the full compiler compiles itself. GCC's build still demonstrates this: it compiles itself in three stages and checks that stage 2 and stage 3 produce identical object code, a strong test that the compiler translates its own source correctly.

Self-hosting raises a subtle security question that Ken Thompson described in his 1984 Turing Award lecture, Reflections on Trusting Trust. A compiler binary could be modified to insert a back door whenever it compiles a login program, and to reinsert that modification whenever it compiles a compiler, so that no trace remains in any source code. The defence, called diverse double-compiling, compiles the compiler's source with an independent compiler and checks that the results match; it is one reason reproducible builds matter for software supply chains (CISSP-117 discusses supply chain security at the governance level).

What makes a good compiler

Correctness comes first: a compiler must preserve the meaning of every valid program, and a compiler bug is far worse than a slow compiler because programmers trust the translation and rarely suspect it. After correctness come the qualities users notice. Diagnostics should identify the real problem, point to the right place, and suggest a fix; modern compilers such as rustc and Clang invest heavily in this. Compile time matters for large programs and for interactive tools; build systems compile millions of lines many times a day. Generated code should be fast, small and predictable. And the compiler should be maintainable, because languages, processors and security requirements keep changing.

These goals conflict. Aggressive optimization costs compile time and can make debugging harder, because the code no longer corresponds line by line to the source. That is why compilers offer optimization levels such as -O0 (fast compilation, easy debugging), -O2 (the usual release setting) and -O3 or -Os (more speed or less size). Language definitions also leave room for the compiler: in C, signed integer overflow is undefined behaviour, which lets the optimizer assume it never happens. That assumption enables real speed-ups, such as simplifying loop bounds, but it surprises programmers whose code relied on wrap-around. Understanding what the compiler may and may not assume is part of writing correct low-level code.

The command below compiles a small C function to RISC-V assembly at two optimization levels with Clang, keeping only the instructions. At -O0 the compiler keeps every variable in memory, loading and storing it on each use so a debugger can inspect it; at -O2 the loop is rewritten to keep everything in registers.

cat sum.c
clang --target=riscv64 -O0 -S sum.c -o - | grep -E "^\s+[a-z]" | grep -v "^\s*\." | wc -l
clang --target=riscv64 -O2 -S sum.c -o - | grep -E "^\s+[a-z]" | grep -v "^\s*\."

$ cat sum.c
int sum_to(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++)
        s += i;
    return s;
}
$ clang --target=riscv64 -O0 -S sum.c -o - | grep -E "^\s+[a-z]" | grep -v "^\s*\." | wc -l
28
$ clang --target=riscv64 -O2 -S sum.c -o - | grep -E "^\s+[a-z]" | grep -v "^\s*\."
	blez	a0, .LBB0_2
	slli	a1, a0, 1
	addi	a2, a0, -1
	addi	a0, a0, -2
	slli	a0, a0, 32
	slli	a2, a2, 32
	mulhu	a0, a2, a0
	srli	a0, a0, 1
	add	a0, a0, a1
	addiw	a0, a0, -1
	ret
	li	a0, 0
	ret

The unoptimized version has 28 instructions, including a loop that runs n times and loads and stores s and i from the stack on every iteration. The optimized version has no loop at all. Clang has recognized that the loop computes a closed-form sum and replaced it with arithmetic that runs in constant time regardless of n, an optimization called scalar evolution, applied by LLVM's induction-variable analysis. A compiler that can do this has understood the loop in a precise mathematical sense. By lesson 11 you will know how such analyses are built.

The compiler ecosystem in 2026

As of late 2026, the dominant ahead-of-time compilers are GCC (version 16 released in 2026) and LLVM/Clang (version 22 released in early 2026), with Microsoft's MSVC on Windows. LLVM also underpins rustc, Swift, Zig, Julia and the GPU compilers of most vendors, and its MLIR framework (multi-level IR, from Google, 2019) is used to build compilers for machine learning, from TensorFlow and PyTorch graphs down to accelerator code. WebAssembly, a portable low-level target for browsers and servers, reached version 3.0 in September 2025, adding garbage-collected types, tail calls, exception handling and 64-bit memories, which makes it a practical target for languages such as Kotlin, Dart and OCaml as well as C and Rust. CPython 3.13 (2024) added an experimental copy-and-patch JIT compiler, still optional in 3.14. JIT compilation therefore now spans Java, JavaScript, Python, .NET and Lua. The fundamentals in this course apply to all of them.

Compiler construction is also increasingly used outside compilers proper. Database systems compile SQL queries to machine code; machine learning frameworks compile model graphs; build systems, linters, formatters and language servers all reuse the front-end techniques of scanning, parsing and semantic analysis; and security tools apply the static analyses of lesson 11 to find bugs. Large language model assistants now help write code, but they rely on the same tools to check it: a model's suggestion is only useful once a compiler has parsed, type-checked and translated it.

Worked examples