From Source Code
to Silicon

Maximal Munch

Lexers use the longest match rule: given >>=, the lexer will produce one RIGHT_SHIFT_ASSIGN token rather than GT, GT, EQ. This is why C++ required a space in vector<vector<int> > before C++11 — the lexer would greedily match >> as a right-shift operator.

Lookahead Budget

Most tokens need only 1–2 characters of lookahead to disambiguate. But some languages break this: Python's significant indentation requires tracking a stack of indent levels, making the lexer context-sensitive. C's type/identifier ambiguity (T * x; — declaration or multiplication?) leaks all the way into parsing.

Recursive Descent

The workhorse of hand-written parsers. Each grammar rule becomes a function. The call stack mirrors the parse tree. Easy to write, easy to debug, good error messages. Used by GCC (since 2004), Clang, Rust, Go, Swift, V8. Limitation: can't directly handle left-recursive grammars without rewriting them.

Pratt Parsing

A top-down operator-precedence parser — elegantly handles infix, prefix, postfix, and mixfix expressions. Each token has a binding power (numeric precedence) and optional nud (null denotation) and led (left denotation) handlers. Dramatically simplifies expression parsing. Used in V8, Rust (partially), and many interpreters.

LR / LALR Parsers

Table-driven shift-reduce parsers generated by tools like Yacc, Bison, ANTLR. Can handle a wider class of grammars (including left recursion) but produce famously inscrutable error messages. The parse table itself can be enormous — LALR(1) reduces it at the cost of some expressive power. Used by older GCC, Ruby (LALR), PostgreSQL's SQL parser.

PEG / Packrat

Parsing Expression Grammars use ordered choice (/) instead of ambiguous alternation (|). Packrat parsing memoizes intermediate results for guaranteed O(n) time at the cost of O(n) memory. Never ambiguous by construction, but the ordered choice can make some grammars behave unintuitively. Used in Lua, Pest (Rust).

LLVM IR

The most influential compiler IR in production. A typed, SSA-based, low-level instruction set. Target-independent but close enough to hardware for efficient lowering. Features: explicit types, getelementptr for pointer arithmetic, intrinsics for target-specific operations. Used by Clang, Rust, Swift, Julia, Zig, and over 30 other language frontends.

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

Sea of Nodes

Used by V8 (TurboFan), HotSpot C2, and Graal. Instead of a linear instruction list within basic blocks, all values and effects float in a graph. Nodes have data edges (value dependencies) and effect/control edges. This representation makes optimizations like GVN, loop-invariant code motion, and scheduling fall out naturally from graph rewriting — but it's notoriously hard to debug.

Stack Machines

Operands are implicit — they live on a virtual stack. Instructions like PUSH, ADD, STORE manipulate the top of stack. Compact encoding (no register operands in the instruction), trivially simple code generation from an AST (just post-order traverse), and easy verification. Used by JVM, .NET CIL, WebAssembly, CPython, Forth.

// x = 42 + y  (stack-based)
PUSH 42       // stack: [42]
LOAD y        // stack: [42, y]
ADD           // stack: [42+y]
STORE x       // stack: []

Register Machines

Operands are explicit register names. Instructions like ADD r0, r1, r2 specify source and destination. Fewer instructions (no push/pop overhead), maps more naturally to hardware. But larger instruction encoding and more complex code generation. Used by Lua 5.0+, Dalvik/ART (Android), LuaJIT, Dis (Limbo).

// x = 42 + y  (register-based)
LOADK  r0, 42   // r0 = 42
LOAD   r1, y    // r1 = y
ADD    r2, r0, r1 // r2 = r0+r1
STORE  x,  r2   // x = r2

Instruction Selection

Mapping IR operations to machine instructions. A single IR operation might map to one instruction, multiple instructions, or be folded into a complex addressing mode. Tree-pattern matching (BURG/iburg) or DAG-based selection (LLVM's SelectionDAG / GlobalISel) are the standard approaches. The challenge: modern ISAs have thousands of instructions with overlapping capabilities — x86-64 has ~1500 distinct instruction forms.

Register Allocation

The IR assumes infinite virtual registers; the hardware has a small fixed set (x86-64: 16 GPRs, ARM64: 31). Graph coloring allocators (Chaitin-Briggs) model this as coloring an interference graph — two live ranges that overlap can't share a register. When coloring fails, spill to the stack. Linear scan allocators (used in JITs) trade allocation quality for speed — one pass over the live ranges, O(n log n).

Instruction Scheduling

Reorder instructions to hide latencies and fill pipeline slots. A multiply on modern x86 has 3-cycle latency — the scheduler inserts independent instructions in those cycles. List scheduling builds a DAG of dependencies and greedily picks ready instructions. This interacts with register allocation: more reordering increases register pressure. LLVM schedules both before and after regalloc.

Peephole Optimization

A final pass over the generated assembly, replacing instruction patterns with cheaper equivalents. Example: mov rax, 0 → xor eax, eax (shorter encoding, breaks dependency chain). imul rax, rax, 2 → shl rax, 1. Modern peephole optimizers are often auto-generated from declarative pattern-match rules.

MLIR & Multi-Level IRs

Developed at Google and now part of the LLVM project, MLIR provides a framework for defining custom IR dialects at any abstraction level — from TensorFlow operations to GPU kernel launches to LLVM IR. Dialects can be mixed in the same module and progressively lowered. This is reshaping compiler design for domain-specific languages, especially in ML hardware targeting.

WebAssembly Beyond the Web

Wasm was designed as a browser compilation target, but its sandboxed execution model, fast startup, and near-native speed make it compelling for edge computing, plugin systems, and serverless. WASI (WebAssembly System Interface) provides POSIX-like capabilities. The component model adds cross-language interop via interface types — a universal ABI for the future.

Compiler as a Service

Modern compilers aren't just batch translators — they're interactive services. The Language Server Protocol (LSP) requires the compiler to provide completions, diagnostics, refactoring, and go-to-definition on every keystroke. This demands incremental compilation (don't recompute what hasn't changed), lazy evaluation (don't analyze files the user isn't looking at), and error recovery (produce useful output from broken code).

Compile-Time Execution

The boundary between compile-time and runtime is dissolving. Zig's comptime runs arbitrary code during compilation. Rust's const fn evaluates functions at compile time. C++'s constexpr/consteval has become Turing-complete. This requires the compiler to include an interpreter for its own IR — Rust's miri and LLVM's ConstantFolding serve this role.