In Introduction to Compilers we treated the compiler as a single box with a front end and a back end. Building that box in one piece would be impossible to get right. Instead, compiler writers split the work into a sequence of smaller steps called phases. Each phase takes one representation of the program, transforms it, and hands a new representation to the next phase.
In this chapter we name the six classic phases plus the two helpers that every phase uses, follow one assignment statement through all of them, compare the output with what GCC really produces, and work out which phase catches which kind of error, a very common GATE and university question.
A phase is a logically separate step of compilation that converts the program from one representation to another. The standard model has six phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization and code generation, supported by a symbol table manager and an error handler.
The Six Phases at a Glance
character stream (source text)
|
+---------------------+
| Lexical Analyzer |
+---------------------+
| token stream
+---------------------+
| Syntax Analyzer |
+---------------------+
| syntax tree
+-----------+ +---------------------+ +-----------+
| | | Semantic Analyzer | | |
| | +---------------------+ | |
| | | annotated syntax tree |
| SYMBOL | +---------------------+ | ERROR |
| TABLE |---| Intermediate Code |---| HANDLER |
| MANAGER | | Generator | | |
| | +---------------------+ | |
| | | intermediate representation
| | +---------------------+ | |
| | | Code Optimizer | | |
| | |(machine-independent)| | |
+-----------+ +---------------------+ +-----------+
| improved intermediate representation
+---------------------+
| Code Generator |
+---------------------+
| target machine code
(optional machine-dependent optimization)
The first three phases form the analysis part (front end): they understand the program and find errors. The last three form the synthesis part (back end): they build the target program. Intermediate code generation is the bridge and is usually counted in the front end, since it does not yet depend on the target machine.
Phase | Input | Output | Main question it answers |
|---|---|---|---|
1. Lexical analysis (scanning) | Characters | Tokens | What are the words? |
2. Syntax analysis (parsing) | Tokens | Parse tree / syntax tree | Are the words arranged according to the grammar? |
3. Semantic analysis | Syntax tree | Annotated (type-checked) syntax tree | Does the sentence make sense? (declarations, types) |
4. Intermediate code generation | Annotated tree | IR, e.g. three-address code | How do we express it in simple machine-like steps? |
5. Code optimization | IR | Better IR | Can it be done faster or smaller? |
6. Code generation | IR | Target code (assembly / machine code) | Which real instructions and registers? |
A helpful analogy is translating an English sentence into Hindi. First you split it into words (lexical), then check the grammar (syntax), then check that it makes sense, since "The table ate the idea" is grammatical but meaningless (semantic), and only then do you write the translation (synthesis).
Our Running Example
We will follow this C statement through every phase:
float avg, m1, m2;
...
avg = (m1 + m2) / 2;
Three things make it interesting: the parentheses change the order of evaluation, the constant 2 is an int while everything else is float, and division by 2 can be done more cheaply.
Phase 1: Lexical Analysis
The lexical analyzer (scanner, lexer) reads the raw characters left to right and groups them into meaningful units called lexemes. For each lexeme it outputs a token of the form <token-name, attribute-value>. Whitespace and comments are thrown away here.
Lexeme | Token | Note |
|---|---|---|
| <id, 1> | 1 = symbol-table entry for avg |
| <=> | no attribute needed |
| <(> | |
| <id, 2> | entry 2 |
| <+> | |
| <id, 3> | entry 3 |
| <)> | |
| </> | |
| <num, 2> | attribute = the value |
| <;> |
So the 20 characters of the statement become a stream of 10 tokens:
<id,1> <=> <(> <id,2> <+> <id,3> <)> </> <num,2> <;>
The symbol table now has entries for the three names (their type, float, was recorded when the declaration was processed):
+---+------+-------+-----
| # | name | type | ...
+---+------+-------+-----
| 1 | avg | float |
| 2 | m1 | float |
| 3 | m2 | float |
+---+------+-------+-----
Details of tokens, lexemes and patterns are in Lexical Analysis: Tokens, Lexemes & Patterns.
Phase 2: Syntax Analysis
The syntax analyzer (parser) checks that the token stream follows the grammar of the language and builds a tree that shows the structure. Interior nodes are operators; children are operands.
=
/ \
<id,1> /
/ \
+ <num,2>
/ \
<id,2> <id,3>
Notice that the parentheses are gone. They were needed only to tell the parser that + must be done before /; that fact is now encoded in the tree's shape (the + node is below the / node, so it is evaluated first). This compact tree is a syntax tree (abstract syntax tree). The full parse tree, which also shows every grammar rule used, is covered in Syntax Analysis & Context-Free Grammars.
If the statement had been avg = (m1 + m2 / 2;, this is the phase that would complain about the missing ).
Phase 3: Semantic Analysis
A program can be grammatically perfect and still be meaningless. The semantic analyzer uses the syntax tree and the symbol table to check meaning, mainly:
Declarations: is every name declared before use? Is anything declared twice in the same scope?
Type checking: does each operator get operands of acceptable types? Does a function get the right number and types of arguments?
Implicit conversions (coercions): where the language allows mixing types, insert the conversion explicitly.
In our example, m1 + m2 is float + float, fine. But the division is float / int. C's rules say the int is converted to float, so the semantic analyzer inserts a conversion node:
=
/ \
<id,1> / (type float)
/ \
+ inttofloat (type float)
/ \ |
<id,2> <id,3> <num,2>
Every node is now annotated with a type, and the result type (float) matches avg, so the assignment is valid. See Semantic Analysis & Type Checking for the full story.
Phase 4: Intermediate Code Generation
Next the compiler produces an intermediate representation that is easy to produce from the tree and easy to translate into machine code. A popular form is three-address code: every instruction has at most one operator on the right side, and compiler-generated temporaries (t1, t2, ...) hold intermediate results.
t1 = id2 + id3
t2 = inttofloat(2)
t3 = t1 / t2
id1 = t3
Reading it bottom-up from the tree: first the +, then the conversion, then the /, then the assignment. It looks like assembly for an imaginary machine with unlimited registers. More in Intermediate Code & Three-Address Code.
Phase 5: Code Optimization
The machine-independent code optimizer improves the intermediate code without changing what it computes. Here three improvements are possible:
Compile-time conversion:
inttofloat(2)always gives2.0, so do it now and dropt2.Strength reduction: dividing by
2.0gives exactly the same floating-point result as multiplying by0.5(0.5 is exactly representable, so both operations compute the same exact value x/2 and round it the same way), and multiplication is much cheaper than division on most CPUs.Copy elimination:
t3is computed only to be copied intoid1, so compute directly intoid1.
t1 = id2 + id3
id1 = t1 * 0.5
Four instructions became two. Note that replacing / 3.0 with * 0.3333... would not be allowed, because 1/3 is not exactly representable and the results could differ in the last bit. Optimizations must preserve meaning exactly. Details are in Code Optimization Techniques.
Phase 6: Code Generation
The code generator maps the IR onto real instructions: it chooses instructions, assigns variables and temporaries to registers, and decides memory locations. For a simple register machine (F means floating point; # marks an immediate constant):
LDF R1, id2 ; R1 = m1
LDF R2, id3 ; R2 = m2
ADDF R1, R1, R2 ; R1 = m1 + m2
MULF R1, R1, #0.5 ; R1 = R1 * 0.5
STF id1, R1 ; avg = R1
Register allocation, instruction selection and instruction ordering are the hard problems here; see Code Generation & Register Allocation.
What GCC Really Does with This Statement
Our textbook walk-through is not just theory. We compiled this function with GCC 15.2 on x86-64 Linux (with -fcf-protection=none to hide the extra endbr64 security instruction):
float average(float m1, float m2) {
float avg;
avg = (m1 + m2) / 2;
return avg;
}
GCC's intermediate code. GCC's main IR is called GIMPLE, and it is a three-address code. gcc -fdump-tree-gimple shows:
float average (float m1, float m2)
{
float D.2837;
float avg;
_1 = m1 + m2;
avg = _1 / 2.0e+0;
D.2837 = avg;
return D.2837;
}
Here _1 is a temporary, exactly like our t1, and the semantic analysis has already turned the int 2 into the float constant 2.0e+0.
Without optimization (-O0), the generated code still uses a real division instruction:
movss xmm0, DWORD PTR -20[rbp] ; m1
addss xmm0, DWORD PTR -24[rbp] ; + m2
movss xmm1, DWORD PTR .LC0[rip]
divss xmm0, xmm1 ; / 2.0
...
.LC0: .long 1073741824 ; bit pattern 0x40000000 = 2.0f
With optimization (-O2), the whole function becomes three instructions:
average:
addss xmm0, xmm1 ; m1 + m2
mulss xmm0, DWORD PTR .LC0[rip] ; * 0.5 (division replaced!)
ret
.LC0: .long 1056964608 ; bit pattern 0x3F000000 = 0.5f
The division has been replaced by a multiplication by 0.5, the same strength reduction we did by hand, and the temporaries and memory copies have vanished into registers.
The Two Helpers
Symbol table manager
The symbol table is a data structure that stores one record for each name in the program (variables, functions, types, labels) with its attributes, such as type, scope, storage location, and for functions the number and types of parameters.
Every phase uses it. The lexer enters names (or the parser does, once it knows the name is being declared), the semantic analyzer reads types from it, the intermediate and code generators read storage locations. It must allow fast insertion and lookup, which is why hash tables are the usual choice. See Symbol Table.
Error handler
Each phase can detect errors. The error handler reports them with a useful message and location, and helps the phase recover so compilation can continue and report further errors instead of stopping at the first one.
Which Phase Detects Which Error?
This is asked very often. Here are real GCC 15.2 messages for small broken programs:
Code fragment | GCC message | Phase |
|---|---|---|
|
| Lexical: |
|
| Lexical: unterminated string literal |
|
| Lexical: |
|
| Syntax |
|
| Semantic |
|
| Semantic (type error) |
calling |
| Not a compiler phase: the linker |
| (none at compile time) | Run-time error, not detected by the compiler |
A neat rule of thumb:
Lexical errors are about single words: characters that cannot start any token, unterminated strings or comments, malformed numbers, over-long identifiers.
Syntax errors are about the arrangement of tokens: missing semicolons or brackets, misplaced keywords,
a = * b;.Semantic errors need declarations and types: undeclared or redeclared names, type mismatches, wrong number of arguments,
breakoutside a loop.
A misspelled keyword such as whlie (x < 5) is not a lexical error: whlie is a perfectly good identifier. The error appears later, typically as a syntax error (or, in C, an implicit-declaration problem).
Phases vs Passes
A phase is a logical step of translation. A pass is one physical reading of the program (source or intermediate form) from beginning to end, often writing an intermediate file or structure.
Several phases can be grouped into one pass. For example, in many front ends the parser is in control and calls the lexer each time it needs the next token, while semantic actions and intermediate code generation happen during parsing. Lexical, syntax, semantic analysis and IR generation then all happen in a single pass.
parser --- "get next token" ---> lexer
| <------- token -----------
|
+--> semantic checks + emit intermediate code, as each construct is recognised
Fewer passes | More passes | |
|---|---|---|
Compile speed | Faster (less reading and writing) | Slower |
Memory | Less | More (whole program or IR kept) |
Optimization | Limited (cannot look ahead in the program) | Better (whole-function or whole-program analysis) |
Language requirements | Usually needs declare-before-use | Can handle forward use |
The number of phases is fixed by the model (six); the number of passes is a design decision of each compiler.
Front End, Back End and Retargeting
Front end (analysis) | Back end (synthesis) | |
|---|---|---|
Phases | Lexical, syntax, semantic analysis, intermediate code generation (and machine-independent optimization is shared) | Machine-dependent optimization, code generation |
Depends on | Source language | Target machine |
Theory used | Regular expressions, finite automata, context-free grammars, type systems | Data-flow analysis, graph colouring, instruction scheduling |
To make a compiler produce code for a new processor (retargeting), only the back end is rewritten. To support a new language, only a new front end is written.
Common Mistakes Students Make
Calling an undeclared variable a syntax error.
return y;is grammatically correct; it is a semantic error.Calling a misspelled keyword a lexical error.
whlieis a valid identifier token.Thinking every phase is compulsory. Code optimization can be skipped (that is roughly what
-O0does) and the program is still correct, only slower. The other five phases are always needed.Saying only the lexer uses the symbol table. All phases use it.
Confusing "phase" with "pass": six phases can be done in one pass or in many.
Keeping parentheses in the syntax tree. They are only grouping hints; the tree's shape replaces them.
GATE / Interview Questions
1. In a compiler, keywords of a language are recognised during which phase?
Lexical analysis. The scanner recognises if, while and so on as keyword tokens (typically by checking each identifier-like lexeme against a table of reserved words).
2. Type checking is normally done during which phase?
Semantic analysis.
3. Which data structure in a compiler stores information about variables and their attributes, and which phases use it?
The symbol table. It is used by all phases: entries are created during analysis, types are read in semantic analysis, and storage information is used in intermediate code and code generation.
4. Match: (P) lexical analysis, (Q) syntax analysis, (R) semantic analysis, (S) code generation with (1) type checking, (2) regular expressions, (3) register allocation, (4) context-free grammars.
P-2, Q-4, R-1, S-3.
5. Classify the errors: (a) int 9lives; (b) if (x > 0 { } (c) float f; f(); (d) the character $ in standard C code.
(a) Lexical: 9lives is a malformed number. (b) Syntax: missing ). (c) Semantic: calling something that is not a function. (d) Lexical: a character that cannot begin any token (note that GCC accepts $ in identifiers as an extension, so a strictly standard compiler is assumed).
6. Give the three-address code for x = a + b * c.
t1 = b * c, then t2 = a + t1, then x = t2. Multiplication comes first because it binds more tightly than addition.
7. What is the difference between a phase and a pass?
A phase is a logical transformation step (e.g. syntax analysis). A pass is one complete traversal of the program or its IR. Multiple phases may be combined in a single pass, and one phase (like optimization) may need several passes.
8. Why is intermediate code used instead of generating machine code directly from the syntax tree?
It separates the language-dependent front end from the machine-dependent back end (easy retargeting, m + n instead of m x n compilers), and it is a convenient form for machine-independent optimization.
Summary
The six phases are lexical analysis (characters to tokens), syntax analysis (tokens to tree), semantic analysis (type checks, conversions), intermediate code generation (e.g. three-address code), code optimization and code generation.
All phases share the symbol table and report to the error handler.
For
avg = (m1 + m2) / 2;: 10 tokens, a tree without parentheses, an insertedinttofloat, four lines of three-address code reduced to two (t1 = id2 + id3; id1 = t1 * 0.5), and five target instructions. GCC does the same: its GIMPLE IR is three-address code and-O2replaces the division withmulssby 0.5.Lexical errors concern single tokens, syntax errors the arrangement of tokens, semantic errors meaning (declarations and types). Undefined references are linker errors.
Phases are logical steps; passes are physical traversals, and several phases can share one pass.
Now we zoom into the first phase. The next chapter, Lexical Analysis: Tokens, Lexemes & Patterns, explains exactly what a scanner produces and how tokens are specified.