Compilers Guide: How Source Code Becomes Machine Code

Compilers Compilers 7 min read 1461 words Beginner ExcellentWiki Editorial Team

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 machine code or assembly. Understanding how compilers work is valuable for every programmer — it demystifies error messages, clarifies why some code patterns perform better than others, and equips you to design languages and tools. The classical compiler architecture divides the compilation process into four major phases: the frontend, the intermediate representation (IR), the optimizer, and the backend. This article provides an end-to-end walkthrough of that pipeline, referencing the canonical treatment in Aho, Lam, Sethi, and Ullman’s “Compilers: Principles, Techniques, and Tools” (the Dragon Book).

The Frontend: Analysis

The frontend is responsible for understanding the source program. It consists of three phases: lexical analysis, syntax analysis, and semantic analysis.

Lexical Analysis (Scanning)

The lexer reads the raw source code as a stream of characters and groups them into tokens — the smallest meaningful units of the language. Tokens include keywords (if, while, return), identifiers (variable_name, myFunction), literals (42, "hello"), operators (+, ->), and delimiters ({, ;).

The lexer also strips comments and whitespace and associates line and column numbers with each token for error reporting. Lexer generators like Lex and Flex take regular expression-based specifications and produce deterministic finite automata (DFAs) for efficient scanning.

Syntax Analysis (Parsing)

The parser takes the token stream from the lexer and builds a parse tree (concrete syntax tree) or abstract syntax tree (AST) according to the language’s grammar. The grammar is typically specified in Backus-Naur Form (BNF) or Extended BNF.

Parsing algorithms fall into two categories: top-down (recursive descent, LL) and bottom-up (LR, LALR). Most hand-written compilers use recursive descent because it is straightforward to implement and produces excellent error messages. Generated parsers (Yacc, Bison, ANTLR) typically use LALR(1) or LL(*) algorithms for better performance and maintainability.

Semantic Analysis

The semantic analyzer checks the program for semantic correctness — things that are syntactically valid but semantically meaningless. This includes:

Type checking — verifying that operations receive operands of the correct type
Scope resolution — ensuring variable references refer to declared identifiers in accessible scopes
Name binding — associating each use of a name with its definition
Const checking — detecting modifications to read-only variables

The semantic analyzer typically builds and maintains a symbol table — a data structure mapping names to their types, scopes, and other attributes. If the program passes semantic analysis, the compiler knows it is a valid program in the source language.

Intermediate Representation

After semantic analysis, the compiler lowers the AST to an intermediate representation (IR). The IR is a programming-language-agnostic representation that sits between the source and target languages. Its design is critical because both the optimizer and the backend consume it.

Common IR forms include:

Three-address code (TAC) — each instruction has at most three operands: a = b + c
Static Single Assignment (SSA) form — a TAC variant where each variable is assigned exactly once; φ functions merge values at control flow joins
Control Flow Graph (CFG) — a graph where nodes are basic blocks and edges represent control flow
LLVM IR — a typed, SSA-based IR used by the LLVM framework, with explicit memory operations (alloca, load, store)

The IR design must balance several concerns: it should be low-level enough to represent target-specific details, yet high-level enough to enable machine-independent optimizations.

The Optimizer

The optimizer applies transformations to the IR to improve the program’s runtime performance, code size, or energy consumption. Optimizations are organized into passes that run in a fixed order, with each pass cleaning up opportunities for subsequent passes.

Machine-Independent Optimizations

These optimizations do not depend on the target architecture:

Constant folding and propagation — evaluating constant expressions at compile time
Dead code elimination — removing unreachable or unused code
Common subexpression elimination — computing an expression once and reusing the result
Loop optimizations — unrolling, invariant code motion, vectorization
Function inlining — replacing function calls with the callee’s body
Global Value Numbering (GVN) — detecting redundant computations across basic blocks

Machine-Dependent Optimizations

These optimizations are specific to the target CPU:

Instruction selection — choosing the best machine instructions for IR operations
Register allocation — mapping virtual registers to physical registers
Instruction scheduling — reordering instructions to minimize pipeline stalls
Peephole optimization — replacing short instruction sequences with better equivalents

The Backend: Synthesis

The backend generates target machine code from the optimized IR. It consists of instruction selection, register allocation, instruction scheduling, and machine code emission.

Instruction Selection

The instruction selector maps IR operations to target machine instructions. For a RISC machine, an addition IR instruction maps to a single ADD instruction. For a CISC machine, a complex addressing mode might replace several IR operations with one instruction.

Register Allocation

Register allocation assigns the program’s virtual registers to physical CPU registers. The classic algorithm uses graph coloring: each virtual register is a node in an interference graph, and two nodes are connected if their live ranges overlap. The allocator colors the graph with K colors (where K is the number of physical registers) and spills excess values to memory.

Code Emission

The final phase emits binary machine code or assembly text. This involves encoding instructions according to the ISA specification, computing relocations for external symbols, and assembling the object file sections (.text, .data, .bss, etc.).

A Complete Example

Consider compiling int x = 3 + 4 * 5;:

Lexer produces tokens: int, x, =, 3, +, 4, *, 5, ;
Parser builds an AST: Declaration(Variable("x"), BinaryOp(+, 3, BinaryOp(*, 4, 5)))
Semantic analysis checks that int is declared, x is not redeclared, and all operands are integers
IR generation produces TAC: t1 = 4 * 5; t2 = 3 + t1; x = t2
Optimizer constant-folds: t1 = 20; t2 = 23; x = 23 then propagates: x = 23
Code generator selects instructions: MOV x, #23

The result is a single move instruction, far smaller than what the source code naively suggests.

FAQ

What is the difference between a compiler and an interpreter? A compiler translates the entire source program to machine code before execution. An interpreter executes the source program directly, typically one statement at a time. Interpreter vs Compiler explores the tradeoffs in depth.

Why do compilers have multiple phases? Separation of concerns. The frontend handles source language specifics, the optimizer works on a language-neutral IR, and the backend handles target architecture specifics. This makes the compiler retargetable — to support a new language, you only write a new frontend; to support a new CPU, only a new backend.

What is a “production compiler”? A production compiler is one used in real-world development, designed for correctness, performance, and usability. GCC, Clang/LLVM, MSVC, and rustc are production compilers. They contrast with “toy compilers” built for education or research.

How does a compiler ensure correctness? Through rigorous testing: conformance test suites, differential testing against other compilers, random program generation (Csmith), and formal verification (CompCert).

What is bootstrapping? Bootstrapping is compiling a compiler with itself. A C compiler written in C is compiled with an existing C compiler. The resulting binary can then compile its own source code, creating a self-hosting compiler. GCC, Clang, and rustc all bootstrap. This process validates that the compiler can correctly compile its own source.

Compilation vs. Interpretation in Practice

The line between compilation and interpretation is increasingly blurred. Python compiles source to bytecode (.pyc files), then interprets the bytecode. Java compiles source to JVM bytecode, which the JVM interprets initially and then JIT-compiles to native code. V8 compiles JavaScript to TurboFan IR and then to native code without an explicit bytecode step (Ignition uses bytecode as an intermediate).

What matters for practical performance is not whether a language is “compiled” or “interpreted” but how much optimization the execution engine performs at runtime and whether the hot code paths are compiled to native code. The modern approach is a continuum: parse → high-level IR → low-level IR → machine code, with execution happening at any stage depending on the runtime’s optimization budget.

How do compilers handle optimization levels? Optimization levels (-O0, -O1, -O2, -O3, -Os, -Oz) are shorthand for predefined pass pipelines. -O0 disables most optimizations for fast compilation. -O2 enables most machine-independent optimizations. -O3 enables all -O2 passes plus aggressive inlining and vectorization. -Os optimizes for code size by selecting smaller instruction sequences. Users can also enable individual passes with -f flags. For example, -funroll-loops enables loop unrolling independent of the optimization level.