Compiler Design (CS-603) - Unit 1 Short Notes

UNIT 1: COMPILER DESIGN

I. INTRODUCTION TO COMPILERS

Definition and Role

A compiler is a translator that converts source code written in a high-level language (source language) into an equivalent target language (often machine code or assembly). It performs analysis (breaking down the source) and synthesis (building the target).

[!TIP]

Translator is the broader term encompassing compilers, interpreters, assemblers, and preprocessors.

Compiler vs Interpreter

Phases of a Compiler (with Example)

Consider source statement: id1 = id2 + id3 * 50

Diagram:

DiagramSEARCH: compiler phases diagram with data flow

Compiler Structure Models

Frontend and Backend

• Frontend: Language-dependent (lexical, syntax, semantic analysis, IR generation). Output: IR.

• Backend: Target-dependent (optimization, code generation). Output: target code.

• Advantages: Modularity, retargetability (same frontend for multiple backends), reuse.

• Disadvantages: Overhead of IR, may miss cross-phase optimizations.

Single-pass vs Multi-pass

Compiler Construction Tools

• LEX/Flex: Generates lexical analyzers from regex patterns.

  • Structure: Definitions %% Rules %% User Subroutines

• YACC/Bison: Generates parsers (LALR) from CFG.

• Other: ANTLR (LL(*)), JavaCC.

Pre-processing

Handles macro expansion, file inclusion (#include), conditional compilation (#ifdef). Occurs before compilation. Output: pure source code.

Input Buffering

Technique to reduce I/O overhead during lexical analysis.

• Double Buffering: Two buffers, alternate between them.

• Sentinel Character: Special end-of-buffer marker to avoid boundary checks.

• Lookahead: Needed for token recognition (e.g., >= vs >).

II. LEXICAL ANALYSIS

Role and Responsibilities

• Read source characters, group into lexemes.

• Identify tokens (keyword, identifier, operator, etc.).

• Remove whitespace/comments.

• Handle lexical errors (invalid characters).

• Interact with symbol table (insert identifiers).

Tokens, Patterns, Lexemes

• Token: Category (e.g., id, num, +).

• Pattern: Rule describing lexemes (regex for id: [a-zA-Z][a-zA-Z0-9]*).

• Lexeme: Actual character sequence (e.g., count is a lexeme for token id).

Specification of Tokens using Regular Expressions

• Example: Even number of as: (aa)*

• Operators: +, -, *, / → regex: [\+\-\*\/]

• Identifiers: [a-zA-Z_][a-zA-Z0-9_]*

• Numbers: [0-9]+(\.[0-9]*)?

Finite Automata for Token Recognition

• NFA: Multiple transitions on same input, ε-transitions.

• DFA: Single transition per input, no ε. Efficient for implementation.

• Conversion: Regex → NFA (Thompson’s construction) → DFA (subset construction) → Minimized DFA.

Example: Regex for id → NFA → DFA with states for start, letter, digit, etc.

Lexical Errors and Handling

• Invalid character (e.g., @ in C).

• Unterminated comment/string.

• Strategy: Panic mode (skip until valid token), error token, repair (insert/delete).

LEX Tool

Structure:

%{

  // Declarations (C code)

%}

%%

  // Rules: pattern { action }

%%

  // User subroutines

Example: Recognize identifiers and numbers:

%%

[a-zA-Z_][a-zA-Z0-9_]* { printf("ID: %s\n", yytext); return ID; }

[0-9]+ { printf("NUM: %s\n", yytext); return NUM; }

"+" { return PLUS; }

%%

Recognition of Identifiers and Keywords

• Keywords (e.g., if, while) are fixed strings. Lexical analyzer checks if lexeme matches keyword pattern → return keyword token; else identifier.

• Implementation: Keyword table (hash/array) checked after identifier pattern match.

Implementation Limitations of FSM

• Cannot count (e.g., balanced parentheses) → need context-free grammar (syntax analysis).

• Cannot handle nested structures (e.g., { ... { ... } ... }).

III. SYNTAX ANALYSIS (PARSING)

Role

• Check if token stream conforms to grammar.

• Build parse tree (or syntax tree).

• Detect syntax errors, recover.

Context-Free Grammars (CFG)

• Components: Terminals (tokens), Non-terminals, Productions, Start symbol.

• Derivation: Leftmost/rightmost replacement.

• Parse Tree: Graphical representation of derivation.

• Ambiguity: String has >1 parse tree (e.g., if-else dangling).

• Left Recursion: A → Aα causes infinite loop in top-down parsers. Eliminate by rewriting:

  
  A → Aα | β  becomes  A → βA', A' → αA' | ε
  
  

• Left Factoring: Remove common prefixes:

  
  A → αβ1 | αβ2  becomes  A → αA', A' → β1 | β2
  
  

Parsing Techniques

Top-down Parsing

• Start with start symbol, apply productions to match input.

• Recursive Descent: Non-recursive procedure per non-terminal. May require backtracking.

• Predictive Parsing: No backtracking, uses LL(1) grammar.

  • LL(1) Properties:

    1. Grammar is non-left-recursive, left-factored.

    2. For any two productions A → α | β, FIRST(α) ∩ FIRST(β) = ∅.

    3. If ε ∈ FIRST(α), then FIRST(β) ∩ FOLLOW(A) = ∅.

  • FIRST Set: Set of terminals that begin strings derived from non-terminal.

  • FOLLOW Set: Set of terminals that appear immediately after non-terminal in sentential forms.

  • Example: For S → aABb | A e, compute FIRST/FOLLOW.

Bottom-up Parsing

• Start with input tokens, reduce to start symbol.

• Shift-reduce: Shift tokens onto stack, reduce when handle found.

• LR Parsing: Most powerful (LR(1) handles all deterministic CFLs).

  • LR(0) Items: Production with dot at some position, e.g., S → L = R •.

  • Canonical Collection: Set of LR(0) items via closure and goto.

  • Parsing Tables: ACTION (shift/reduce/accept/error) and GOTO.

  • Types:

    • LR(0): No lookahead, limited.

    • SLR(1): Uses FOLLOW for reductions → less powerful than LR(1).

    • LALR(1): Merges LR(1) states with same core → common in practice (YACC/Bison).

    • LR(1): Full lookahead, largest class.

Differences:

SLR: May have conflicts not in LALR/LR(1).

LALR: Smaller tables than LR(1), same power for many grammars.

LR(1): Largest tables, most powerful.

Parsing Table Construction (SLR Example)

Grammar:

E → E + T | T

T → T * F | F

F → (E) | id

Steps:

1. Augment: E' → E.

2. Compute LR(0) items, closure, goto.

3. Build ACTION/GOTO using FOLLOW(E) for reductions.

4. Resolve conflicts (if any).

Error Recovery in Parsing

• Panic mode: Skip tokens until synchronizing token (e.g., ;).

• Phrase level: Insert/delete tokens to recover (e.g., missing ;).

• Error productions: Add productions for common errors.

• Global correction: Minimum edits (dynamic programming, expensive).

IV. SEMANTIC ANALYSIS

Role

• Ensure program meaning is consistent.

• Type checking, type conversion.

• Enforce language rules (e.g., break only in loops).

• Build symbol table with scope info.

Syntax-Directed Definitions (SDD) and Translations (SDT)

• SDD: CFG + semantic rules (attributes) on productions.

• SDT: SDD with semantic actions embedded in grammar.

• Annotated Parse Tree: Parse tree with attribute values at nodes.

• Dependency Graph: Nodes = attribute instances, edges = dependencies. Cycle → semantic error.

Attributes

• Synthesized: Computed from children’s attributes (bottom-up). Example: E.value = E1.value + T.value.

• Inherited: Computed from parent/siblings (top-down). Example: S → if (E) S1 else S2, pass E.true to S1 and E.false to S2.

Example: L-attributed definition allows inherited attributes from left siblings only → suitable for top-down evaluation.

Type Checking

• Type Systems: Set of rules assigning types to expressions.

• Type Expressions: Built from base types (int, real) with constructors (array, function).

• Type Equivalence:

  • Name equivalence: Two types same if declared with same name (e.g., typedef).

  • Structural equivalence: Same structure (e.g., array[10] of int vs array[10] of int).

• Type Conversion:

  • Implicit: Automatic (e.g., int → float in C).

  • Explicit: Cast (e.g., (float) x).

• Type Checking Algorithm: Walk AST, verify operator/operand types, apply conversion rules.

Symbol Table Management

• Organization: Scope-based (global, function, block). Nested scopes → stack of tables.

• Data Structures:

  • Hash Table: Fast lookup, collisions handled.

  • Binary Search Tree: Ordered, slower.

  • Linked List: Simple, slow.

• Entries: Name, type, scope, line number, size, address, etc.

Semantic Errors

• Type mismatch (e.g., int + string).

• Undeclared variable.

• Multiple declarations.

• Incompatible operand types (e.g., array assigned to scalar).

Overloading of Functions

• Same name, different parameter types/numbers.

• Resolution: Based on argument types at call site.

• Example: print(int), print(string).

Polymorphic Functions

• Functions that work with multiple types (e.g., generic max<T> in Java).

• Implementation: Type parameters, type erasure, or dynamic dispatch.

V. INTERMEDIATE CODE GENERATION

Need for IR

• Machine-independent, easier optimization.

• Bridges frontend and backend.

Forms of Intermediate Code

Quadruples vs Triples:

• Quadruples: Easy optimization (renaming result), but extra field.

• Triples: No extra field, but harder to optimize (need to track references).

• Indirect triples: Combine benefits (use index array).

Generation of TAC

Expressions

• Arithmetic: a + b * c → t1 = b * c; t2 = a + t1

• Logical: a && b → t1 = a; if t1 goto L1; t2 = false; goto L2; L1: t2 = b; L2:

Flow Control

• If: if (a < b) S → if a < b goto S1; goto L1; S1: S; L1:

• If-else: if (a) S1 else S2 → if a goto L1; S2; goto L2; L1: S1; L2:

• While: while (a) S → L1: if a goto L2; goto L3; L2: S; goto L1; L3:

• For: for (i=0; i<n; i++) S → i=0; L1: if i<n goto L2; goto L3; L2: S; i=i+1; goto L1; L3:

• Switch: See Special Topics.

Backpatching

• Used for boolean expressions and jumps where target addresses unknown until later.

• Boolean Expressions: Generate TAC with jumps to true/false lists.

  • Example: a && b → t1 = a; if t1 goto L1; false; L1: t2 = b; if t2 goto true; goto false;

  • Backpatch: Fill true/false lists when target known.

• Flow-of-control: For if/while, maintain lists of pending jumps.

  • Algorithm: makelist(i), merge(p1,p2), backpatch(p, target).

Directed Acyclic Graphs (DAGs)

• Definition: DAG for expressions where common subexpressions share nodes.

• Construction:

  1. For each identifier/constant, create leaf node.

  2. For operation op, check if node (op, left, right) exists → reuse; else create.

  3. Update hash table (node → value).

• Example:

  T1 = A + B; T2 = C + D; T3 = E - T2; T4 = T1 - T3

  DAG: + nodes for (A,B) and (C,D), - nodes reuse T2 and T1.

• Applications: Common subexpression elimination, constant folding, dead code elimination.

Flow Graphs

• Definition: Graph where nodes = basic blocks (maximal straight-line code), edges = flow of control.

• Construction:

  1. Identify leaders: First instruction, target of jump, instruction after jump.

  2. Basic block = leader to next leader-1.

  3. Edges: Fall-through (next block), jump (target block).

• Basic Block Characteristics:

  • Single entry, single exit.

  • No jumps inside except at end.

  • Used for local optimization.

Partitioning into Basic Blocks

1. Determine leaders.

2. For each leader, block starts at leader, ends before next leader.

3. Add edges between blocks.

VI. RUNTIME ENVIRONMENT

Storage Organization

• Static Allocation: Global/static variables, fixed addresses (e.g., FORTRAN).

• Stack Allocation: Activation records for procedures (local vars, parameters, return address). Used for recursive procedures.

• Heap Allocation: Dynamic memory (malloc, new). Garbage collection needed.

Activation Record (AR) Model

Typical layout (grows downward):

|-----------------|
| Actual params   |  (caller pushes)

| Return address  |
| Control link     |  (pointer to caller’s AR)

| Access link      |  (for nested scopes)

| Saved registers  |
| Local variables  |
| Temporary vars   |
|-----------------|

• Calls: Caller pushes params, jumps to callee → callee creates AR.

• Returns: Callee restores registers, pops AR, jumps to return address.

Storage Allocation Strategies

Register Allocation

• Graph Coloring:

  1. Build interference graph: nodes = temporaries, edge if live ranges overlap.

  2. Color graph with k colors (available registers).

  3. If coloring fails → spill temporaries to memory.

• Example: If 3 registers, but graph requires 4 colors → spill one temporary.

Procedure Calls

• Parameter Passing:

  • Call-by-value: Copy value.

  • Call-by-reference: Pass address (aliasing).

  • Call-by-value-result: Copy in/out (like inout).

  • Call-by-name: Textual substitution (thunks).

• Activation/Deactivation: Caller sets up params, callee saves state, returns via AR.

VII. CODE OPTIMIZATION

Principle Sources

Basic Block Optimization

• Constant Folding: Evaluate constant expressions at compile time.

  x = 3 + 5 * 2 → x = 13.

• Copy Propagation: Replace x = y with uses of x by y.

  x = y; z = x + 1 → z = y + 1.

• Common Subexpression Elimination (CSE): Reuse computed values.

  t1 = a + b; ... t2 = a + b → t2 = t1.

• Dead Code Elimination: Remove assignments whose values never used.

Loop Optimization

• Loop Invariant Code Motion: Move calculations independent of loop outside.

  for(i=0;i<n;i++) { x = y*z; a[i] = x; } → x = y*z; for(...) a[i]=x;

• Induction Variables: Variables with linear form x = c*i + d. Can be strength-reduced.

• Strength Reduction: Replace expensive ops (multiply) with cheaper (add).

  x = i * 4 → x = i << 2 or maintain x += 4 per iteration.

• Loop Unrolling: Duplicate loop body to reduce branch overhead.

Peephole Optimization

• Scope: Small window (peephole) of target code.

• Transformations:

  • Redundant load/store elimination.

  • Jump optimization: goto L1; L1: goto L2 → goto L2.

  • Algebraic simplifications: x = x * 1 → delete.

• Implementation: Scan code, apply pattern-matching rules.

DAG-based Optimizations

• Construction: From basic block, build DAG.

• Applications:

  • Eliminate common subexpressions (shared nodes).

  • Eliminate dead code (nodes with no output use).

  • Perform constant folding on constant nodes.

Properties of Optimizing Compilers

• Preservation of meaning: Optimized code must do same as original.

• Speedup: Should improve performance (time/space).

• Worthwhile: Optimization cost < benefit.

• Platform-independent: IR-based.

Tools for Code-Improving Transformations

• Data Flow Analysis: Reaching definitions, live variables, available expressions.

• Dependency Graphs: For scheduling.

• Profiling: Guide optimizations (hot spots).

VIII. ERROR HANDLING

Types of Errors

Error Detection and Recovery

• Detection: Each phase uses grammar/semantic rules.

• Recovery:

  • Lexical: Skip invalid char, continue.

  • Syntax: Panic mode (skip to synchronizing token), phrase-level (insert/delete), error productions.

  • Semantic: Report, continue (may cause cascading errors).

Error Reporting

• Message: Line number, error type, context.

• Example: error: line 15: ‘;’ expected.

Error Handling Phase Functionality

• Not a separate phase; integrated into each phase.

• Maintains error count, attempts recovery to find more errors.

IX. SPECIAL TOPICS (FREQUENTLY ASKED)

Input Buffering

• Purpose: Reduce I/O calls during lexical analysis.

• Double Buffering: Two buffers of size B. When one exhausted, fill other.

• Sentinel: Special char (e.g., eof) at end of buffer to avoid boundary checks.

• Lookahead: Needed for maximal munch (longest match). Use lexemeBegin and forward pointers.

L-attributed Definition

• Definition: SDD where inherited attributes can only come from parent or left siblings.

• Evaluation: Top-down (pre-order traversal).

• Example:

  S → A B

  A.synth = ...

  B.inherit = A.synth (allowed: left sibling).

  B.inherit = S.inherit (allowed: parent).

• Use: Suitable for recursive descent parsers.

Dynamic Storage Allocation

• Heap Allocation: malloc/free (C), new/delete (C++).

• Strategies:

  • First-fit: First block large enough.

  • Best-fit: Smallest sufficient block.

  • Worst-fit: Largest block.

• Garbage Collection: Reclaim unreachable objects.

  • Reference counting: Count references, collect when zero.

  • Mark-sweep: Mark reachable, sweep unmarked.

  • Copying: Two heaps, copy live objects.

Backpatching

• Purpose: Resolve forward jumps (unknown target addresses).

• Boolean Expressions: Maintain true and false lists of quadruple indices.

• Flow-of-control Statements:

  • If: if (E) S1 else S2 → backpatch E.true to S1, E.false to S2.

  • While: while (E) S → backpatch E.true to S, E.false to after loop.

• Example:

  if a < b then x = y else x = z

  TAC: if a < b goto —; goto —; x = y; goto —; x = z;

  Backpatch true list to x=y, false to x=z.

Peephole Optimization

• Window: Fixed-size sequence of instructions (e.g., 3–5).

• Patterns:

  • LOAD R, x; STORE x, R → delete both.

  • MOV R1, R2; ADD R1, c → ADD R2, c if R1 dead.

  • JMP L1; L1: JMP L2 → JMP L2.

• Implementation: Scan repeatedly until no change.

Loop Optimization Techniques

1. Loop Invariant Code Motion: Move invariant computations outside.

2. Induction Variable Elimination: Replace induction vars with canonical form.

3. Strength Reduction: * → +, ^2 → *.

4. Loop Unrolling: Duplicate body to reduce loop overhead.

5. Loop Fusion: Combine loops with same range.

Characteristics of Basic Blocks

• Single entry (first instruction), single exit (last instruction).

• No jumps except at end.

• All instructions execute if entry taken.

• Used for data flow analysis, optimization.

Overloading of Functions

• Same function name, different parameter types/numbers.

• Resolution: At compile time based on argument types (static overloading).

• Example: void print(int), void print(string).

• Ambiguity: If conversions ambiguous → compile error.

Polymorphic Functions

• Work with multiple types.

• Ad-hoc Polymorphism: Overloading (different implementations per type).

• Parametric Polymorphism: Generic functions (e.g., template<class T> T max(T a, T b)).

• Subtype Polymorphism: Inheritance, virtual functions (runtime).

Procedure Calls

• Steps: Evaluate args, save caller state, jump to callee, callee sets up AR, executes, returns value, restore state.

• Calling Convention: Who pushes args (caller/callee), who cleans stack, register preservation.

• Performance: Overhead of AR setup, parameter passing.

Symbol Table Data Structures

• Hash Table: Fast O(1) average lookup, handle collisions (chaining/open addressing).

• Binary Search Tree: Ordered, O(log n) if balanced.

• Linked List: Simple, O(n) lookup.

• Scoped Tables: Stack of hash tables for nested scopes.

Quadruples vs Triples

Cross Compiler

• Compiler runs on machine A, generates code for machine B.

• Example: Compile C code for ARM on x86 host.

• Use: Embedded systems, OS development.

Finite State Machines (FSM) in Lexical Analysis

• DFA recognizes tokens.

• States: Start, in-id, in-num, etc.

• Transitions: On input char, move state.

• Limitation: Cannot count or match nested structures.

Applications of DAGs

• Common Subexpression Elimination: Shared nodes.

• Constant Folding: Evaluate constant nodes.

• Dead Code Elimination: Nodes with no effect on output.

• Code Generation: Order of evaluation (postorder traversal).

Equivalence of Type Expressions

• Name Equivalence: Types equal if declared with same name (e.g., typedef int miles; miles vs int → different).

• Structural Equivalence: Types equal if same structure (e.g., array[10] of int ≡ array[10] of int).

• Example: int and integer (alias) may be name-equivalent if same declaration.

Constant Folding

• Evaluate constant expressions at compile time.

• Example: 3 + 5 * 2 → 13.

• Prerequisite: Operands must be compile-time constants.

Three-Address Code for Switch Statements

switch E {

  case c1: S1; break;

  case c2: S2; break;

  ...

  default: Sd;

}

TAC:

t = E

if t == c1 goto L1

if t == c2 goto L2

...

goto Ld

L1: S1; goto Lend

L2: S2; goto Lend

...

Ld: Sd

Lend:

LR Parsing Tables Implementation

• LR(0) Items: A → α•β.

• Canonical Collection: Closure (add items for non-terminal after dot), Goto (move dot over terminal/non-terminal).

• SLR Table:

  • ACTION: If item A → α•aβ → shift on a.

  • If A → α• (complete) and a ∈ FOLLOW(A) → reduce.

  • If S' → S• and a = $ → accept.

• Example: For S → L = R | R, L → *R | id, R → L, compute items, build table.

Regular Expressions for Specific Languages

• Odd number of a and odd number of b:

  (a(ba)*b | b(ab)*a)(a|b)*

  Explanation: Start with a...b or b...a to get odd counts, then any even pairs.

• Identifier in C: [a-zA-Z_][a-zA-Z0-9_]*

• Integer with optional sign: [+-]?[0-9]+

Exam Tips:

• Phases of Compiler: Memorize output for a = b + c * 50 at each phase.

• LEX: Structure (definitions, rules, subroutines) often asked.

• LL(1) vs LR: Know FIRST/FOLLOW computation, parsing table construction.

• Attributes: Distinguish synthesized (bottom-up) vs inherited (top-down). L-attributed allows left siblings.

• TAC: Practice generating for expressions, loops, conditionals.

• Backpatching: Crucial for boolean expressions and jumps.

• DAG: Construct from basic block, identify CSE.

• Activation Record: Know layout (temporaries, locals, params, control/access links).

• Optimization: Constant folding, CSE, loop invariant motion are favorite.

• Special Topics: Input buffering, L-attributed, backpatching, peephole, loop opt, DAG apps frequently appear as short notes.