The Compiler Pipeline

A compiler is a program that translates source code written in one language (the source language) into an equivalent program in another language (the target language), typically closer to or identical with machine code. The central design principle behind every serious compiler is phase separation: the overall translation is decomposed into a sequence of passes, each of which takes a well-defined input representation and produces a well-defined output representation. The pipeline is traditionally divided into a front end, a middle end, and a back end. The front end is concerned with understanding the source language: it reads raw characters, groups them into meaningful tokens (lexical analysis), organizes tokens into a hierarchical syntax tree according to the grammar of the language (syntax analysis, or parsing), and then checks that the program makes sense according to rules that a grammar alone cannot express, such as type consistency and variable scoping (semantic analysis). The middle end operates on an intermediate representation (IR), a language-agnostic and machine-agnostic form that captures the program's meaning in a shape convenient for analysis and transformation; here optimizations happen. The back end takes the (possibly optimized) IR and produces actual target code, handling machine-specific concerns like instruction selection, register allocation, and instruction scheduling. The reason this decomposition matters is separation of concerns combined with reusability. A front end for a language like C needs to be written only once, and it can be paired with many back ends (x86, ARM, RISC-V, WebAssembly) as long as they all consume the same IR. Conversely, a back end for a target architecture can be reused across many source languages. This "N front ends × M back ends" architecture, connected through a common IR, is precisely why a single toolchain like LLVM can support C, C++, Rust, Swift, and Julia while targeting dozens of hardware platforms, rather than requiring N × M independent translators.

The pipeline proceeds as a strict sequence of transformations on progressively more structured representations of the program. Each phase's output feeds the next phase's input, and (in most designs) a symbol table is threaded through several phases to record information about identifiers — their types, scopes, and storage.

1. Lexical analysis (scanning). The source text, a raw sequence of characters, is grouped into tokens — the smallest meaningful units such as keywords, identifiers, literals, operators, and punctuation. Whitespace and comments are typically discarded here. This phase is implemented efficiently using finite automata derived from regular expressions, giving linear-time scanning.

2. Syntax analysis (parsing). The token stream is checked against the context-free grammar of the language and organized into a tree structure, usually an abstract syntax tree (AST), that reflects the hierarchical, nested structure of the program (expressions inside statements inside functions, and so on). A syntax error — a token sequence that cannot be produced by the grammar — is detected here.

3. Semantic analysis. The AST is walked to enforce rules the grammar cannot express: that variables are declared before use, that types are used consistently (type checking), that function calls match function signatures, and so on. This phase builds and consults the symbol table, and it may annotate the AST with type information, producing what is sometimes called an annotated or decorated AST.

4. Intermediate code generation. The annotated AST is translated into an intermediate representation — a lower-level, often linear, form such as three-address code, a control-flow graph, or static single assignment (SSA) form. The IR is deliberately independent of both the original source syntax and the eventual target machine.

5. Optimization (middle end). The IR is analyzed and rewritten to improve performance or size without changing observable behavior: eliminating dead code, propagating constants, hoisting loop-invariant computations, eliminating common subexpressions, and inlining function calls, among many others. This phase may iterate, applying multiple passes until a fixed point or a resource budget is reached.

6. Code generation (back end). The optimized IR is translated into target code: machine instructions, bytecode, or assembly. This step involves instruction selection (choosing target instructions to implement IR operations), register allocation (mapping an unbounded set of IR-level variables to a fixed set of physical registers), and instruction scheduling (ordering instructions to exploit pipeline parallelism and hide latency).

7. Target-specific optimization and assembly/linking. A final pass may perform peephole optimizations directly on the generated machine code, after which an assembler and linker produce an executable binary, resolving symbolic addresses into concrete memory locations. ``` function COMPILE(sourceText): tokens ← LEX(sourceText) // Phase 1: characters → tokens ast ← PARSE(tokens) // Phase 2: tokens → syntax tree if PARSE_ERROR(ast): report syntax error; return FAILURE symbolTable ← new SymbolTable() annotatedAst ← CHECK_SEMANTICS(ast, symbolTable) // Phase 3: scope/type checking if SEMANTIC_ERROR(annotatedAst): report semantic error; return FAILURE ir ← GENERATE_IR(annotatedAst, symbolTable) // Phase 4 ir ← OPTIMIZE(ir) // Phase 5 (may iterate to fixpoint) targetCode ← GENERATE_CODE(ir) // Phase 6: instruction selection, // register allocation, scheduling targetCode ← PEEPHOLE_OPTIMIZE(targetCode) // Phase 7a binary ← ASSEMBLE_AND_LINK(targetCode) // Phase 7b return binary ``` The diagram below shows this pipeline as a chain of representations, with the symbol table threaded through the phases that need it, and the two "error exit" points where translation can halt early.

Time complexity. For a well-designed compiler, each front-end phase runs in time linear in the size of its input, and the whole front end runs in O(n) time where n is the length of the source text, because:

• Lexical analysis uses a deterministic finite automaton (DFA) to scan characters, doing O(1) work per character transition, giving O(n) total.
• Parsing with standard deterministic techniques (LL(1), LALR(1), operator-precedence, or recursive descent for suitable grammars) processes each token in amortized O(1) time using a stack-based or table-driven algorithm, giving O(n) total for n tokens.
• Semantic analysis typically walks the AST once (or a small constant number of times), doing O(1) amortized work per node with symbol-table operations averaging O(1) via hashing, giving O(n) total for an AST of size O(n).

The middle end is where complexity honesty matters most: many optimization analyses (data-flow analysis, alias analysis, register allocation via graph coloring) are not linear. Classical data-flow analyses converge in a number of passes bounded by the depth of the control-flow lattice, giving polynomial but super-linear worst-case time in general; register allocation via graph coloring is NP-hard in general (approximated in practice with heuristics like Chaitin-Briggs coloring). A compiler's overall running time is therefore dominated in practice by the front end for small/simple programs, and by optimization and register allocation for large, heavily optimized builds.

Space complexity is O(n) for holding the token stream, AST, symbol table, and IR simultaneously, since each is a data structure whose size is (at worst) proportional to the source program's size — though optimizations like SSA form or extensive inlining can increase IR size by a constant or logarithmic factor relative to source size, and aggressive inlining can in pathological cases cause superlinear code growth, which real compilers bound with heuristics and size budgets.

Correctness argument. The core correctness property a compiler must satisfy is semantic preservation: the target program, when executed, must produce the same observable behavior as the source program under its language's defined semantics (this includes an explicit, spec-defined notion of what "undefined behavior" permits). The phase-by-phase structure supports a proof strategy by induction over the pipeline: 1. Lexing is correct if the token stream is exactly the one implied by the language's lexical grammar — provable because each token type corresponds to a regular language, and DFA equivalence to regular expressions is a classical, well-established result. 2. Parsing is correct if the AST it builds is exactly a parse consistent with the language's context-free grammar for every string the grammar accepts, and it rejects every string the grammar does not accept — this is the soundness and completeness of the specific parsing algorithm (e.g., LALR(1) parser correctness relative to its grammar), established once per parsing method. 3. Semantic analysis is correct if it accepts exactly the ASTs that satisfy the source language's static semantics (typing rules, scoping rules) — this is typically established by proving the implemented type-checking algorithm is sound (and ideally complete) with respect to the language's formal type system, often expressed as inference rules. 4. IR generation is correct if it is a meaning-preserving translation: for every annotated AST node, the generated IR computes the same value/effect as the source construct under the language's operational semantics. This is proved by structural induction on the AST: assume each subtree translates correctly, show the composed IR for the parent construct preserves meaning. 5. Each optimization pass is correct if it is proven to preserve the program's observable semantics — for example, dead-code elimination is correct if the eliminated code provably has no observable effect (proved using a data-flow analysis such as liveness, whose correctness itself rests on the standard fixed-point theory of data-flow frameworks over lattices). 6. Code generation is correct if the emitted machine instructions implement the IR's semantics under the target machine's instruction-level semantics — typically shown via a simulation relation between IR execution steps and generated machine execution steps. Because each phase's correctness is a local claim about a well-defined transformation, the end-to-end correctness of the whole compiler follows by chaining these local correctness proofs — this is precisely why splitting the pipeline is not just an engineering convenience but a proof-engineering necessity: verifying one monolithic character-stream-to-machine-code function directly would be intractable, while verifying (and testing) each stage in isolation is tractable, and this is the foundation of verified-compiler projects such as CompCert.

Tradeoffs. Splitting into many phases costs some performance overhead (materializing intermediate structures like token arrays, ASTs, and IR takes memory and time that a fused, single-pass translator might avoid) and can slow down compile time itself. Production compilers mitigate this with techniques like combining lexing and parsing into a single pass with lazy token production, or using compact IR representations. The tradeoff is compile-time engineering cost versus correctness and retargetability — for small tools like a one-off scripting-language interpreter, the phase separation may be collapsed, but for any compiler intended to be robust, maintained, and reused, the layered pipeline is close to universal.

Consider compiling the tiny statement: ``` x = a + b * 2; ``` assuming `a` and `b` are previously declared `int` variables, and we are targeting a simple three-address-code machine.

Trace the symbol table's role: at semantic analysis time, when the analyzer visits `ID(a)`, it looks up `a` in the symbol table, finds it declared as `int`, and annotates that AST node with type `int`; the same happens for `b` and `x`. If `b` had never been declared, the lookup would fail and semantic analysis would report an undeclared variable error — a class of error a parser alone cannot detect, because "`b` is used but never declared" is not a property expressible in the context-free grammar; it requires tracking declarations across the whole program, which is exactly what the symbol table and semantic-analysis phase exist to do. Now suppose instead the source had a mismatched type, say `x = a + "hello";` where `a` is `int` and `"hello"` is a string literal. Lexing succeeds (it happily tokenizes a string literal), and parsing succeeds (the grammar for `expr + expr` has no notion of operand types), but semantic analysis fails: type checking the `Add` node finds an `int` and a `string` operand with no valid `+` rule, and the compiler halts with a type error before ever reaching IR generation — illustrating exactly why phase separation matters: syntactic well-formedness and semantic well-formedness are genuinely different questions, checked by different phases with different theoretical tools.

Every production compiler toolchain — GCC, LLVM/Clang, the Java and .NET JIT compilers, Go's compiler, Rust's `rustc` — is organized around this same front-end/middle-end/back-end pipeline, even when implementation details differ. Web browsers' JavaScript engines (V8, SpiderMonkey) run a compressed version of this pipeline at runtime to just-in-time compile hot code paths. Database systems parse and semantically validate SQL queries using lexers and parsers before generating an execution plan, which is itself an optimized intermediate representation analogous to compiler IR. Regular-expression engines, configuration-file parsers, and domain-specific languages embedded in build tools all reuse the lexer/parser/semantic-checker structure at a smaller scale. Understanding this pipeline is foundational before studying Lexical Analysis and Tokens in depth, before formalizing grammars with Context-Free Grammars for Parsing, and before exploring how Intermediate Representations enable the retargetable, optimizing middle ends that make modern compilers both correct and fast.

Ask the tutor: How does the parser actually decide, token by token, which grammar rule to apply — and what happens when a grammar is ambiguous?