PadhaikoAll subjects

Introduction

Compiler Design (ENCT 326)

Open in the Padhaiko app

1.1 Compiler and Interpreter

A programming language implementation translates human-readable source code into executable instructions that the underlying hardware or runtime environment can execute. The two foundational execution paradigms are compilation and interpretation.

Definition

Compiler

A compiler is a system software program that accepts an entire computer program written in a high-level source language (such as C, C++, or Rust) and translates it into an equivalent program written in a low-level target language (such as machine code or assembly language) in a single unified translation process before execution.

Definition

Interpreter

An interpreter is a language translator that directly executes the operations specified in a source program statement-by-statement or instruction-by-instruction, fetching, analyzing, and executing each construct without producing an intermediate standalone machine-code binary file.

AspectCompilerInterpreter
Input ProcessingTranslates the entire source program at once into object/machine codeTranslates and executes the program line by line (or instruction by instruction)
Execution SpeedFast execution; target machine code runs directly on hardware without translation overheadSlower execution; each statement is repeatedly decoded and interpreted at runtime
Memory RequirementGenerates standalone object files (.o, .exe); requires substantial memory during compilation, but runtime memory is leanRetains the interpreter and source/intermediate representation in memory during entire execution
Error ReportingCompiles all syntax and semantic errors into a comprehensive diagnostic report before executionHalts immediately at the first encountered error during execution
Code OptimizationExtensive global and local optimization passes are performed across basic blocks and loopsMinimal or no optimization because execution proceeds immediately upon parsing
PortabilityTarget code is specific to a target CPU architecture (e.g., x86_64, ARM64)Source code or bytecode is portable across any machine with the interpreter installed
Representative LanguagesC, C++, Rust, Fortran, GoPython, Ruby, PHP, JavaScript (classical), Perl

1.1.1 Hybrid Implementation and Just-In-Time (JIT) Compilers

Modern runtime environments combine both paradigms to balance portability with raw execution speed:

  1. Source-to-Bytecode Compilation: The source code is parsed and compiled into an architecturally neutral, compact intermediate bytecode format (e.g., .class files in Java, .pyc files in Python).
  2. Virtual Machine Interpretation: A virtual machine (e.g., Java Virtual Machine - JVM, Common Language Runtime - CLR) interprets bytecode instructions sequentially.
  3. Just-In-Time (JIT) Compilation: The runtime monitors execution frequencies ("hot spots" such as inner loops and heavily invoked methods) and dynamically compiles frequently executed bytecode segments into native machine code at runtime.
Diagram: Java execution pipelineText
Source Program (.java)
        |
        v
Bytecode Compiler (javac)
        |
        v
Bytecode (.class)
        |
        v
Virtual Machine (JVM)
   |                    |
   v                    v
Interpreter          JIT Compiler
(cold paths)         (hot paths)
   |                    |
   |                    v
   |             Native Machine Code
   |                    |
   v                    v
     Hardware Execution (CPU)

1.1.2 Cousins of the Compiler in the Language Processing System

A compiler operates as part of a larger pipeline called the language processing system:

Language Processing System Components
ComponentInput FormatOutput FormatPrimary Responsibility
PreprocessorRaw source code with directives (#include, #define)Pure high-level source codeMacro expansion, header file inclusion, conditional compilation, comment stripping
CompilerPreprocessed source codeAssembly language codeLexical, syntactic, semantic analysis, intermediate representation, and machine-target code generation
AssemblerAssembly code (mnemonics, e.g., MOV, ADD)Relocatable machine object code (.o, .obj)Resolves symbolic opcodes into binary instruction words and local addresses
LinkerMultiple relocatable object files and external librariesAbsolute executable binary file (.exe, ELF)Resolves external symbol references, merges data/code segments, assigns base addresses
LoaderExecutable file from secondary storageActive process memory space in RAMAllocates memory, initializes registers, sets up program stack/heap, branches CPU to entry point

1.2 Compiler structure: Analysis and synthesis model of compilation, different sub-phases within the analysis and synthesis phases

The architecture of a modern compiler is divided into two primary subsystems: the Analysis Phase (Front-End) and the Synthesis Phase (Back-End).

Diagram: phases of a compilerText
Source Program (character stream)
        |
        v
1. Lexical Analyzer (Scanner)
        | token stream
        v
2. Syntax Analyzer (Parser)
        | parse / syntax tree
        v
3. Semantic Analyzer
        | decorated AST
        v
4. Intermediate Code Generator
        | intermediate representation (IR)
        v
5. Code Optimizer
        | optimized IR
        v
6. Code Generator
        |
        v
Target Machine Code

Every phase 1-6 talks to both:
  - Symbol Table Management (two-way)
  - Error Handler (two-way)

1.2.1 Analysis Phase (Front-End)

The analysis phase inspects the source program to extract its structural grammatical form and detect errors, decomposing it into an intermediate representation. The front-end is largely independent of the target machine architecture.

  1. Lexical Analysis (Scanning):
    • Reads the input stream of raw characters from left to right.
    • Groups characters into meaningful sequences called lexemes.
    • Produces an output stream of tokens of the form ⟨token-name, attribute-value⟩.
    • Strips whitespace, tabs, and comments; stores identifier strings in the symbol table.
  2. Syntax Analysis (Parsing):
    • Imposes a hierarchical grammatical structure on the token stream using a context-free grammar (CFG).
    • Constructs a syntax tree (or parse tree) where interior nodes represent grammar operators/productions and leaf nodes represent operands/terminals.
    • Verifies syntactic correctness according to the language grammar (e.g., balancing parentheses, matching semicolons).
  3. Semantic Analysis:
    • Checks whether the parse tree conforms to language semantic rules (type consistency, scope rules, array bound validity).
    • Performs type checking and automatic type coercion (e.g., widening integer to floating-point).
    • Produces an annotated (decorated) syntax tree.

1.2.2 Synthesis Phase (Back-End)

The synthesis phase takes the intermediate representation and symbol table information produced by the analysis phase and constructs the desired target program.

  1. Intermediate Code Generation:
    • Translates the annotated syntax tree into an explicit, machine-independent, low-level intermediate representation (IR).
    • A universal representation is three-address code (TAC), where each instruction contains at most one operator and at most three operand addresses:
  1. Code Optimization:
    • Analyzes the intermediate representation to produce faster-executing or smaller code.
    • Machine-independent optimizations include common subexpression elimination, constant folding, dead-code elimination, and loop-invariant code motion.
  2. Code Generation:
    • Maps the optimized intermediate code onto the instruction set architecture (ISA) of the target machine.
    • Selects machine instructions, allocates and assigns CPU registers, and emits relocatable object code or assembly code.

1.2.3 Compiler Passes

Definition

Compiler Passes

A pass in a compiler refers to one complete traversal of the source program or its intermediate representation.


1.3 Basic concepts like preprocessor, macros, symbol table, and error handler

1.3.1 Preprocessors and Macro Processors

A preprocessor handles preliminary source transformations before the compiler parses the code:

1.3.2 Symbol Table Management

The symbol table is a central data repository maintained across all phases of compilation:

1.3.3 Error Detection and Handling

Every phase of compilation must detect, report, and recover from errors without abruptly crashing:

Compiler Errors and Recovery Strategies
Compilation PhaseTypical Error TypesCommon Recovery Strategies
Lexical AnalysisIllegal characters (e.g., @ in C), unterminated strings, misspelled keywordsPanic mode (discard invalid character), delete/insert characters, transpose characters
Syntax AnalysisMissing semicolons, unbalanced parentheses, unmatched elsePanic mode (discard tokens until synchronizing token like ; or }), phrase-level recovery, error productions
Semantic AnalysisType mismatches (assigning string to float), undeclared variables, multiple declarations in same scopeEmit diagnostic message, assign error type to expression to prevent cascading false alarms
Code GenerationExceeding available registers, displacement overflow, memory limit exceededSpill registers to activation record stack frames, fall back to indirect addressing

Worked Examples

Example 1

1

Trace the compilation of the following high-level language assignment statement through all six phases of a compiler:

Assume , , and are floating-point variables (-bit float), while is an integer literal. Detail the data structure or intermediate representation emitted at each phase.

Phase 1 — Lexical Analysis: The lexical analyzer scans the character stream and identifies lexemes, looking up or inserting identifiers in the symbol table. It produces the token stream:

Where symbol table entries are:

  • (float)
  • (float)
  • (float)

Phase 2 — Syntax Analysis: The syntax analyzer parses the token stream according to arithmetic operator precedence ( binds tighter than ) and constructs the syntax tree:

Phase 3 — Semantic Analysis: The semantic analyzer detects that is of type float, but is an integer. It inserts a type-conversion operator into the decorated syntax tree:

Phase 4 — Intermediate Code Generation: The intermediate code generator traverses the decorated tree and produces three-address code (TAC):

Phase 5 — Code Optimization: The optimizer analyzes the TAC, detects that can be computed at compile time (constant folding), and eliminates the redundant temporary :

Phase 6 — Code Generation: The code generator assigns machine registers (using ) and emits target assembly code:

Text
LDF   R2, id3      ; Load floating-point rate into R2
MULF  R2, #60.0    ; Multiply R2 by constant 60.0
LDF   R1, id2      ; Load floating-point initial into R1
ADDF  R1, R2       ; Add R2 to R1
STF   id1, R1      ; Store result from R1 into position
Answer:

The statement is converted into tokens, parsed into a hierarchical syntax tree respecting operator precedence, annotated with an explicit conversion, lowered into three-address code, optimized via constant folding () and temporary elimination, and finally emitted as target assembly instructions.

Example 2

2

A program consists of high-level instructions inside an iterative computational loop executed times.

  1. A pure interpreter requires per instruction to fetch, decode, and execute.
  2. An optimizing compiler requires an upfront compilation time of , but the generated native machine instructions execute at per instruction.

Calculate:

Interpreted Execution Time: The interpreter executes statements for each of the iterations. The total execution time is:

Compiled Execution Time: The compiler incurs a one-time compilation overhead , after which the target code runs for all iterations:

Breakeven Iteration Count : The compiler becomes faster than the interpreter when :

Solving for :

Answer:
  • Interpreter total time: .
  • Compiler total time: .
  • Breakeven loop iterations: iterations (compiler is already faster for iterations).
Example 3

3

Consider the arithmetic assignment expression:

  1. Construct the parse tree and abstract syntax tree (AST).
  2. Generate three-address code (TAC) without optimization.
  3. Apply common subexpression elimination to produce the optimized TAC and state the minimum number of temporaries needed.

Constructing the Syntax Tree and AST: In the parse tree, every grammar rule production is expanded. In the compact Abstract Syntax Tree (AST), the interior nodes are operators and leaves are identifiers:

  • Node
  • Node
  • Node
  • Node
  • Root
  • Assignment:

Notice that the subexpression appears twice in the tree structure.

Unoptimized Three-Address Code: Evaluating each operation sequentially into distinct temporary registers:

This requires temporary variables () and TAC instructions.

Common Subexpression Elimination & Register Reuse: The expression is evaluated in . Since neither nor is modified, is an identical subexpression that can be replaced by :

Answer:

Unoptimized TAC requires temporaries and instructions. Optimized TAC detects the common subexpression and reduces the sequence to instructions: ; ; ; , requiring only temporary variables.


Exercises

Practice Exercises — Introduction to Compiler Design

Question 1

Explain why modern computer architectures require compilers rather than directly executing high-level language source text. Contrast the error detection capabilities and diagnostic feedback between compilers and interpreters.

Need for Compilers: Digital computer processors (CPUs) operate strictly on binary machine instructions represented as opcode-operand sequences dictated by their Instruction Set Architecture (ISA). High-level programming languages offer abstraction (data typing, object modeling, structured control flow) that humans can comprehend, but hardware cannot natively decode. Compilers bridge this semantic gap by systematically lowering abstractions into optimized machine words.

Diagnostic and Error Detection Differences:

  • Compilers: Scan the entire program statically during compilation. Because the whole translation unit is available, the compiler performs global syntax validation and semantic type inference, exposing all syntactic mistakes, undefined references, and type contradictions in a single diagnostic report before any code executes.
  • Interpreters: Analyze and validate constructs on the fly. An interpreter cannot detect an error located on line 500 of a program until runtime control flow reaches that line. This makes debugging latent branch errors harder, although it enables dynamic interactive testing (REPL).
Answer:

Compilers bridge the semantic gap between high-level human abstractions and raw CPU hardware instruction sets. Compilers perform comprehensive global static checking before execution, whereas interpreters only expose syntax and semantic errors dynamically when execution control reaches the erroneous statement.

Question 2

Describe the analysis-synthesis model of compilation. Clearly differentiate between the responsibilities of the front-end and the back-end, and explain why separating them simplifies retargeting a compiler to multiple hardware platforms.

Analysis-Synthesis Model: The compilation process is partitioned into:

  1. Analysis (Front-End): Consists of Lexical, Syntax, and Semantic analysis. It analyzes the source text to ensure validity and translates it into an intermediate representation (IR) while maintaining the symbol table. It is source-language dependent and target-machine independent.
  2. Synthesis (Back-End): Consists of Intermediate Code Optimization and Target Code Generation. It takes the IR and transforms it into efficient machine code for the target processor. It is target-machine dependent.

Benefits for Portability and Retargeting: If a compiler family supports high-level source languages (e.g., C, Fortran, Ada) and target computer architectures (e.g., x86, ARM, RISC-V), a monolithic compiler would require distinct translation systems. By decoupling the front-end from the back-end via a standardized Intermediate Representation (IR):

  • Only front-ends are built (one per source language).
  • Only back-ends are built (one per target architecture).

The total development effort drops from to .

Answer:

The front-end performs language-dependent analysis to produce a machine-independent intermediate representation (IR), while the back-end performs target-dependent synthesis into machine code. Decoupling them through an IR reduces the complexity of supporting languages across architectures from to .

Question 3

What is a symbol table? Explain its operational role in each phase of a compiler, and explain why a hash table is the preferred data structure for implementing it.

Symbol Table Role Across Phases: The symbol table stores identifier names alongside attributes such as type, size, scope, and relative storage offset:

  • Lexical Analyzer: Enters identifier strings (lexemes) and returns token pointers.
  • Syntax Analyzer: Adds grammatical attributes and verifies scope boundaries.
  • Semantic Analyzer: Verifies identifier declarations, enforces type rules, and checks parameter matching in function calls.
  • Intermediate Code Generator & Optimizer: Resolves identifier sizes and memory offsets to generate three-address temporary addresses.
  • Code Generator: Maps symbolic identifiers to real machine memory addresses or register bindings.

Why Hash Tables Are Preferred: Compilers frequently query the symbol table—every identifier occurrence in the source program triggers a lookup(), and every declaration triggers an insert().

  • Linear lists incur search time, which causes compiler execution time to scale quadratically with program size ().
  • Balanced binary search trees require time per query.
  • Hash tables with separate chaining provide expected time for both insertion and lookup, allowing large programs with tens of thousands of identifiers to compile linearly in time.
Answer:

The symbol table is a centralized dictionary storing identifier metadata used by all compiler phases to enforce scoping, check types, and calculate memory offsets. Hash tables are preferred because their expected lookup and insertion times prevent compiler slowdown on large programs.

Question 4

A software module containing lines of code is benchmarked under two build and execution strategies:

  1. Multi-Pass Compiled Pipeline:
    • Pass 1 (Lexical/Syntax analysis): per line.
    • Pass 2 (Semantic analysis/IR): per line.
    • Pass 3 (Optimization & Code Gen): per line.
    • Runtime execution of the compiled binary: per run.
  2. Direct Bytecode Interpretive Engine:
    • Translation overhead: per line per execution run.
    • Bytecode execution time: per run.

Calculate:

Total Compilation Time: Total compilation time per line:

For lines:

Total Elapsed Time for Runs:

  • Compiled System: Compiles once upfront, then executes times:
  • Interpreted System: Translates and executes on every run:

For runs:

Threshold Execution Runs : The compiled pipeline is faster when :

Answer:
  • Total compilation time: .
  • For runs: Compiled pipeline takes , while interpreter takes .
  • Breakeven threshold: runs (compiled is faster for or more runs).
Question 5

Explain the roles of the preprocessor, assembler, linker, and loader in the context of the complete language processing ecosystem. Highlight the fundamental distinction between static and dynamic linking.

Roles in the Language Processing System:

  1. Preprocessor: Operates on raw source files before compilation. Handles macro expansion (#define), file inclusion (#include), and conditional compilation (#ifdef), generating pure source code.
  2. Assembler: Translates the compiler's output assembly mnemonics into relocatable machine object modules (.o or .obj), replacing symbolic opcodes with binary bit patterns.
  3. Linker: Combines independently compiled object files and precompiled library routines. It resolves external cross-module references and builds an executable binary.
  4. Loader: Coordinates with the OS kernel to load the executable into primary memory (RAM), setting up virtual memory pages, initialization stacks, and passing CPU control to main().

Static vs. Dynamic Linking:

  • Static Linking: The linker copies all required library functions directly into the final executable binary at link time. The resulting executable is self-contained and larger in size, but has no runtime dependency on external library files.
  • Dynamic Linking: The linker places stub symbols and import tables in the executable rather than copying code. The actual library code (.so on Linux, .dll on Windows) is loaded into memory only when the program is launched or invoked at runtime, enabling memory sharing across multiple processes and simple library updates.
Answer:

The preprocessor expands macros and headers; the assembler generates relocatable binary object files; the linker combines object modules and resolves external references; the loader mounts the executable into RAM. Static linking binds all library code into the executable at build time, while dynamic linking resolves library routines at runtime, saving disk space and memory.

Lexical Analysis (part 1: 2.1–2.3) →