COMPILER DESIGN / OVERVIEW

Compiler Design — The Full Map

How source code becomes machine code — every phase from characters to instructions

EXPLANATION

A compiler is a program that translates source code written in one language (source) into another language (target), usually machine code or bytecode. Understanding compilers means understanding exactly what happens to your code between the moment you write it and the moment the CPU executes it.

Why study compilers?
- You write better code — understanding what the compiler does helps you write code it can optimize
- You understand error messages — "unexpected token", "type mismatch", "undefined reference" all come from specific compiler phases
- You can build your own DSLs (Domain Specific Languages)
- It connects TOC (grammars, automata) to real systems (parsers, type checkers)
- Directly tested in GATE

The compilation pipeline — six phases:

① Lexical Analysis (Scanning)
Source text → stream of tokens. "int x = 5 + 3;" → [INT, ID(x), ASSIGN, NUM(5), PLUS, NUM(3), SEMI]
Tool: Finite Automaton (your DFA/NFA knowledge applies here!)

② Syntax Analysis (Parsing)
Token stream → Abstract Syntax Tree (AST). Checks grammatical structure.
Tool: Context-Free Grammar + parser (LL, LR). Your CFG knowledge applies here!

③ Semantic Analysis
AST → annotated AST. Type checking, scope resolution, variable declarations.
"Are you adding an int and a string? Is this variable declared?"

④ Intermediate Code Generation
AST → Three-Address Code (TAC) or IR (LLVM IR). Language-independent, easy to optimize.

⑤ Optimization
IR → optimized IR. Dead code elimination, constant folding, loop unrolling, inlining.
"This x = 2+3 → x = 5 at compile time"

⑥ Code Generation
Optimized IR → target machine code. Register allocation, instruction selection, instruction scheduling.

Interpreter vs Compiler:
- Compiler: translates whole program first, then runs. (C, C++, Rust, Go)
- Interpreter: translates and runs line by line. (Python, Ruby)
- JIT (Just-In-Time): hybrid — interprets first, compiles hot paths at runtime. (Java JVM, V8 for JS, PyPy)

Python specifically: your .py file → CPython compiles to bytecode (.pyc) → CPython VM interprets bytecode. Python is compiled AND interpreted!

DIAGRAM

SOURCE CODE: int result = 2 + 3 * x;

  ┌─────────────────────────────────────────────────────┐
  │  Phase 1: LEXICAL ANALYSIS (Scanner)                │
  │  int result = 2 + 3 * x ;                           │
  │  [INT][ID:result][=][NUM:2][+][NUM:3][*][ID:x][;]   │
  └──────────────────────┬──────────────────────────────┘
                         ↓
  ┌─────────────────────────────────────────────────────┐
  │  Phase 2: SYNTAX ANALYSIS (Parser) → AST            │
  │         ASSIGN                                      │
  │        /                                           │
  │    result      +                                    │
  │               /                                    │
  │              2   *                                  │
  │                 /                                  │
  │                3   x                                │
  └──────────────────────┬──────────────────────────────┘
                         ↓
  ┌─────────────────────────────────────────────────────┐
  │  Phase 3: SEMANTIC ANALYSIS                         │
  │  Check: result declared? x declared? types match?   │
  └──────────────────────┬──────────────────────────────┘
                         ↓
  ┌─────────────────────────────────────────────────────┐
  │  Phase 4: IR GENERATION (Three-Address Code)        │
  │  t1 = 3 * x                                         │
  │  t2 = 2 + t1                                        │
  │  result = t2                                        │
  └──────────────────────┬──────────────────────────────┘
                         ↓
  ┌─────────────────────────────────────────────────────┐
  │  Phase 5: OPTIMIZATION                              │
  │  (if x is constant 4: t1=12, t2=14, result=14)      │
  └──────────────────────┬──────────────────────────────┘
                         ↓
  ┌─────────────────────────────────────────────────────┐
  │  Phase 6: CODE GENERATION                           │
  │  MOV R1, [x]    ; load x                            │
  │  IMUL R1, 3     ; R1 = 3*x                          │
  │  ADD R1, 2      ; R1 = 2 + 3*x                      │
  │  MOV [result], R1                                   │
  └─────────────────────────────────────────────────────┘

CODE

PYTHON

1# See Python's compiler in action!
2import ast
3import dis
4import py_compile
5import sys
6
7source = """
8def add(a, b):
9    result = a + b
10    return result
11
12x = add(2, 3)
13print(x)
14"""
15
16# ── Phase 2: AST (Python exposes its own AST) ─────────
17print("=== Python AST ===")
18tree = ast.parse(source)
19print(ast.dump(tree, indent=2)[:800])
20
21# ── Phase 6: Bytecode (Python's "machine code") ───────
22print("
23=== Python Bytecode (dis) ===")
24code = compile(source, "<string>", "exec")
25dis.dis(code)
26
27# ── See .pyc file (compiled bytecode on disk) ─────────
28import tempfile, os
29with tempfile.NamedTemporaryFile(suffix=".py", delete=False, mode="w") as f:
30    f.write(source)
31    fname = f.name
32
33py_compile.compile(fname)
34print(f"
35Compiled to .pyc: {fname}c")
36print(f"Python version: {sys.version}")
37print(f"
38Key insight: Python IS compiled — just to bytecode, not machine code")
39print(f"CPython VM then interprets that bytecode")
40
41os.unlink(fname)

NEXT →1. Lexical Analysis