1.2 Phases of a Compiler: Analysis vs Synthesis, Front-End vs Back-End

Back to DBMS Notes

📚Module 01Phases of a Compiler: Analysis vs Synthesis⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The International Publishing House

Imagine translating an ancient Sanskrit legal manuscript into modern Japanese engineering specifications:

1. The Analytical Linguist (Front-End / Analysis):
   • Reads the raw characters and groups them into meaningful words (Lexical Analysis).
   • Verifies grammatical sentence structure (Syntax Analysis).
   • Checks the legal and contextual sanity of clauses (Semantic Analysis).
   • Condenses the text into a neutral, unambiguous intermediate outline (Intermediate Code Generation).
2. The Target Fabricator (Back-End / Synthesis):
   • Eliminates redundant clauses and streamlines sentence flow for conciseness (Code Optimization).
   • Translates the streamlined outline into idiomatic modern Japanese utilizing available technical terminology and page formatting (Target Code Generation).

💻 Bridging to Computer Science: Analysis vs Synthesis Architecture

This two-part division is the cornerstone of modern compiler design: The Front-End understands the source language, while the Back-End understands the target silicon. By inserting a machine-independent Intermediate Representation (IR) between them, we decouple language semantics from hardware constraints, enabling the legendary $M + N$ compiler scalability.

📑Table of Contents

• 🏗️ The 6 Canonical Compiler Phases Pipeline
• 📐 Formal Mathematical & Architectural Foundations
  • 🔍 Phase 1: Lexical Analysis (Scanner)
  • 🌲 Phase 2: Syntax Analysis (Parser)
  • 🎯 Phase 3: Semantic Analysis (Type Checker)
  • 🔄 Phase 4: Intermediate Code Generation (ICG)
  • ⚡ Phase 5: Machine-Independent Code Optimization
  • 💾 Phase 6: Target Code Generation
• ⚙️ Concrete Step-by-Step Execution Trace
• 🏛️ Front-End vs Back-End: The Retargetability Invariant
  • The M × N vs M + N Scalability Law
• 🔄 Passes vs Phases & Cross-Compilers
  • Passes vs Phases
  • Cross-Compilers & T-Diagrams
• 🛠️ Compiler Construction Tools
• 🏭 Real-World Production Context:
• 📐 Numerical Applications & Worked Examples
  • Example 1: Compiler Phase Error Classification
  • Example 2: T-Diagram Cross-Compiler Bootstrapping
• 🎯 Exam & Interview Pitfall Check

---

🏗️ The 6 Canonical Compiler Phases Pipeline

Every production compiler processes source text across six sequential phases:

Architecture Flow

The 6 Canonical Compiler Phases Pipeline

Decoupling Front-End (Analysis) from Back-End (Synthesis) via Intermediate Representation

📥Front-End

Analysis Phase (Source-Language Dependent)

🔍Phase 1

Lexical Analyzer

Scans characters into tokens; strips comments and whitespace.

→

Token Stream

🌲Phase 2

Syntax Analyzer

Constructs hierarchical parse tree verifying grammar rules.

→

Parse Tree / AST

🎯Phase 3

Semantic Analyzer

Enforces static type checking, scope rules, and array bounds.

→

Decorated AST

🔄Phase 4

Intermediate Code Gen

Generates linear machine-independent three-address code (TAC).

↓Intermediate Representation (IR)

📤Back-End

Synthesis Phase (Target-Hardware Dependent)

⚡Phase 5

Code Optimizer

Eliminates dead code, folds constants, and optimizes loop invariants.

→

Optimized TAC

💾Phase 6

Target Code Generator

Allocates registers and generates target assembly or machine opcodes.

---

📐 Formal Mathematical & Architectural Foundations

A compiler can be formally specified as a composition of mathematical mapping functions operating across intermediate abstract domains:

$$\mathcal{C} = \mathcal{G}_{\text{target}} \circ \mathcal{O}_{\text{opt}} \circ \mathcal{I}_{\text{IR}} \circ \mathcal{S}_{\text{sem}} \circ \mathcal{P}_{\text{syn}} \circ \mathcal{L}_{\text{lex}}$$

🔍 Phase 1: Lexical Analysis (Scanner)

Transforms a continuous stream of source characters $\Sigma^*$ into a stream of structured tokens:

$$\mathcal{L} : \Sigma^* \to \mathcal{T}^* \quad \text{where } \tau \in \mathcal{T} = \langle \text{TokenType}, \text{AttributeValue} \rangle$$

Operates via Deterministic Finite Automata (DFA) derived from regular expressions. Strips redundant whitespace and comments.

🌲 Phase 2: Syntax Analysis (Parser)

Verifies whether the sequence of tokens forms a valid sentence generated by a Context-Free Grammar $G = (V, \Sigma, P, S)$:

$$\mathcal{P} : \mathcal{T}^* \to \text{ParseTree} \quad \text{such that } S \Rightarrow^* w$$

Detects grammatical syntax violations such as mismatched parentheses or missing delimiters. Emits an Abstract Syntax Tree (AST).

🎯 Phase 3: Semantic Analysis (Type Checker)

Decorates the AST with type attributes and validates contextual invariants that Context-Free Grammars cannot express:

$$\mathcal{S} : \text{AST} \to \text{DecoratedAST}$$

Validations include:

• Type Checking: Ensuring operand types match operator domain requirements (e.g., float $\times$ float).
• Type Coercion: Inserting implicit type-cast nodes (e.g., int_to_float).
• Scope Checking: Ensuring identifiers are declared before use.

🔄 Phase 4: Intermediate Code Generation (ICG)

Constructs a low-level, machine-independent representation of the program:

$$\mathcal{I} : \text{DecoratedAST} \to \text{TAC}$$

Typically realized as Three-Address Code (TAC), where each instruction has at most one operator and three operands:

$$x = y \text{ op } z$$

⚡ Phase 5: Machine-Independent Code Optimization

Transforms the intermediate representation to improve time complexity, decrease binary size, and minimize energy consumption without altering program semantics:

$$\mathcal{O} : \text{TAC} \to \text{TAC}_{\text{opt}} \quad \text{such that } \text{Semantics}(\text{TAC}_{\text{opt}}) \equiv \text{Semantics}(\text{TAC})$$

Applies constant propagation, dead-code elimination, common subexpression elimination, and loop-invariant hoisting.

💾 Phase 6: Target Code Generation

Maps the optimized intermediate representation into machine-specific assembly mnemonics or binary opcodes:

$$\mathcal{G} : \text{TAC}_{\text{opt}} \to \text{Assembly}_{\text{arch}}$$

Solves two computationally hard problems:

• Instruction Selection: Choosing optimal machine opcodes.
• Register Allocation: Mapping an unbounded set of symbolic variables into a small, fixed set of $K$ physical CPU registers (NP-complete, solved via Graph Coloring heuristics).

---

⚙️ Concrete Step-by-Step Execution Trace

Let us trace the famous canonical expression through all six phases:

$$\text{position} = \text{initial} + \text{rate} \times 60$$

Execution Trace: position = initial + rate * 60 Across Compiler Phases

End-to-end transformation of the canonical expression from raw source text to x86-64 assembly

Source Text

Lexical Analyzer

Syntax Analyzer

Semantic Analyzer

Intermediate Code Gen

Code Optimizer

Target Code Gen

1

Source Text→Lexical Analyzer

Character Scanning & Tokenization

2

Lexical Analyzer→Syntax Analyzer

Hierarchical Parse Tree Construction

3

Syntax Analyzer→Semantic Analyzer

Static Type Checking & Type Coercion

4

Semantic Analyzer→Intermediate Code Gen

Linear Three-Address Code (TAC) Generation

5

Intermediate Code Gen→Code Optimizer

Constant Folding & Temporary Pruning

6

Code Optimizer→Target Code Gen

Register Allocation & x86-64 Assembly Emission

---

🏛️ Front-End vs Back-End: The Retargetability Invariant

Why are compilers decomposed into Front-End and Back-End?

Front-End vs Back-End Architecture

The M + N modularity advantage over M × N monolithic compilers

Source-Dependent

Compiler Front-End (Analysis)

📥

Dominant Architecture / DomainLexical, Syntax, Semantic Analysis, Intermediate Code Gen

• •Completely dependent on the source language specification (C, Rust, Go).
• •Completely independent of the target CPU architecture.
• •Produces machine-independent Intermediate Representation (IR).
• •Encapsulates language grammar rules, syntax error diagnostics, and AST creation.

"Changing the source language requires writing only one new front-end."

Target-Dependent

Compiler Back-End (Synthesis)

📤

Dominant Architecture / DomainCode Optimization, Register Allocation, Instruction Scheduling

• •Completely dependent on target CPU instruction set (x86, ARM64, RISC-V).
• •Completely independent of the source language.
• •Consumes machine-independent Intermediate Representation (IR).
• •Performs peephole tuning, register assignment, and pipeline hazard avoidance.

"Targeting a new CPU architecture requires writing only one new back-end."

The M × N vs M + N Scalability Law

Suppose we wish to support $M$ different programming languages (e.g., C, C++, Rust, Fortran) across $N$ distinct hardware architectures (e.g., x86-64, ARM64, RISC-V, WebAssembly):

• Monolithic Compilers: Require building $M \times N$ completely separate monolithic compilers.
• IR-Decoupled Compilers (e.g., LLVM): Require building only $M$ front-ends and $N$ back-ends, yielding an engineering complexity of:

$$\text{Compilers Needed} = M + N \ll M \times N$$

---

🔄 Passes vs Phases & Cross-Compilers

Passes vs Phases

• Phase: A logical stage in the translation process (e.g., Lexical, Semantic).
• Pass: A complete traversal of the source program or intermediate representation stored on disk or in memory.
  • Single-Pass Compiler: Interweaves lexical, syntax, semantic analysis, and target code generation in one pass. Faster compilation, small memory footprint, but cannot perform aggressive whole-program optimizations. Requires forward declarations for symbols.
  • Multi-Pass Compiler: Traverses the program representation multiple times. Enables global optimizations, loop transformations, and register allocation across whole functions.

Cross-Compilers & T-Diagrams

A native compiler runs on machine $H$ and produces code for machine $H$.
A cross-compiler runs on host machine $H$ and produces executable machine code for target machine $T$ ($H \neq T$).

In compiler literature, a compiler is formalized using a T-Diagram:

$$\begin{bmatrix} \text{Source } S & & \text{Target } T \\ & \text{Implementation } I & \end{bmatrix}$$

Meaning: A compiler written in language $I$ that translates programs written in source language $S$ into target language $T$.

Rule of T-Diagram Combination:

Two compilers can be combined if the implementation language of the first matches the target language of the second:

$$\begin{bmatrix} S & & T \\ & I_1 & \end{bmatrix} + \begin{bmatrix} I_1 & & M_2 \\ & M_1 & \end{bmatrix} \implies \begin{bmatrix} S & & T \\ & M_2 & \end{bmatrix} \text{ (running on } M_1 \text{)}$$

---

🛠️ Compiler Construction Tools

Modern compilers are rarely written entirely by hand. Standard automated generators construct phases directly from declarative formal specifications:

The Modern Compiler Construction Toolkit

Specialized generator engines automating compiler phase construction

🔍

Scanner Generators

Phase 1: Lexical Analysis

• Takes regular expressions as input and produces high-speed DFA state-machine scanners in C/C++.
• Automatically handles buffering, line numbering, and token classifications.

Key Abstractions / Calls

LexFlexragel

🌲

Parser Generators

Phase 2: Syntax Analysis

• Consumes Context-Free Grammars written in BNF and emits LALR(1) or LL(k) pushdown automata parsers.
• Resolves shift/reduce ambiguities using precedence and associativity declarations.

Key Abstractions / Calls

YaccBisonANTLR

🎯

Syntax-Directed Translators

Phase 3: Semantic Analysis

• Associates semantic action code blocks with grammar productions.
• Evaluates attribute values across tree nodes to perform type checking.

Key Abstractions / Calls

ANTLR ActionsTreecc

⚡

Optimizer & Target Engines

Phases 4-6: Synthesis

• Modular SSA-based intermediate representation optimization pipeline.
• Pluggable target back-ends supporting instruction selection and register coloring.

Key Abstractions / Calls

LLVM (opt / llc)GCC GIMPLE

---

🏭 Real-World Production Context:

The modern gold standard of decoupled compiler architecture is LLVM (Low Level Virtual Machine):

• Front-Ends: clang (C/C++), rustc (Rust), and swiftc (Swift) compile diverse language grammars down into a standardized, strongly typed LLVM Intermediate Representation (LLVM IR).
• Middle-End (opt): Over 100 machine-independent transformation passes (dead code elimination, loop vectorization, constant folding) operate purely on LLVM IR.
• Back-End (llc): A single shared code generator translates LLVM IR into optimized machine assembly targeting x86-64, ARM64, RISC-V, and WebAssembly.

---

📐 Numerical Applications & Worked Examples

Example 1: Compiler Phase Error Classification

Classify each of the following programming errors into the exact earliest compiler phase responsible for detecting it:

1. int 2x = 50;
2. x = y + z$ (where $ is not an allowed character in the language)
3. if (a > b { return a; }
4. float y = "hello" * 3.14;
5. int x = 10 / 0; (in a static const expression context)
6. int arr[10]; int val = arr[20]; (at runtime)

Step-by-Step Solution:

1. int 2x = 50;:

   • The scanner encounters 2 followed by x. In standard identifier lexical rules, an identifier cannot start with a digit.
   • Detected in: Lexical Analysis.

2. x = y + z$:

   • The symbol $ does not belong to the alphabet $\Sigma$ of the language. The scanner cannot match any valid token pattern.
   • Detected in: Lexical Analysis.

3. if (a > b { return a; }:

   • The token stream is IF, LPAREN, ID, GT, ID, LBRACE. The grammar production for if expects a closing parenthesis RPAREN before the body block: $S \to \text{if } ( E ) \ S$.
   • Detected in: Syntax Analysis.

4. float y = "hello" * 3.14;:

   • Grammatically, Expr * Expr is syntactically valid. However, the multiplication operator $*$ is not defined between type string and type float.
   • Detected in: Semantic Analysis (Type Checking).

5. int x = 10 / 0; (Static Constant Folding):

   • Evaluated during compile-time constant folding.
   • Detected in: Semantic Analysis / Code Optimization.

6. int arr[10]; int val = arr[20];:

   • Non-constant or unchecked index access cannot be verified statically by standard parsers.
   • Detected in: Runtime / Operating System (Segmentation Fault).

---

Example 2: T-Diagram Cross-Compiler Bootstrapping

A research lab has:

• A computer architecture $A$ with a native C compiler: $\begin{bmatrix} C & & A \\ & A & \end{bmatrix}$.
• A new hardware architecture $B$ with zero software available.
• A C compiler written in C that targets architecture $B$: $\begin{bmatrix} C & & B \\ & C & \end{bmatrix}$.

Derive the exact sequence of compilation steps using T-diagram algebra to produce a native compiler running on $B$ that compiles C programs to $B$:

$$\text{Goal: } \begin{bmatrix} C & & B \\ & B & \end{bmatrix}$$

Step-by-Step Derivation:

Step 1: Produce a Cross-Compiler Running on $A$
Compile the source code of the B-targeting compiler ($\begin{bmatrix} C & & B \\ & C & \end{bmatrix}$) using the native compiler on $A$ ($\begin{bmatrix} C & & A \\ & A & \end{bmatrix}$):

$$\begin{bmatrix} C & & B \\ & C & \end{bmatrix} + \begin{bmatrix} C & & A \\ & A & \end{bmatrix} \implies \begin{bmatrix} C & & B \\ & A & \end{bmatrix}$$

We now have a cross-compiler that runs on host machine $A$ and produces binary code for target machine $B$.

Step 2: Produce the Native Compiler for $B$
Feed the source code of the B-targeting compiler ($\begin{bmatrix} C & & B \\ & C & \end{bmatrix}$) into the newly built cross-compiler ($\begin{bmatrix} C & & B \\ & A & \end{bmatrix}$):

$$\begin{bmatrix} C & & B \\ & C & \end{bmatrix} + \begin{bmatrix} C & & B \\ & A & \end{bmatrix} \implies \begin{bmatrix} C & & B \\ & B & \end{bmatrix}$$

The resulting binary runs natively on architecture $B$ and generates code for architecture $B$. We copy this binary to machine $B$. Bootstrapping complete.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is Code Optimization considered an optional phase in compilers? What invariant must the optimizer never violate?"
Key Focus Points:

• Semantic Equivalence Invariant: The optimizer can only transform code if $\text{Semantics}(\text{Code}_{\text{opt}}) \equiv \text{Semantics}(\text{Code})$. It must produce functionally identical output for all possible inputs.
• Optionality: A compiler must generate functionally correct machine code even at -O0 (zero optimizations). If turning off optimizations fixes a bug, the optimizer is defective!

Question 2: "Explain why Lexical and Syntax analysis cannot detect undeclared variables or type mismatches."
Key Focus Points:

• Context-Free Limits: Regular expressions (Scanner) and Context-Free Grammars (Parser) only verify lexical tokens and grammatical tree shape ($S \to ID = E$).
• Contextual Requirement: Checking whether an identifier exists in the symbol table or whether float * string is valid requires context-sensitive Semantic Analysis.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Is a compiler phase the same as a compiler pass?
Answer: No, they are fundamentally distinct. A phase is a logical step of transformation (e.g. Lexical, Syntax, Semantic, ICG, Optimization, Code Gen). A pass is a physical traversal of the AST or source file representation on disk or in RAM. Multiple phases can be combined into a single pass (e.g. in single-pass compilers).

Trap 2: Is the Symbol Table discarded once Lexical Analysis finishes?
Answer: No. The symbol table persists across the entire compilation pipeline. It is created during Lexical Analysis, decorated with types during Semantic Analysis, queried for memory offsets during ICG, and updated with physical register allocations during Target Code Generation.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic1.1 Language Processing SystemNext Topic →1.3 Symbol Table Management & Error Handling