Program Compilation Stages
Compilation transforms human-readable source code into lower-level representations that can eventually be executed by a computer. Along the way, a compiler recognises tokens, checks grammar and meaning, creates intermediate code, may optimise it, and generates target code.
Learning Objectives
- 12.5.1.3 Describe programme compilation stages: lexical analysis, syntactic analysis, semantic analysis, intermediate code generation, optimization and target code generation.
- 12.5.1.4 Understand the role of linkers, loaders and library routines.
The Compilation Pipeline
Compilation is not one giant translation step. It is a sequence of stages. Each stage receives an input, performs a specialised task and passes a new representation to the next stage.
1. Lexical Analysis
Reads source characters, groups them into lexemes and classifies those lexemes as tokens.
int total = 42; TYPE IDENTIFIER(total) ASSIGNMENT INTEGER(42) SEMICOLON
Two Broad Phases
At school level, the compilation process can be grouped into two broad parts: analysis, which understands and checks the source program, and synthesis, which constructs lower-level output from the analysed program.
Analysis
Breaks down source code, checks its structure and meaning, and builds an internal representation.
Synthesis
Uses the analysed representation to create intermediate, improved and target-level code.
Extension: Front End, Middle End and Back End
Front End
Understands the source language: lexical, syntax, semantic analysis and usually IR creation.
Middle End
Analyses and improves machine-independent intermediate representations.
Back End
Selects target instructions, works with registers and produces target-specific code.
Quick Recap: Compiler, Interpreter and Assembler
Compiler
Translates a complete high-level program into object or target code before normal execution.
Interpreter
Translates and executes instructions during execution rather than first producing a standalone executable.
Assembler
Translates assembly-language instructions into machine/object code.
Real execution models can be hybrid
Java normally compiles source into JVM bytecode. Python implementations may also compile source into an intermediate bytecode before execution.
One Program Through the Whole Compiler
Follow one statement all the way through the pipeline. Its meaning stays the same, but its internal representation changes from stage to stage.
int result = (3 + 4) * x;
Source Code
Human-readable high-level code written by the programmer.
int result = (3 + 4) * x;
Video Overview
Stages of Compilation
Watch the overview once, then use the interactive sections below to study each stage in detail.
1. Lexical Analysis
The lexical analyser, or lexer/scanner, reads the source program as characters, groups characters into lexemes, classifies them as tokens, and passes a token stream to the parser.
Classify tokens
Token vs Lexeme
A lexeme is the actual character sequence written in the source program. A token is the category assigned to that lexeme.
Tokeniser Lab
Edit the C-like statement and press Tokenise. This simplified classroom lexer recognises common keywords, identifiers, numbers, operators and punctuation.
1 Main Tasks of the Lexer
- Read source code as a stream of characters.
- Group characters into lexemes.
- Classify lexemes as tokens.
- Recognise keywords, identifiers, literals, operators and punctuation.
- Usually ignore comments and non-significant whitespace.
- Report invalid characters or malformed token patterns.
Whitespace is not always meaningless
In many languages spaces mainly separate tokens. Python is a useful exception: indentation has syntactic meaning because it marks blocks of code.
The Symbol Table
Several compiler stages use a symbol table to store information about identifiers such as their name, type and scope.
| Identifier | Type | Scope | Kind |
|---|---|---|---|
result |
int |
local | variable |
x |
int |
local | variable |
2. Syntax Analysis — Parsing
The parser receives the token stream and checks whether the tokens follow the grammar of the programming language. It builds a structural representation such as a parse tree or an abstract syntax tree.
Syntax Error Example
int result = (3 + 4 * x;
The opening parenthesis has no matching closing parenthesis.
Parse Tree vs Abstract Syntax Tree
| Parse Tree | Abstract Syntax Tree (AST) |
|---|---|
| Closely represents grammar rules. | Represents essential program structure. |
| May contain nodes such as expression, term and factor. | Usually uses operators and operands as important nodes. |
| More detailed and verbose. | More compact. |
| Includes more concrete syntax detail. | Omits unnecessary punctuation while preserving structure. |
Parse Tree ↔ AST Explorer
Compare two structural representations of a * b + c.
Notice that operator precedence makes * occur below the root
+.
-
expr
-
expr
-
term
- a
- *
- b
-
term
- +
-
term
- c
-
expr
-
+
-
*
- a
- b
- c
-
*
3. Semantic Analysis
A statement can be grammatically valid but still be meaningless. Semantic analysis checks that the syntactically correct program obeys type, declaration, scope and operation rules.
- Check that identifiers have been declared.
- Check variable and expression data types.
- Check operator compatibility.
- Check function arguments and return types.
- Check scope rules.
Error Classifier
Decide whether each example is most likely a lexical, syntax or semantic error.
int 2age = 15;
Memory rule
Lexical = invalid word/symbol pattern · Syntax = invalid grammar · Semantic = valid grammar but invalid meaning/type.
4. Intermediate Code Generation
After analysis, the compiler can produce an Intermediate Representation (IR). IR is easier to analyse and optimise than the original source code and is usually less dependent on a specific processor.
a = b + c * d;
t1 = c * d
t2 = b + t1
a = t2
2 Common Intermediate Representations
| IR | Idea |
|---|---|
| Three-address code | Break complex expressions into simple instructions using temporary values. |
| Bytecode | Intermediate instructions intended for a virtual machine. |
| Stack code | Operations use a stack rather than many explicit addresses. |
| Postfix notation | Operators follow operands, for example A B +. |
5. Code Optimization
Optimization transforms intermediate code to improve efficiency while preserving the program's observable behaviour. The aim may be faster execution, smaller code or reduced memory usage.
Constant Folding
Calculate constant expressions during compilation.
Before:
t1 = 3 + 4
t2 = t1 * x
After:
t1 = 7
t2 = 7 * x
Algebraic Simplification
Remove operations that do not change the result.
Before:
y = x + 0
After:
y = x
Dead Code Elimination
Remove instructions that cannot affect observable output.
return total;
total = total + 10;
Second line is unreachable.
Optimization must preserve meaning
The optimized program should still produce the same observable result as the unoptimized program.
6. Target Code Generation
The final compiler stage converts optimized intermediate code into instructions for the target processor or execution environment. The exact result depends on the target architecture.
result = 7 * x
Register use
MOV R1, x
MUL R1, 7
MOV result, R1
Simplified model
The target instructions shown here are illustrative. Real instruction generation depends on the processor, calling conventions and compiler.
After Compilation — Linker, Loader & Libraries
Generating object code is not always the final step before a program runs. Large programs may contain several object modules and use pre-written library routines.
Object Files and Library Routines
Object files are separately compiled program components. Library routines are pre-written and tested reusable code that can be linked into a program.
Linker vs Loader
Linker: combines object modules/libraries and resolves references.
Loader: places the executable into main memory and prepares it to run.
Compilation Stages Summary
| Stage | Input | Main purpose | Typical output |
|---|---|---|---|
| Lexical Analysis | Characters | Recognise lexemes and classify tokens | Token stream |
| Syntax Analysis | Tokens | Check grammar and order | Parse Tree / AST |
| Semantic Analysis | AST + symbol table | Check meaning, types and declarations | Checked / annotated representation |
| Intermediate Code Generation | Checked representation | Create machine-independent form | Intermediate Representation |
| Code Optimization | IR | Improve efficiency without changing behaviour | Optimized IR |
| Target Code Generation | Optimized IR | Generate target instructions | Object / machine code |
Common Pitfalls
Token ≠ Lexeme
total is a lexeme. IDENTIFIER is its token category.
Parser ≠ Parse Tree
The parser is the compiler component. The parse tree is a representation that may be produced during parsing.
AST ≠ Parse Tree
A parse tree closely reflects grammar rules; an AST removes unnecessary concrete syntax and preserves important structure.
Syntax ≠ Semantics
Syntax asks “Is it written correctly?” Semantics asks “Does it make sense?”
Compiler ≠ Linker ≠ Loader
Compilation translates program representations. Linking combines compiled components. Loading places the executable into memory when it is run.
Practice Tasks
Put the six compilation stages in the correct order.
Explain the difference between a token and a
lexeme using total = price + 5;.
Create a token/lexeme table for:
while (score >= pass) score = score - 5;
Create an AST for (a + b) * c.
Classify the following as lexical, syntax or semantic errors:
invalid identifier 2age, incomplete expression
price + ;, and assigning a string to an integer.
Convert a = b + c * d; into simple three-address code.
Apply constant folding or dead code elimination to improve a short program without changing its observable result.
Explain the difference between a linker and a loader, including when each is used.
Exam Practice
Q1: State what is meant by program compilation. [1]
Reveal marking point
Q2: Describe two activities performed during lexical analysis. [2]
Reveal marking points
Q3: Describe the purpose of syntax analysis. [2]
Reveal marking points
Q4: State two possible results of code optimization. [2]
Reveal marking points
Q5: Explain the difference between a linker and a loader. [4]
Reveal marking points
Self-Check Quiz
Q1: What does the lexical analyser pass to the parser?
Q2: Why is an AST called “abstract”?
Q3: Which stage normally performs type checking?
Q4: Why is intermediate code useful?
Q5: Should optimization change the intended program result?
Q6: What does a linker do?
Q7: What does a loader do?