Phases of a Compiler

You write int result = (a + 2) * b;. The CPU understands only binary. A compiler bridges that gap through six sequential phases — each with one specific job, producing one specific output, and passing it to the next.

Two helpers accompany every phase: the Symbol Table (a dictionary of every name in the program) and the Error Handler (which collects mistakes at each phase).

We will trace the same example line through every phase.

The lexer reads source code character by character and groups them into tokens — the smallest meaningful units of the language.

A token has two parts:

• Lexeme — the actual text from the source code (e.g. int, result, +)
• Token Type — the category it belongs to (e.g. KEYWORD, IDENTIFIER, ARITH_OP)

Whitespace and comments are discarded — they are not tokens and carry no meaning to later phases.

Token Type Reference

What Gets Discarded

Exam Example 1 — Simple Declaration

Exam Example 2 — Arithmetic Expression

Exam Example 3 — If Statement

Exam Example 4 — While Loop

Errors the Lexer Catches

The parser takes the token stream and checks whether the tokens are arranged in a valid order according to the language's grammar rules. If valid, it builds an Abstract Syntax Tree (AST) — a tree that captures the structure of the code without punctuation.

What is a Grammar Rule?

A grammar rule is a recipe that says: "this sequence of tokens counts as valid code."

Two symbols to know:

• → means "can be written as"
• | means "or"

For example, the rule for a variable declaration:

Read it as: "A valid statement is: a type, then a name, then =, then an expression, then ;."

Watch how our line matches it token by token:

Every slot is filled — the statement is valid.

Expression Rules and Operator Precedence

An expression can be simple (5) or complex ((a + 2) * b). Three rules handle all cases:

Why three separate rules? To encode operator precedence — the rule that * is computed before +.

Because * lives in term, which is inside expression, multiplication always binds tighter than addition. The tree reflects this: whichever operation is deeper in the tree runs first.

Example 1 — Simple Assignment: int x = 5;

The simplest case — just a type, a name, and a single integer.

Example 2 — Operator Precedence: a + 2 * b

No parentheses — the grammar rule forces * to sit deeper in the tree, so it is evaluated first.

The × node is lower in the tree → it is evaluated first → result is a + (2 * b).

Example 3 — Parentheses Override: (a + 2) * b

Adding parentheses flips the tree. Now + is deeper — so it runs first.

The + node is now lower → it runs first → result is (a + 2) * b.

Compare Example 2 and 3 side by side: the only change is parentheses, but the entire tree structure flips. The parentheses themselves never appear in the tree — their effect is already captured by which node sits deeper.

Full Declaration AST

Wrapping Example 3 in the full declaration int result = (a + 2) * b;:

The semicolon is gone. The type and name sit beside the value. The expression is now a sub-tree — structure replaces punctuation.

Errors the Parser Catches

Syntax checks structure. Semantics checks meaning. The semantic analyser walks the AST and verifies that the program actually makes sense.

"Colourless green ideas sleep furiously" is grammatically perfect but semantically nonsense. Similarly, int x = "hello"; is syntactically valid C but semantically wrong.

What It Checks

• Type compatibility — are operand types compatible? (int + int is fine; int + string is not)
• Declaration before use — is every variable declared before it is used?
• Scope rules — is this identifier visible in the current scope?
• Function calls — correct number and types of arguments?

All checks consult the Symbol Table, which maps every name to its type, scope, and memory location.

Our Example — Step by Step

Semantic Errors

The compiler does not jump straight from the AST to machine code. It first produces a simplified, machine-independent version of your program called Intermediate Representation (IR).

Think of it as a first draft. It is simpler than the AST and simpler to optimise. Once the draft is good, you translate it to the final target.

The key benefit: the same IR works for any CPU. Write the front-end once, then generate x86, ARM, or WebAssembly by swapping only the last step.

Three-Address Code

The most common IR format is Three-Address Code (TAC). The rule is simple:

Each instruction does exactly one operation and stores the result in a temporary variable.

If an expression needs multiple operations, you break it into steps. Temporaries t1, t2, … hold the intermediate results.

How the AST Maps to IR

The compiler walks the AST bottom-up — children before parents. Each operator node becomes one TAC instruction.

Our expression: (a + 2) * b

Full IR output:

Example 2 — Two sub-expressions: x = (a + b) * (a - b)

Both sides of the * are computed independently and stored in temporaries before the multiply happens.

Example 3 — If / Else

In TAC there are no nested blocks — conditionals flatten into labels and goto instructions:

Example 4 — Loop

Every loop becomes: initialise → label → check condition → body → increment → jump back:

The optimizer rewrites IR to make the program faster or smaller while guaranteeing the output stays identical. Think of it as a smart editor who simplifies your draft without changing the meaning.

This phase is technically optional, but a good optimizer can make code 5–10× faster in practice. Below are the five most important techniques.

Technique 1 — Constant Folding

What: If both operands are known constants, compute the result at compile time.

Technique 2 — Constant Propagation

What: If a variable is always the same constant value, replace every use of it with that constant directly. This often unlocks folding.

Propagation and folding work together: propagation substitutes the value, then folding evaluates the result.

Technique 3 — Dead Code Elimination

What: Remove code whose result is never used, or code that can never be reached.

Case A — unused variable:

Case B — unreachable branch:

Technique 4 — Common Subexpression Elimination (CSE)

What: If the same expression is computed more than once with the same inputs, compute it once and reuse the result.

Technique 5 — Loop Invariant Code Motion (LICM)

What: If a computation inside a loop produces the same result on every iteration (because it doesn't depend on the loop variable), move it outside.

If N = 1,000,000 — this removes 999,999 multiplications.

Our Example — All Techniques Applied

Starting IR from Phase 4:

Suppose a = 3 and b = 4 are known at compile time:

The code generator translates optimized IR into real CPU instructions. Abstract names like t1 and a are replaced with actual registers and memory addresses.

Three main jobs:

1. Instruction Selection — pick the right CPU instruction for each IR operation
2. Register Allocation — decide which variables live in fast registers vs. slow memory
3. Instruction Scheduling — reorder instructions to avoid CPU pipeline stalls

Registers vs. Memory

Registers are tiny, ultra-fast storage slots inside the CPU (e.g. R1, R2, R3). Memory is large but much slower. The allocator tries to keep every "live" variable in a register for as long as possible.

A variable is live between its first assignment and its last use. Two variables that are never live at the same time can share a register.

Example 1 — Arithmetic: result = (a + 2) * b

R1 is reused for both t1 and t2 because t1 is dead the moment t2 is computed.

Example 2 — If / Else

Key idea: the IR temporary t1 = score >= 60 disappears. The comparison result is held in the CPU's flags register, not in a general-purpose register. The conditional jump JGE reads those flags directly.

Example 3 — Loop

sum and n are loaded into registers before the loop so the CPU does not hit memory on every iteration. sum is stored back only once after the loop ends.

Example 4 — Function Call

A calling convention decides which registers carry arguments and which register holds the return value. Here we use: args in R1, R2, …; return value in R0.

Instruction Selection

For the same IR operation there can be several valid instructions. A good code generator picks the cheapest one:

All three produce the same result; Option C avoids the multiply unit entirely.

Register Spilling

A CPU has only 8–16 general-purpose registers. When more variables are live at the same time than there are registers, the allocator spills the least-needed variable to the stack:

Every spill/reload is a slow memory access, so minimising spills is a key goal of register allocation.

Trace the following program through all six phases of a compiler.

Phase 1 — Lexical Analysis

Phase 2 — Syntax Analysis (Abstract Syntax Tree)

Parentheses and semicolons do not appear in the tree — the structure itself encodes their meaning.

Phase 3 — Semantic Analysis

Phase 4 — IR Generation (Three-Address Code)

Phase 5 — Code Optimization

Phase 6 — Code Generation (Assembly)

Summary