Chapter 03 of 33

Phases of a Compiler

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

avg

<id, 1>

1 = symbol-table entry for avg

=

<=>

no attribute needed

(

<(>

m1

<id, 2>

entry 2

+

<+>

m2

<id, 3>

entry 3

)

<)>

/

</>

2

<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:

  1. Compile-time conversion: inttofloat(2) always gives 2.0, so do it now and drop t2.

  2. Strength reduction: dividing by 2.0 gives exactly the same floating-point result as multiplying by 0.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.

  3. Copy elimination: t3 is computed only to be copied into id1, so compute directly into id1.

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

int a = 3 @ 4;

stray '@' in program

Lexical: @ is not a valid character in C

char *s = "hello;

missing terminating " character

Lexical: unterminated string literal

int 2x = 5;

invalid suffix 'x' on integer constant

Lexical: 2x is a malformed number

int x = 10 (no ;) then return x;

expected ',' or ';' before 'return'

Syntax

return y; with no y declared

'y' undeclared (first use in this function)

Semantic

int n = p * 2; where p is a struct

invalid operands to binary * (have 'struct point' and 'int')

Semantic (type error)

calling add() that is declared but defined nowhere

undefined reference to 'add' (from ld)

Not a compiler phase: the linker

x = a / b; where b is 0 when the program runs

(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, break outside 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. whlie is a valid identifier token.

  • Thinking every phase is compulsory. Code optimization can be skipped (that is roughly what -O0 does) 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 inserted inttofloat, 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 -O2 replaces the division with mulss by 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.