Self-checkedTier 1 11 min readcd.compiler-phases

Phases of a compiler

What a compiler is and the phases it is built from: lexical, syntax and semantic analysis, intermediate code, optimisation and code generation, the symbol table and error handling, front end and back end, phases versus passes, and which phase catches which error.

Why it exists

A processor runs only machine instructions, but people write programs in languages with names, types, expressions and loops. Something must translate one into the other. Doing it in one step is hard and error-prone, so a compiler splits the job into phases. Each phase solves one well-defined problem (cut the text into words, check the sentence structure, check the types, choose instructions) and hands a cleaner representation to the next phase.

The split also pays off in a way that GATE asks about: if every language-to-machine pair needed its own compiler, supporting $m$ languages on $n$ machines would need $m \times n$ compilers. With a common intermediate representation, each language needs one front end that produces it and each machine one back end that consumes it: only $m + n$ pieces.

Prerequisites

None. This is a starting point.

None. You should be comfortable with the idea of a program as text and with the stack and the memory picture of a running C program, which the later runtime pages build on.

Precise definitions

Compiler. A program that reads a program in a source language and translates it into an equivalent program in a target language, reporting errors it finds. Interpreter. A program that executes the source program directly, statement by statement, without producing a target program. Compiled code usually runs faster; an interpreter gives faster feedback and easier debugging. Many systems mix them (Java compiles to bytecode, which a virtual machine interprets or compiles at run time).

Language processing system (the tools around a compiler):

Tool	Job
preprocessor	expands macros and includes files (`#define`, `#include`) before compilation
compiler	source to assembly (or to object code)
assembler	assembly to relocatable machine code
linker	combines object files and libraries, resolves external references
loader	places the executable in memory and starts it

The phases. The classical division:

Lexical analysis (scanning). Reads the character stream and groups it into tokens (identifiers, keywords, numbers, operators, punctuation), discarding white space and comments. Details: lexical analysis.
Syntax analysis (parsing). Checks that the token sequence follows the grammar of the language and builds a parse tree or syntax tree.
Semantic analysis. Checks what the grammar cannot: declared before use, types of operands, number of arguments. It annotates the tree with types and inserts conversions (for example inttofloat).
Intermediate code generation. Translates the tree into a machine-independent form, usually three-address code.
Code optimisation (machine-independent). Rewrites the intermediate code to be faster or smaller without changing its meaning: local optimisation and data flow analysis.
Code generation. Chooses target instructions, assigns registers and memory locations.
Machine-dependent optimisation (peephole and similar) may follow.

Two components work with every phase: the symbol table, which records for every name its type, scope and storage, and error handling, which detects, reports and (ideally) recovers so that more than one error is found per run.

Front end and back end. The front end (phases 1 to 4, and the machine-independent part of 5) depends on the source language and not on the machine. The back end (code generation and machine-dependent work) depends on the machine and not on the source language. The intermediate code is the interface between them. The part between is sometimes called the middle end.

Analysis and synthesis. The analysis part breaks the source into pieces and builds the intermediate representation; the synthesis part builds the target program from it. The symbol table is shared.

Phase versus pass. A phase is a logical step; a pass is one reading of the whole program (or of its representation) from beginning to end. Several phases may be combined in one pass (a lexer, parser and semantic checker working together, which is what syntax-directed translation does), and a phase may need several passes. A single-pass compiler is fast and small but cannot do global optimisation, because it never sees the whole program at once.

Cross-compiler. Runs on one machine and produces code for another. Bootstrapping. Writing a compiler for a language in that language itself and compiling it with an earlier, simpler compiler.

Which phase finds which error.

Error	Phase that finds it	Why
an illegal character such as `@` in C, a malformed number `1.2.3`	lexical analysis	no token pattern matches
a missing semicolon, unbalanced parenthesis, `else` without `if`	syntax analysis	the token sequence is not derivable from the grammar
use of an undeclared variable, assigning a string to an int, wrong number of arguments	semantic analysis	needs the symbol table and types, which a context-free grammar cannot express
division by zero, array index out of range, null pointer	none (run time)	the value is known only when the program runs

How it works

The animation compiles one assignment, position = initial + rate * 60, with a real (very small) compiler. Step through it and watch the same program change shape: characters, tokens, tree, typed tree, three-address code, shorter three-address code, machine code. Every phase output was produced by running that phase; nothing is typed in. The script also runs the source, the unoptimised code, the optimised code and the machine code on sample values and checks that they compute the same result.

The phases of a compiler: source program

Every phase actually run

source program

position = initial + rate * 60

Step 0

The source program is just characters. A compiler is a pipeline of phases; each takes the output of the one before. The first six phases are shown here, run for real on this one assignment.

0 / 6

computed by script: the algorithm is executed, one move per step. python3 scripts/gen-cd-traces.py

Two details to notice. The grammar lets 60 appear next to rate, but only the semantic analyser knows that rate is a float and 60 an int, so only it can insert inttofloat. And the optimiser removes one instruction by converting the constant at compile time, which is a transformation on the intermediate code that does not care about any machine.

Worked examples

EX 1Which phase reports the error?

Easy

For each C fragment, name the phase that detects the problem.

int x = 12$; the $ does not belong to any token pattern: lexical analysis.
x = (a + b; the closing parenthesis is missing, so the tokens are not a sentence of the grammar: syntax analysis.
y = z + 1; where z was never declared: semantic analysis (symbol table lookup fails).
char *p = 3.5; incompatible types: semantic analysis.
a[10] with int a[5]; the index is a run-time value in general, so a compiler normally cannot reject it: not a compile-time error (undefined behaviour at run time).

EX 2Tokens of an assignment

Easy

How many tokens does position = initial + rate * 60 have? The tokens are position, =, initial, +, rate, *, 60: three identifiers, one number and three operators, so 7 tokens. The blanks are not tokens. (The mini compiler's lexer gives the same count, and so does the real C lexer in the lexical analysis page's check.)

EX 3Why an intermediate representation saves work

Medium

A company supports 4 source languages on 5 target machines. Without an intermediate representation every pair needs its own compiler: $4 \times 5 = 20$ . With one, it needs 4 front ends and 5 back ends: $4 + 5 = 9$ . Adding a sixth machine costs one back end (10 total) instead of four new compilers.

EX 4Three-address code before and after optimisation

Medium

Generate three-address code for a = b + c * d - e, all variables float. Because * binds tighter than + and -, which are left-associative, the tree is $(b + (c \cdot d)) - e$ and the code is

t1 = c * d
t2 = b + t1
t3 = t2 - e
a = t3

Four instructions. The temporary t3 exists only to be copied to a, so the optimiser computes straight into a:

t1 = c * d
t2 = b + t1
a = t2 - e

(This is what the mini compiler produces and checks.) For x = 2 * 3 + a the unoptimised code needs a temporary for 2 * 3, one for inttofloat, one for the sum, and the copy; after constant folding the whole code is x = 6.0 + a.

EX 5Phase or pass?

GATE level

A compiler reads the source once from left to right, scanning, parsing and checking types in one sweep, and generating code as it goes. Is it a one-phase compiler? No: it still has the logical phases (scanning, parsing, checking, generation) but they are combined into a single pass. What it cannot do is any optimisation that needs the whole program, such as moving code out of a loop that appears later in the text, or deciding which variables are never used. That is why optimising compilers use several passes over an intermediate representation.

Cheat box

Phases in order: lexical, syntax, semantic, intermediate code, optimisation, code generation. Symbol table and error handling serve all of them.
Lexical: characters to tokens. Syntax: tokens to a tree (grammar). Semantic: types, declarations, conversions.
Front end: source-language dependent. Back end: machine dependent. Intermediate code in between: $m + n$ instead of $m \times n$ compilers.
Phase is logical; pass is a physical read of the program. Several phases can share one pass.
Illegal character: lexical. Missing bracket: syntax. Undeclared name or type mismatch: semantic. Divide by zero: run time.
Preprocessor, compiler, assembler, linker, loader: the language processing chain.

Traps and GATE patterns

Connections

Builds on

No prerequisites.

Unlocks

Lexical analysisPrerequisite of Lexical analysisuses Storage organisation: static, stack and heapuses

Across subjects

Recursion and the call stackanalogous-to

Within this subject

Lexical analysisimplemented-by Three-address code, quadruples and triplesimplemented-by Local optimisationimplemented-by

The first phase is described in lexical analysis. The grammar that the second phase uses is the context-free grammar of the language, and the parsing methods follow in LL(1) parsing and LR parsing. The intermediate form is three-address code, which the optimiser improves in local optimisation. The names and addresses kept in the symbol table are used again in activation records, the run-time counterpart of the stack you saw in recursion and the call stack.

PYQs

17 previous year questions from your book. I re-solved each one myself (4 by running or simulating, 13 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2025 · MCQQ2 · page 251 of the book

Which ONE of the following statements is FALSE
regarding the symbol table?

(a)Symbol table is responsible for keeping track of the scope of variables.
(b)Symbol tables can be implemented using a binary search tree.
(c)Symbol table is not required after the parsing phase.
(d)Symbol table is created during the lexical analysis phase.

GATE 2024 · MCQQ3 · page 251 of the book

Consider the following two sets:

P. Lexical Analyzer
1. Abstract Syntax Tree
Q. Syntax Analyzer
2. Token
R.Intermediate
code
Generator
3. Parse Tree
S. Code Optimizer
4. Constant Folding

Which one of the following options is the CORRECT
match from Set X to Set Y?

(a)P-4; Q-1; R-3; S-2
(b)P-2; Q-3; R-1; S-4
(c)P-2; Q-1; R-3; S-4
(d)P-4; Q-3; R-2; S-1

GATE 2017 · MCQQ5 · page 251 of the book

Match the following according to input (from the left
column) to the compiler phase (in the right column)
that processes it:
(P) Syntax Tree
(i) Code Generator
(Q) Character Stream
(ii) Syntax Analyzer
(R)Intermediate
Representation
(iii)Semantic
Analyzer
(S) Token Stream
(iv) Lexical Analyzer

COMPILER DESIGN

(a)P-ii, Q-iii, R-iv, S-i
(b)P-ii, Q-i, R-iii, S-iv
(c)P-iii, Q-iv, R-i, S-ii
(d)P-i, Q-iv, R-ii, S-iii

GATE 2016 · MCQQ6 · page 252 of the book

Match the following
List-1
List-2
P. Lexical analysis
(i)Leftmost derivation
Q. Top-down parsing   (ii) Type checking
R. Semantic analysis    (iii)Regular expressions
S.Runtime
environments
(iv)Activation records

(a)P-i, Q-ii, R-iv, S-iii
(b)P-iii, Q-i, R-ii, S-iv
(c)P-ii, Q-iii, R-i, S-iv
(d)P-iv, Q-i, R-ii, S-iii

GATE 2015 · MCQQ7 · page 252 of the book

Match the following ?
GROUP 1
GROUP 2
P. Lexical analysis
1. Graph coloring
Q. Parsing
2. DFA minimization
R. Register allocation
3. Post- order traversal
S. Expression evaluation
4. Production Tree

(a)P-2, Q-3, R-1, S-4
(b)P-2, Q-1, R-4, S-3
(c)P-2, Q-4, R-1, S-3
(d)P-2, Q-3, R-4, S-1

GATE 2010 · MCQ · 1 markQ10 · page 252 of the book

Which data structure in a compiler is used for
managing information about variables and their
attributes?

(a)Abstract syntax tree
(b)Symbol table
(c)Semantic stack
(d)Parse Table COMPILER DESIGN

GATE 2009 · MCQ · 1 markQ11 · page 253 of the book

Match all items in Group 1 with correct options
from those given in Group 2.

Group 1
Group 2
P.
Regular
expression
1.
Syntax
analysis
Q.
Pushdown
automata
2.
Code
generation
R.
Dataflow
analysis
3.
Lexical
analysis
S.
Register
allocation
4.
Code
optimization

(a)P-4. Q-1, R-2, S-3
(b)P-3, Q-1, R-4, S-2
(c)P-3, Q-4, R-1, S-2
(d)P-2, Q-1, R-4, S-3

GATE 2005 · MCQQ13 · page 253 of the book

Consider line number 3 of the following C- program.
                  int main ( ) {                           /*Line 1 */
                  int I, N;
/*Line 2 */
                  fro (I = 0, I < N, I++);         /*Line 3 */
                     }

Identify the compiler's response about this line while
creating the object-module

(a)Both lexical and syntactic errors
(b)Only a lexical error
(c)Only syntactic errors
(d)No compilation error

GATE 2005 · MCQQ14 · page 253 of the book

Consider the following C-program:

double foo (double); /* Line 1 */

int main()

{

double da, db;

// input da

db = foo(da);

}

double foo(double a)

{

    return a;

}

COMPILER DESIGN

(a)no compile warning or error
(b)some compiler-warnings not leading to unintended results
(c)some compiler-warnings due to type- mismatch eventually leading to unintended results
(d)compiler errors

GATE 2026 · MCQQ2 · page 256 of the book

Consider the following C statements:
             char *str1 = "Hello; /* Statement S1 */
             char *str2 = "Hello;"; /* Statement S2 */
              int *str3 = "Hello"; /* Statement S3 */

Which of the following options is/are correct?

(a)S1 and S2 have syntactic errors
(b)S2 has a lexical error and S3 has a syntactic error
(c)S1 has a lexical error and S3 has a semantic error
(d)S1 has a syntactic error and S3 has a semantic error

GATE 2018 · MCQ · 1 markQ17 · page 258 of the book

Which one of the following statements is FALSE?

(a)Context-free grammar can be used to specify both lexical and syntax rules.
(b)Type checking is done before parsing.
(c)High-level language programs can be translated to different Intermediate Representations.
(d)Arguments to a function can be passed using the program stack. COMPILER DESIGN

GATE 2014 · NATQ26 · page 260 of the book

Consider the expression tree shown. Each leaf represents a
numerical value, which can either be 0 or 1. Over all
possible choices of the values at the leaves, the maximum
possible value of the expression represented by the tree
is __________ ,

GATE 2007 · MCQ · 1 markQ37 · page 263 of the book

Consider the CFG with {S, A, B} as the non-
terminal alphabet, {a,b} as the terminal alphabet, S
as the start symbol and the following set of
production rules:

S → aB     S → bA

B → b      A → a

B → bS     A → aS

B → aBB   S → bAA

Which of the following strings is generated by the
grammar?

(a)aaaabb
(b)aabbbb
(c)aabbab
(d)abbbba

GATE 2021 · MCQQ8 · page 274 of the book

Consider the following ANSI C program:

int main() {

Integer x;

return 0;

}

Which one of the following phases in a seven-phase
C compiler will throw an error?

(a)Lexical analyzer
(b)Machine dependent optimizer
(c)Semantic analyzer
(d)Syntax analyzer

GATE 2020 · MCQ · 1 markQ9 · page 274 of the book

Consider the following statements.

I.
Symbol table is accessed only during lexical
analysis and syntax analysis.

II.
Compilers for programming languages that
support recursion necessarily need heap
storage for memory allocation in the run-time
environment.

III.
Errors violating the condition 'any variable
must be declared before its use' are detected
during syntax analysis.

Which of the above statements is/are TRUE?

(a)II only
(b)I only
(c)I and III only
(d)None of I, II and III

GATE 2023 · MCQ · 1 markQ8 · page 281 of the book

Consider the following statements regarding the
front-end and back-end of a compiler: -

S1: The front-end includes phases that are
independent of the target hardware.
S2: The back-end includes phases that are specific
to the target hardware.
S3: The back-end includes phases that are specific
to the programming language used in the source
code.
Identify the CORRECT option.

(a)Only S1 is TRUE.
(b)Only S1 and S2 are TRUE.
(c)S1, S2, and S3 are all TRUE.
(d)Only S1 and S3 are TRUE.

GATE 2014 · MCQQ18 · page 282 of the book

Which one of the following is NOT performed during
compilation?

(a)Dynamic memory allocation
(b)Type checking
(c)Symbol table management
(d)Inline expansion

Self-check

Question 1

Which phase of the compiler can detect that a variable is used before it is declared?

Show answer

Semantic analysis, with the help of the symbol table. The grammar alone cannot express it.

Question 2

What is the output of the lexical analyser, and what does the parser build from it?

Show answer

A stream of tokens; the parser builds a parse (syntax) tree from them.

Question 3

There are 6 source languages and 8 machines. How many compilers are needed with and without a common intermediate representation (counting a front end or back end as one piece)?

Show answer

Without: $6 \times 8 = 48$ compilers. With: $6 + 8 = 14$ pieces (6 front ends and 8 back ends).

Question 4

A compiler performs scanning, parsing and code generation in one left-to-right sweep. How many passes and how many phases?

Show answer

One pass, but still several logical phases.

Revision card

One-screen revision

Phases: lexical, syntax, semantic, intermediate code, optimisation, code generation; symbol table and error handler throughout.
Front end (language) and back end (machine) meet at the intermediate code: $m + n$ not $m \times n$ .
Illegal character lexical; missing bracket syntax; undeclared name or type error semantic; divide by zero at run time.
Phase is logical, pass is a reading of the program.

References

·Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (2nd edition), Chapter 1 Introduction (the structure of a compiler)
·Cooper and Torczon, Engineering a Compiler, Chapter 1 Overview of Compilation

Verification

The phase outputs in the animation are produced by a real mini compiler (scripts/cd_mini.py): lexer, recursive-descent parser, type checker, three-address code generator, optimiser and a register-machine code generator. scripts/enum-checks/cd_front.py runs 3000 random assignments through every phase and the source value, the three-address code, the optimised code and the machine code always agree. The classification of errors by phase is the usual textbook division; textbooks differ slightly on whether some checks (for example reachability warnings) belong to semantic analysis or to optimisation. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (token counts, FIRST and FOLLOW sets, LL(1) tables and moves, LR item sets, state counts and parses, operator-precedence values, attribute evaluation and printing schemes, activation-record counts and access links, parameter-passing results, three-address code, jumping and backpatched code, leaders and blocks, value numbering and DAGs, gen/kill and data flow sets, Sethi-Ullman labels and live ranges); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Lexical analysis