Inside a Compiler: From Source Text to Machine Code

Text in, machine code out, four stages between

A compiler's job is to prove, mechanically, that a piece of source text has a precise meaning, and then produce a sequence of instructions with that exact meaning. Despite decades of added sophistication, almost every compiler still factors that job into the same four stages: turn characters into tokens, turn tokens into a tree, turn the tree into simple linear instructions, and then improve those instructions without changing what they mean.

Lexing: characters to tokens

The lexer (or scanner) reads raw characters and groups them into tokens — the smallest meaningful units: numbers, identifiers, operators, keywords, punctuation. Whitespace and comments are usually discarded here. Internally a lexer is almost always a finite-state machine equivalent to a big regular expression: it can recognise 42.5 as a single NUMBER token in one pass without ever needing to look further ahead than the next character, because number syntax is regular.

input:   "12 + 3 * x"
tokens:  NUM(12)  PLUS  NUM(3)  STAR  IDENT(x)

Parsing: tokens to a tree

The parser takes that flat token stream and imposes structure: an Abstract Syntax Tree (AST) that captures precedence and associativity, the two things a flat list of tokens cannot express. For arithmetic, a widely used technique is recursive-descent parsing with precedence climbing (also called a Pratt parser): each operator is assigned a binding power, and the parser recurses into subexpressions only as long as the next operator binds at least as tightly as the current one.

12 + 3 * x   parses as   (+ 12 (* 3 x))     not   (* (+ 12 3) x)

because * has higher binding power than +, so the parser
descends into "3 * x" before returning to finish the addition

Ambiguous grammars — famously the dangling else problem, where if (a) if (b) s1; else s2; could attach the else to either if — are resolved by a fixed convention (attach to the nearest unmatched if) baked directly into the parsing rule, rather than left to chance.

Codegen: tree to three-address code

Once the AST is built, code generation walks it and emits simple, linear instructions, typically in three-address code form: every instruction has at most one operator and writes to at most one temporary.

AST:  (+ 12 (* 3 x))

three-address code:
  t1 = 3 * x
  t2 = 12 + t1

Each three-address instruction maps almost directly onto a handful of real machine instructions (load, multiply, add, store), which is why this intermediate form is the standard hand-off point between a compiler's front end (language-specific) and back end (target-specific): retargeting to a new CPU means rewriting only the small final step from three-address code to that CPU's instructions.

Optimisation: constant folding and beyond

Between codegen and final emission sit optimisation passes that improve the code without changing its meaning. The simplest and most universal is constant folding: if an instruction's operands are both known at compile time, evaluate it once during compilation instead of on every run.

before:                  after constant folding:
  t1 = 3 * 4               t1 = 12
  t2 = t1 + x               t2 = 12 + x   (further folds if x is also constant)

Real compilers chain dozens of such passes — dead-code elimination, common-subexpression elimination, strength reduction, inlining, register allocation — each one a small, meaning-preserving rewrite, run repeatedly until nothing more changes. The interactive demo above implements only the essentials — lexer, recursive-descent parser, three-address codegen and one constant-folding pass — but every full-scale compiler, from a JavaScript engine's JIT to GCC, is built from the same four stages, just with far more of them chained together.

Frequently asked questions

Try it live

Everything above runs in your browser — open Compiler Pipeline and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.