# Compilation
## How Languages Work — The Codex Coding
**URL:** https://thecodex.expert/coding/how-languages-work/compilation/
**Type:** concept
**Confidence:** high
**Last verified:** 2026-06-01
**Sources:** 5

---

## CANONICAL DEFINITION

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.

---

## CONCEPT RELATIONSHIP MAP

**Requires first:** How Computers Work · Binary and Number Systems

**Enables:** C · C++ · Rust · Go · Swift · Type Systems · Interpretation (contrast)

**Commonly confused with:** Interpretation (not a binary choice — Java, Python both compile and interpret)

---

## CURIOUS LEVEL

A compiler is a translator: it reads code written for human eyes and produces code a processor can execute — and does this before the program runs.

### The Pipeline Stages

1. **Lexing** — source text → token stream (keywords, identifiers, literals, operators)
2. **Parsing** — token stream → Abstract Syntax Tree (enforces grammar; catches syntax errors)
3. **Semantic analysis** — AST → annotated AST with types; catches type errors, undefined variables
4. **Optimisation** — constant folding, dead code elimination, loop-invariant code motion, inlining
5. **Code generation** — produces machine code or IR for a target architecture
6. **Linking** — combines object files, resolves external references → executable

Compiled languages: C, C++, Rust, Go, Swift. Java compiles to JVM bytecode (intermediate). TypeScript compiles to JavaScript.

Key property: translation happens BEFORE the program runs. The compiler is not present at runtime.

---

## EXPLORING LEVEL

### Front/Middle/Back End (LLVM model)

Front end (language-specific): lexing → parsing → semantic analysis → IR generation
Middle end (language-agnostic): IR optimisation passes
Back end (architecture-specific): instruction selection → register allocation → code generation

LLVM IR is typed, SSA-form (Static Single Assignment — each variable assigned exactly once). Enables many optimisations. Used by Clang (C/C++), rustc (Rust), Swift compiler.

### Abstract Syntax Tree

Token stream → AST via context-free grammar. For `result = x + 42`:
```
AssignStatement
├── left:  Identifier("result")
└── right: BinaryExpr(op="+")
           ├── left:  Identifier("x")
           └── right: IntegerLiteral(42)
```

### Optimisation Examples

- Constant folding: `2 + 3` → `5` at compile time
- Dead code elimination: remove unreachable branches
- Loop-invariant code motion: move constant computation out of loops
- Inlining: replace function call with function body
- Vectorisation: scalar loops → SIMD instructions

GCC/Clang levels: -O0 (none), -O1, -O2, -O3 (aggressive), -Os (size).

### Code Generation and Linking

Compiler produces object files (.o / .obj) with unresolved references. Linker combines and resolves → executable. Static linking bundles libraries. Dynamic linking resolves .so/.dll at load time.

### COMMONLY CONFUSED

- Compilation and interpretation are not binary opposites. Java compiles to bytecode (compilation), then the JVM interprets/JIT-compiles it (interpretation/compilation at runtime).
- A compiler is not a linker. Compiler: source → object code. Linker: object files → executable.
- Compiled ≠ always faster. JIT-compiled languages (V8, HotSpot) can approach AOT performance.

---

## DEEP DIVE LEVEL

### Formal Language Theory

Lexical analysis uses regular grammars (Type 3, Chomsky hierarchy; recognised by finite automata). Syntax uses context-free grammars (Type 2; pushdown automata). Semantic constraints (scoping) use context-sensitive analysis.

### LLVM IR Example

C: `int add(int a, int b) { return a + b; }`

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

### Register Allocation

Graph colouring problem: build interference graph (nodes=variables, edges=simultaneously live), colour with k colours (k=register count). NP-complete (Karp, 1972). Heuristics: Chaitin's algorithm (1982), linear scan (Poletto & Sarkar, 1999).

### Primary Sources

- Aho, Lam, Sethi & Ullman (2006). Compilers: Principles, Techniques, and Tools (Dragon Book). 2nd ed. Pearson.
- Lattner & Adve (2004). LLVM: A compilation framework. CGO 2004.
- Backus et al. (1957). The FORTRAN automatic coding system. WJCC.
- Chaitin et al. (1981). Register allocation via coloring. Computer Languages 6(1).
- LLVM Project. LLVM Language Reference Manual. llvm.org/docs/LangRef.html.

---

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*
*Last verified: June 2026 · Source confidence: high*