Intro to Compilers (Compiler Design): The Six Phases Traced with Worked Examples

Compiler Design can feel like a pile of jargon: lexeme, LALR, three-address code, coercion. Students often memorise six phases without ever seeing them do any work. One assignment, position = initial + rate * 60, is enough to make all six visible: it leaves behind a token stream, a syntax tree, a coercion node, four three-address instructions, two optimised ones and five assembly instructions. Those artefacts are what GATE CS, vivas and interviews ask you to name.

What a compiler actually does: analysis then synthesis

A compiler translates a complete high-level source program into an equivalent target program, usually assembly or machine code, and reports translation errors.

The front end performs mostly machine-independent analysis: lexical, syntax and semantic analysis, then intermediate-code generation. The back end performs machine-dependent synthesis through optimisation and code generation. This split lets one front end feed several back ends.

Models can mix. Java's javac compiles source to bytecode, which the JVM interprets or JIT-compiles. The wider flow is preprocessor, compiler, assembler, linker and loader.

The six phases end to end

The logical pipeline has six phases:

1. Lexical analysis: converts source characters into tokens.

2. Syntax analysis: applies a grammar to build a parse tree or syntax tree.

3. Semantic analysis: checks types, declarations and scope.

4. Intermediate-code generation: produces machine-independent three-address code.

5. Code optimisation: improves that intermediate representation without changing meaning.

6. Code generation: converts the result into target assembly or machine code.

Across all phases, the symbol table manager stores identifier attributes and the error handler reports each phase's errors.

Take position = initial + rate * 60. Here position, initial and rate are float variables while 60 is an integer literal, and that single type mismatch is what forces the semantic phase into visible work further down the pipeline.

One statement through the whole compiler pipeline

1. Lexical analysis. The scanner discards spaces and emits:

<id,1> <=> <id,2> <+> <id,3> <*> <60>

It records 1 -> position, 2 -> initial and 3 -> rate in the symbol table. The other outputs are operator tokens and a number token.

2. Syntax analysis. The parser builds this syntax tree:

      =
     / \
   id1   +
        / \
      id2   *
           / \
         id3  60

Multiplication has higher precedence, so rate * 60 forms the deeper subtree.

3. Semantic analysis. Type checking finds an integer inside float arithmetic and replaces the 60 leaf with inttofloat(60). This is a semantic action, not syntax.

4. Intermediate-code generation. The compiler emits four three-address instructions:

t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

There are four instructions and three temporaries: t1, t2, t3. Each right-hand side has at most one operator.

5. Optimisation. Constant folding changes inttofloat(60) to 60.0, and copy propagation removes t3:

t1 = id3 * 60.0
id1 = id2 + t1

The count falls from 4 to 2 instructions and from 3 to 1 temporary, without changing meaning.

6. Code generation. With float registers R1 and R2, output can be:

LDF   R2, id3
MULF  R2, R2, #60.0
LDF   R1, id2
ADDF  R1, R1, R2
STF   id1, R1

The float operations use LDF, MULF and ADDF; #60.0 is immediate. STF stores the result in id1. This is a three-operand target, destination then two sources; a two-operand machine would fold the destination into the first register instead, and that choice of register set and mnemonic is precisely what makes this phase machine-dependent.

Tokens, lexemes and patterns

A token is a category such as identifier. A lexeme is actual text such as position. A pattern describes valid lexemes, for example a letter followed by letters or digits. Here position maps to <id,1>.

Now count the tokens in int a = b + 3;:

1. int, keyword

2. a, identifier

3. =, operator

4. b, identifier

5. +, operator

6. 3, integer constant

7. ;, separator

The total is exactly 7. Scanners discard whitespace and comments, but keywords and separators count. A string literal such as "hello, %d" is one token. Lexical Analysis in Compiler Design explains how patterns become a recogniser.

Syntax and semantics: grammars, trees and type checks

This layered context-free grammar expresses precedence without ambiguity:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id | num

Because + is at the E level and * at the deeper T level, multiplication groups first. E -> E + E | E * E | id is ambiguous because it permits multiple parses.

A parse tree includes grammar symbols such as E, T and F; an abstract syntax tree keeps essential operators and operands. Grammar cannot check declarations, scope or type compatibility. Semantic analysis does, as inttofloat(60) shows. Context-Free Grammars and Pushdown Automata develops the theory behind parsing and LL or LR methods.

Compiler-phase traps students fall into

• Is position a token? No, it is a lexeme whose category is <id>.

• Are parse trees and syntax trees identical? No. A parse tree retains grammar symbols; a syntax tree is condensed.

• Do six phases mean six passes? No. A phase is logical; one full-input pass can run several phases.

• Is optimisation compulsory and always faster? No. It must preserve meaning and may be skipped. IR optimisation also differs from machine-dependent peephole optimisation.

• Which phase catches an error? Illegal characters are lexical, missing semicolons syntax, and undeclared variables semantic.

• Is a string several tokens? The whole literal is one; keywords, operators and semicolons also count.

How GATE and interviews test compiler phases

The official GATE Computer Science syllabus names Compiler Design. Marks, question counts and sectional timing for a given year are in that year's official notification.

Questions commonly ask which phase reports an error, token or temporary counts, precedence in trees, and the symbol table's role. That phase-to-artefact mapping is drilled row by row, with an input-phase-output table, in Phases of a Compiler for GATE. Parser internals such as LL, LR, LALR and FIRST/FOLLOW, plus syntax-directed translation, need separate practice. The GATE Test Series provides timed, exam-level work.

Interviews ask what happens to a .c file, compiler versus interpreter, symbol-table contents, and why passes are needed. Narrate the pipeline to answer them.

The short version and your next step

A compiler analyses source, then synthesises target code. Six phases turned position = initial + rate * 60 into five assembly instructions, with symbol-table and error support throughout.

Master the scanner next: its patterns, its recogniser, and the token-versus-lexeme line carry marks of their own. For structured, subject-wise coverage, use GATE Guidance by Sanchit Sir. Pair it with timed practice and explain the trace aloud.