Compiler Phases: Working of Each Phase in Detail (With an End-to-End Example)

A typical compiler converts a source program into machine-executable code through a pipeline of phases: lexical analysis , syntax analysis , semantic analysis , intermediate code generation , optimization , and code generation.

A helpful way to understand the pipeline is to walk the same program through each phase, observing what data structures are built (tokens, AST, symbol tables, IR, etc.) and what transformations occur. The example below uses a small expression language fragment (like many textbooks) so the changes are visible without getting lost in full language features like control-flow or functions.

Example input (source language):

1int a = 3;
2int b = 4;
3int c = a * (b + 5) - 2;

Below, each phase is described in detail, followed by what happens to the running example. When possible, I’ll show representative outputs (tokens, AST shapes, symbol table entries, IR instructions, and final code sketch).

Phase 1 — Lexical Analysis (Scanner)

Goal: Convert a character stream into a token stream.

Token , lexeme , regular expression , DFA.

How it works

1. The lexer reads input left-to-right.
2. It classifies substrings into tokens using patterns (often implemented with DFA tables derived from regular expressions).
3. It typically:
   • Skips whitespace and comments.
   • Recognizes multi-character operators (==, <=, *, etc.).
   • Distinguishes keywords from identifiers (e.g., int is a keyword, a is an identifier).
   • Produces numeric literals (e.g., 3, 4, 5, 2).

Representative tokens for the example (simplified):

1INT  a  ASSIGN  NUM(3)  SEMI
2INT  b  ASSIGN  NUM(4)  SEMI
3INT  c  ASSIGN
4IDENT(a) MUL LPAREN
5IDENT(b) PLUS NUM(5) RPAREN
6MINUS NUM(2)  SEMI

Typical outputs/data

• A sequence of tokens: $\text{Token}_1, \text{Token}_2, \dots$
• Optional token attributes: identifier names, numeric values, source locations for error reporting.

Common failure modes

• Illegal characters (e.g., $ if not allowed).
• Malformed numbers (e.g., 12..3).
• Unterminated comments or strings (if supported).

[CalloutBlock]

Phase 2 — Syntax Analysis (Parser)

Goal: Check the grammar structure and build a hierarchical representation (parse tree / AST).

Context-free grammar (CFG) , parse tree , AST , shift-reduce.

How it works

1. The parser consumes the token stream.
2. Using a grammar (CFG), it decides whether the token sequence forms valid constructs.
3. It builds a structured representation:
   • Parse tree (faithful to grammar)
   • or AST (more semantic, fewer punctuation nodes)

For many expression languages, the parser organizes the expression by precedence and associativity:

• * binds tighter than + / -
• parentheses override precedence.

Representative AST idea for the expression The right-hand side of c is:

1a * (b + 5) - 2

AST shape (conceptual):

• Root: -
  • Left: *
    • Left: a
    • Right: +
      • Left: b
      • Right: 5
  • Right: 2

Typical outputs/data

• An AST for the whole program (or one per function/block)
• Error messages when grammar constraints are violated (missing semicolons, mismatched parentheses, etc.)

Phase 3 — Semantic Analysis

Goal: Ensure the program is meaningful beyond syntax.

Symbol table , scope , type checking , lvalue.

How it works

1. Build/populate the symbol table.
2. Resolve identifiers (a, b, c) to declarations.
3. Perform checks:
   • Variables declared before use.
   • Type compatibility for operations (+, *, -).
   • Assignment correctness (RHS type matches LHS type, or implicit conversions allowed).
4. Optionally annotate AST nodes with types (e.g., int).

Symbol table entries (conceptual) After int a = 3;

• a : int (assigned an address or intermediate storage location)

After int b = 4;

• b : int

After int c = ...;

• c : int

Then for the expression:

• a, b are int
• b + 5 produces int
• a * (b + 5) produces int
• ... - 2 produces int
• Therefore assignment to c is type-correct.

What semantic analysis “adds”

• Attributes like:
  • node.type = int
  • node.symbolRef = <symbol table entry>
  • resolved scopes/links

Phase 4 — Intermediate Code Generation (IR Generation)

Goal: Translate the AST into an intermediate representation that’s easier to optimize and analyze.

Intermediate representation (IR) , three-address code , temporary variable (temp) , basic block.

How it works

1. Walk the AST in an evaluation order.
2. Emit IR instructions for each operation, using temporaries for subexpressions.

Three-address IR sketch Let temps be t1, t2, t3, t4.

Expression: a * (b + 5) - 2

1. Compute (b + 5):
   • t1 = b + 5
2. Compute a * t1:
   • t2 = a * t1
3. Compute t2 - 2:
   • t3 = t2 - 2
4. Assign to c:
   • c = t3

Also, the declarations/assignments:

• a = 3
• b = 4
• c = t3

A combined IR listing (simplified):

1a = 3
2b = 4
3t1 = b + 5
4t2 = a * t1
5t3 = t2 - 2
6c = t3

Intermediate products

• A list of IR instructions
• Control-flow graph (CFG) if the language has branches/loops
• For straight-line code, it’s essentially one basic block.

Phase 5 — Optimization

Goal: Improve performance (time/space) or reduce code size while preserving semantics.

constant folding , common subexpression elimination , dead code elimination , strength reduction.

What can be optimized in the example Because b is assigned 4, t1 = b + 5 can be partially constant-folded:

• t1 = 4 + 5 = 9 Then:
• t2 = a * t1, with a = 3 → t2 = 3 * 9 = 27 Then:
• t3 = t2 - 2 = 27 - 2 = 25 Finally:
• c = 25

So the optimized IR may collapse to:

1a = 3
2b = 4
3c = 25

Mermaid view of dataflow optimization

Phase 6 — Code Generation

Goal: Convert optimized IR into target-specific assembly/machine code.

calling convention , instruction selection , register allocation , prologue/epilogue.

How it works (conceptually)

1. Instruction selection: Map IR operations to target ISA operations.
2. Register allocation: Decide which temps live in registers and which spill to stack.
3. Addressing/storage layout: Determine where variables a, b, c live (registers/stack/memory).
4. Emit instructions: Produce final assembly.

Sketch for a simple target (illustrative) Since constant folding already simplified to c = 25, code generation is trivial:

1; assume integer vars stored in registers or stack slots
2mov a, 3
3mov b, 4
4mov c, 25

If optimizations were not applied, you’d see multiply/add/sub instructions and temps, e.g., compute t1, t2, t3 and then store to c.

Full end-to-end walk-through (compact view)

Source

1int a = 3; int b = 4; int c = a * (b + 5) - 2;

1. Lexical analysis → tokens (int, a, =, 3, *, (, b, +, 5, ), -, 2, ;)
2. Syntax analysis → AST with operator hierarchy: - ( * a ( + b 5 ) ) 2
3. Semantic analysis
   • Build symbol table: a:int, b:int, c:int
   • Type-check arithmetic: everything is int
4. IR generation (3-address code)
   • t1 = b + 5
   • t2 = a * t1
   • t3 = t2 - 2
   • c = t3
5. Optimization
   • Propagate constants: t1=9, t2=27, t3=25
   • Final: c = 25
6. Code generation
   • Emit simple target instructions to store a, b, c