Phases of a Compiler

Introduction

A compiler performs the translation of a high-level source program into a low-level target program through a series of well-defined phases. Each phase takes input from the previous phase, performs a specific transformation, and passes its output to the next phase. Understanding these phases is crucial for grasping how compilers work internally.

The compilation process is logically divided into two major parts:

• Analysis (Front End): Breaks the source program into constituent pieces and creates an intermediate representation
• Synthesis (Back End): Constructs the desired target program from the intermediate representation

Overview of All Phases

Phase 1: Lexical Analysis (Scanning)

The lexical analyzer reads the source program character by character and groups them into meaningful sequences called lexemes. Each lexeme is mapped to a token of the form:

Example

For the statement: position = initial + rate * 60

The lexical analyzer produces:

Where the symbol table contains:

Key Tasks

• Removes whitespace and comments
• Identifies tokens (keywords, identifiers, operators, literals)
• Stores identifiers in the symbol table
• Reports lexical errors (invalid characters, malformed numbers)

Phase 2: Syntax Analysis (Parsing)

The syntax analyzer takes the token stream from the lexical analyzer and creates a parse tree (or syntax tree) that represents the grammatical structure of the program according to the language's grammar rules.

Example

For position = initial + rate * 60, the parse tree is:

Key Tasks

• Verifies that the token arrangement follows grammar rules
• Constructs parse trees or abstract syntax trees
• Reports syntax errors (missing semicolons, unbalanced parentheses)
• Uses context-free grammars for language specification

Phase 3: Semantic Analysis

The semantic analyzer uses the syntax tree and symbol table information to check the source program for semantic consistency with the language definition. It performs type checking and ensures that operations are semantically valid.

Key Tasks

• Type checking: Ensures operators have compatible operands
• Type coercion: Inserts implicit type conversions where needed
• Scope resolution: Verifies variable declarations and visibility
• Array bounds checking: Validates array index usage

Example

Notice that the integer 60 is converted to a float using intToFloat because rate is a floating-point variable.

Phase 4: Intermediate Code Generation

After semantic analysis, the compiler generates an intermediate representation (IR) of the source program. This IR should be easy to produce and easy to translate into the target machine code.

Three-Address Code Example

For position = initial + rate * 60:

Properties of IR

• Machine-independent
• Easy to generate from syntax tree
• Easy to translate to target code
• Facilitates optimization

Phase 5: Code Optimization

The code optimizer improves the intermediate code to produce better target code — "better" meaning faster execution, less memory usage, or smaller code size. This phase is optional but crucial for performance.

Example

The intermediate code:

After optimization becomes:

Common Optimizations

• Constant folding (computing constant expressions at compile time)
• Dead code elimination
• Common subexpression elimination
• Loop optimization

Phase 6: Code Generation

The code generator takes the optimized intermediate code and produces the target code — typically assembly language or machine code for a specific processor architecture.

Example

For the optimized code above, target code might be:

Key Decisions

• Register allocation and assignment
• Instruction selection
• Instruction scheduling

Supporting Components

Symbol Table Manager

The symbol table is a data structure that stores information about identifiers (variables, functions, classes) throughout the compilation process:

• Name and type
• Scope and lifetime
• Memory location
• Number of parameters (for functions)

Error Handler

Each phase can encounter errors. The error handler:

• Reports the error location (line number, column)
• Provides meaningful error messages
• Attempts error recovery to continue compilation
• Classifies errors (lexical, syntactic, semantic)

Complete Example

Consider compiling: x = a + b * 5

Interview Questions

1. How many phases does a compiler have? Name them.

Six phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, and code generation. Two auxiliary components support all phases: the symbol table manager and the error handler.

1. What is the difference between analysis and synthesis in compilation?

Analysis (front end) breaks down the source program and creates an intermediate representation. It includes lexical, syntax, and semantic analysis. Synthesis (back end) constructs the target program from the IR and includes code optimization and code generation.

1. Why is intermediate code generation important?

It provides machine independence (same front end for different targets), facilitates optimization (easier to optimize IR than machine code), and enables retargetability (one front end, multiple back ends).

1. Which phase detects undeclared variables?

The semantic analysis phase detects undeclared variables, type mismatches, and other semantic errors using the symbol table to track declarations and scopes.

1. Is code optimization a mandatory phase?

No, code optimization is optional. A compiler can work without it, but optimization significantly improves the quality of generated code in terms of speed and resource usage.