Compilation is the process by which a compiler translates source code written in a high-level programming language into a lower-level representation — typically machine code or an intermediate representation — by performing lexical analysis, syntactic parsing, semantic analysis, optimisation, and code generation as a series of sequential transformation passes over the source text.
A compiler is a translator: it reads code you wrote for human eyes and produces code a processor can execute — and it does this before your program runs, not while it runs.
The translation problem
When you write x = 5 + 3 in C or Rust, the processor has no idea what that means. Processors speak machine code — binary instructions like "load the value 5 into register R1, load 3 into register R2, add them, store the result." A compiler bridges that gap.
The job of a compiler sounds simple: take text in one language, produce output in another. But the source text has to be understood completely — every variable, every function call, every loop — before a single byte of machine code can be produced. That understanding happens in stages, each building on the last.
Stage 1 — Lexing: turning text into words
The first thing a compiler does is break the source text into tokens — the smallest meaningful units. The string int x = 42; is not four characters to a compiler — it is four tokens: a keyword (int), an identifier (x), an assignment operator (=), and a number literal (42), followed by a semicolon.
This stage is called lexical analysis (or lexing, or tokenisation). Whitespace and comments are stripped. What remains is a clean sequence of tokens. Think of it as the compiler learning to read individual words before it can understand sentences.
Stage 2 — Parsing: understanding structure
Tokens become a tree. The expression 2 + 3 * 4 is not just three numbers and two operators in a row — it has structure: the multiplication happens before the addition, so the tree has * as a child of +. This tree is called an Abstract Syntax Tree (AST).
Parsing enforces the grammar of the language. If you write int = x 42; instead of int x = 42;, the parser rejects it — the token sequence doesn't match any valid grammar rule.
Parsing is like diagramming a sentence. "The cat sat on the mat" has a subject (cat), a verb (sat), and a prepositional phrase (on the mat). The compiler does the same for code: it identifies what is a declaration, what is an expression, what is a conditional, and how they nest inside each other. The resulting tree represents the grammar structure of your program.
Stage 3 — Semantic analysis: checking meaning
The AST might be grammatically valid but still wrong. Adding a number to a function, using a variable before declaring it, calling a function with the wrong number of arguments — these are grammatically legal in terms of token sequences, but meaningless. Semantic analysis catches them.
This is where type checking happens in statically typed languages. The compiler walks the AST, assigns types to every expression, and verifies that operations are applied to compatible types. The error "cannot add int and string" comes from this stage.
Stage 4 — Optimisation: making it faster
Once the compiler understands what the program does, it looks for ways to produce the same result more efficiently. It might replace x * 2 with x << 1 (a left-bit-shift, which is faster). It might eliminate code that can never execute. It might move a constant calculation out of a loop so it's done once instead of thousands of times.
Optimisations preserve the meaning of the program — the output must be identical to what the original code would produce — while reducing execution time or memory use.
Stage 5 — Code generation: producing machine code
The final stage translates the optimised representation into actual machine instructions for a specific processor. A program compiled for an Intel x86-64 processor produces different binary output than the same program compiled for an ARM processor, even though the source code is identical. This is why compiled programs are platform-specific.
What languages use compilation
C, C++, Rust, Go, and Swift compile directly to machine code. The resulting program runs without any other software — just the operating system. Java and Kotlin compile to bytecode for the Java Virtual Machine (JVM), which is an intermediate step: bytecode is not machine code but is lower-level than source code, and the JVM executes it at runtime (often with further just-in-time compilation to machine code). TypeScript compiles to JavaScript, which is then interpreted or JIT-compiled in the browser.
The key characteristic of compilation is that the translation happens before the program runs. You run the compiler once, producing an executable file. That file is what you distribute and run — the compiler is no longer involved.
The compiler pipeline in detail
The standard compilation pipeline described in Aho, Lam, Sethi, and Ullman's Compilers: Principles, Techniques, and Tools (the "Dragon Book") consists of a front end, a middle end, and a back end:
- Front end: lexical analysis → syntactic analysis → semantic analysis → IR generation. Language-specific.
- Middle end: IR optimisation passes. Language-agnostic; operates on the intermediate representation.
- Back end: instruction selection → register allocation → code generation. Architecture-specific.
This separation allows compilers like LLVM to support many source languages (via separate front ends) and many target architectures (via separate back ends), sharing the middle-end optimisation work. Clang is LLVM's C/C++ front end. Rust's compiler (rustc) uses LLVM as its back end.
Lexical analysis in detail
The lexer (scanner) reads source characters and produces a token stream. Tokens are described by regular expressions — each token type (identifier, integer literal, string literal, keyword, operator) is matched by a pattern. The lexer is typically implemented as a finite automaton derived from the regular expression patterns.
Consider: result = x + 42;
IDENTIFIER "result"
ASSIGN "="
IDENTIFIER "x"
PLUS "+"
INTEGER "42"
SEMICOLON ";"Syntactic analysis and the AST
The parser takes the token stream and builds an Abstract Syntax Tree according to the language's context-free grammar — typically specified in BNF or EBNF notation. The AST abstracts away syntactic details (parentheses, semicolons) and retains only the structural meaning.
For result = x + 42, the AST looks like:
AssignStatement
├── left: Identifier("result")
└── right: BinaryExpr(op="+")
├── left: Identifier("x")
└── right: IntegerLiteral(42)Common parsing algorithms: recursive descent (handwritten, top-down; used in GCC, Clang, rustc), LR parsing (bottom-up, table-driven; used in many generated parsers), and PEG parsers (Parsing Expression Grammars; used in some modern languages). Most production compilers use hand-written recursive descent for its error-recovery flexibility.
Semantic analysis and the symbol table
The semantic analysis phase walks the AST and builds a symbol table — a mapping from identifier names to their types, scopes, and locations. It performs:
- Scope resolution: which declaration does each identifier reference?
- Type checking: are operations applied to compatible types?
- Control flow analysis: does every code path return a value? (for non-void functions)
- Definite assignment: is every variable used after being initialised?
In Rust, the borrow checker is a semantic analysis pass that enforces ownership rules — verifying that references are valid and no data races exist. This happens entirely at compile time, producing zero runtime overhead.
Optimisation passes
The middle end operates on an Intermediate Representation (IR) — a low-level but architecture-independent form. LLVM's IR is called LLVM IR; GCC's is called GIMPLE. Common optimisation passes include:
- Constant folding: evaluate
2 + 3at compile time →5 - Dead code elimination: remove code the program can never reach
- Loop-invariant code motion: move computations that don't change inside a loop to before the loop
- Inlining: replace a function call with the function body (eliminates call overhead)
- Common subexpression elimination: compute
a + bonce if used multiple times - Vectorisation: transform scalar loops into SIMD instructions
Optimisation levels in GCC and Clang: -O0 (none), -O1 (basic), -O2 (standard), -O3 (aggressive), -Os (optimise for size). Higher levels trade compilation time for runtime performance.
Code generation and linking
Instruction selection maps IR operations to processor instructions. Register allocation decides which values to keep in CPU registers (fast) versus spill to memory (slow) — this is an NP-hard problem in general; heuristics like graph colouring are used. Instruction scheduling reorders instructions to reduce pipeline stalls on superscalar processors.
The compiler produces object files (.o on Linux, .obj on Windows) — machine code with unresolved external references. The linker combines object files and resolves references to produce an executable. Static linking bundles library code into the executable. Dynamic linking leaves references to shared libraries (.so / .dll) to be resolved at load time.
gcc hello.c -o hello invokes both automatically, which is why the distinction is often invisible to beginners.Formal language theory foundations
Compiler theory is grounded in formal language theory. A programming language's syntax is formally described by a context-free grammar (CFG) — a set of production rules of the form A → α, where A is a non-terminal symbol and α is a string of terminal and non-terminal symbols. The language defined by a CFG is the set of all strings derivable from the start symbol.
The Chomsky hierarchy (Noam Chomsky, 1956) classifies formal grammars by generative power: regular grammars (Type 3, recognisable by finite automata — sufficient for lexical analysis), context-free grammars (Type 2, recognisable by pushdown automata — sufficient for syntax), context-sensitive grammars (Type 1), and unrestricted grammars (Type 0, Turing-complete). Programming language syntax is context-free; some semantic constraints (e.g. variable scoping) require context-sensitive analysis handled by the semantic pass, not the parser.
LLVM IR: a concrete intermediate representation
LLVM IR is a typed, SSA-form (Static Single Assignment) intermediate representation. In SSA form, each variable is assigned exactly once — allowing many optimisations to work by simple inspection of definition-use chains without complex dataflow analysis. The following C code:
int add(int a, int b) {
return a + b;
}Compiles to LLVM IR approximately as:
define i32 @add(i32 %a, i32 %b) {
entry:
%result = add i32 %a, %b
ret i32 %result
}LLVM IR is architecture-independent. The same IR can be compiled to x86-64, ARM, WebAssembly, or any other target that has an LLVM back end.
Register allocation: graph colouring
Register allocation assigns program variables to a finite set of processor registers. The classical approach models this as a graph colouring problem: build an interference graph where nodes are variables and edges connect variables that are simultaneously live (in use); a valid register assignment is a graph colouring using k colours where k is the number of available registers. Graph colouring is NP-complete in general (Karp, 1972), so compilers use heuristics — Chaitin's algorithm (1982) is the classical approach; linear scan allocation (Poletto and Sarkar, 1999) is widely used in JIT compilers for speed.
The authoritative reference for compiler construction is: Aho, A. V., Lam, M. S., Sethi, R. & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. Known as the "Dragon Book." The LLVM project's documentation at llvm.org/docs/ is the primary reference for LLVM IR and the LLVM compilation framework.
Key papers
- Backus, J. et al. (1957). "The FORTRAN automatic coding system." Proceedings of the Western Joint Computer Conference. — The first optimising compiler; demonstrated that machine-code performance was achievable from high-level source.
- Chaitin, G. J. et al. (1981). "Register allocation via coloring." Computer Languages, 6(1), 47–57.
- Poletto, M. & Sarkar, V. (1999). "Linear scan register allocation." ACM TOPLAS, 21(5).
- Lattner, C. & Adve, V. (2004). "LLVM: A compilation framework for lifelong program analysis & transformation." CGO 2004.