UNIT 4: Compiler Design - Short Notes

I. Introduction and Compiler Overview

Phases of a Compiler

A compiler operates as a sequence of phases, each transforming the source program representation.

Separation of Lexical & Syntax Analysis

• Simplicity: Lexical analysis deals with regular patterns (tokens), syntax analysis with context-free structures. Separation simplifies each phase's design.

• Efficiency: Lexical analyzer can use fast, table-driven techniques (finite automata). Syntax analysis is more complex.

• Portability: Token definitions & lexical rules are often language-specific, while parser logic is more general. Separating them aids in retargeting.

• Ignoring Whitespace/Comments: Lexical phase removes these non-significant characters, simplifying the parser's token stream.

Bootstrapping

• Concept: The process of using a compiler to compile itself. Often involves writing the initial compiler in a different language (or machine code), then using that compiler to compile a more advanced version of itself written in its own source language.

• Significance: Essential for self-hosting compilers. Enables the compiler's source code to be written in the very language it compiles, improving maintainability and portability.

• Types:

  • Simple Bootstrapping: Write compiler C₁ for language L in language M. Use C₁ (in M) to compile C₂ (in L) to get C₃ (in machine code).

  • Cross-Compilation: Compiler runs on machine A but generates code for machine B. First step in bootstrapping for a new platform.

Comprehensive Example: Compilation of a = (x/y) * (y + x - z)

1. Lexical Analysis: [id(a), =, (, id(x), /, id(y), ), *, (, id(y), +, id(x), -, id(z), )]

2. Syntax Analysis: Builds parse tree based on grammar (e.g., E → E * E | E / E | E + E | E - E | (E) | id).

3. Semantic Analysis: Checks types (assume all id are int). No type errors. Annotates nodes with type int.

4. Intermediate Code (TAC):

   
   t1 = x / y
   
   t2 = y + x
   
   t3 = t2 - z
   
   t4 = t1 * t3
   
   a = t4
   
   

5. Optimization: (Minimal here). Could potentially combine t2 and t3 if no reuse.

6. Code Generation (x86-like):

   
   mov eax, x
   
   cdq
   
   idiv y        ; eax = x/y
   
   mov ebx, eax  ; save t1 in ebx
   
   mov eax, y
   
   add eax, x    ; eax = y+x
   
   sub eax, z    ; eax = (y+x)-z
   
   imul ebx      ; eax = t1 * t3
   
   mov a, eax
   
   

II. Lexical Analysis

Role & Responsibilities

• Tokenization: Scan source characters, form lexemes, and output corresponding tokens (<token-name, attribute-pointer>).

• Remove Noise: Strip whitespace and comments.

• Error Detection: Report illegal characters or malformed lexemes (e.g., 12.3.4).

• Correlation with Symbol Table: For tokens like id and literal, often inserts into symbol table and returns a pointer to the entry as the attribute.

Finite Automata & Regular Expressions

• Regular Expressions (RE): Algebraic notation to describe regular languages (sets of strings).

  • Example: Strings with odd number of a and odd number of b:

$$ ( (a(ba)^*b) + (b(ab)^*a) ) (a|b)^* $$

    *   `(a(ba)*b)`: Starts/ends with `a...b`, odd `a`, odd `b`.

    *   `(b(ab)*a)`: Starts/ends with `b...a`, odd `a`, odd `b`.

    *   `(a|b)*`: Any suffix doesn't change parity.

• Finite Automata (FA): Machine (states, transitions) that accepts/rejects strings. RE → NFA (Thompson's construction) → DFA (subset construction) → Minimized DFA.

• Lexical Spec → RE → DFA → Code: Standard implementation path.

LEX/FLEX

• Structure of a Lex Program:

  
  %{
  
      /* C declarations (global vars, functions) */
  
  %}
  
  %% 
  
  /* Rules Section: Pattern { Action } */
  
  [a-zA-Z_][a-zA-Z0-9_]*   { return ID; }   /* Recognizes identifiers */
  
  "+"|"-"|"*"|"/"          { return *yytext; } /* Returns operator char */
  
  [ \t\n]                  ; /* Skip whitespace */
  
  .                        { fprintf(stderr, "Illegal char: %c\n", *yytext); }
  
  %%
  
  /* User Code Section (main, yyerror, etc.) */
  
  int main() { yylex(); return 0; }
  
  

• How it works: Lex generates lex.yy.c containing a table-driven DFA scanner. yylex() function drives the DFA.

Token Recognition: Identifiers & Keywords

• Challenge: Keywords (if, while) and identifiers share the same lexical pattern ([a-zA-Z_][a-zA-Z0-9_]*).

• Solution:

  1. Lexical analyzer recognizes the lexeme as an id pattern.

  2. Looks up the lexeme in the symbol table.

  3. If found and marked as keyword, returns the keyword token.

  4. If not found (or found as ordinary identifier), returns id token and possibly inserts new entry.

• Example: Lexeme "while" → lookup → found as keyword → return token WHILE.

Input Buffering

• Need: To look ahead several characters to recognize the longest possible lexeme (maximal munch).

• Technique: Sentinel Method

  • Use two buffers (lexemeBegin, forward pointers) of size N.

  • End of each buffer marked by a sentinel character (e.g., EOF).

  • When forward reaches sentinel, refill that buffer. Avoids checking forward against buffer end on every character read.

  • Benefit: Reduces per-character branching overhead, speeding up scanning.

[!TIP] Exam Focus: Be prepared to write a simple Lex program for identifiers/operators and explain the sentinel method. The odd a/b RE is a classic.

III. Syntax Analysis

Role of the Parser

• Receives token stream from lexical analyzer.

• Constructs a parse tree (or AST) to represent the grammatical structure.

• Detects syntax errors (missing ;, mismatched ()).

• Reports errors meaningfully and attempts recovery to find more errors.

Context-Free Grammars (CFG)

• Components: G = (V, T, P, S)

  • V: Set of non-terminals (syntactic variables, e.g., E, T, F).

  • T: Set of terminals (tokens, e.g., id, +, *).

  • P: Set of productions (rules), e.g., E → E + T.

  • S: Start symbol.

• Derivation: Applying productions to replace a non-terminal.

  • Leftmost Derivation: Always replace leftmost non-terminal.

  • Rightmost Derivation: Always replace rightmost non-terminal.

• Parse Tree: Graphical representation of derivation. Interior nodes = non-terminals, leaves = terminals.

• Ambiguity: A grammar is ambiguous if a string has >1 distinct parse tree (or leftmost/rightmost derivation).

  • Example: E → E + E | E * E | a | b | c for string a+b*c.

    • Tree 1 (+ at root): (a+b) * c

    • Tree 2 (* at root): a + (b*c)

  • Solution: Use precedence rules or rewrite grammar to be unambiguous:

    
    E → E + T | T
    
    T → T * F | F
    
    F → a | b | c | (E)
    
    

Top-Down Parsing

Starts from start symbol, attempts to derive the input string.

• Recursive Descent: Write a procedure for each non-terminal. Backtracking may be needed (inefficient).

• Predictive Parsing (Non-Recursive): Uses a parsing table and a stack. No backtracking.

  • FIRST(X): Set of terminals that can begin any string derived from X.

  • FOLLOW(X): Set of terminals that can appear immediately to the right of X in some sentential form. $ (EOF) is in FOLLOW(S).

  • Algorithm for FIRST/FOLLOW: Standard procedures (see below).

  • Predictive Parsing Table M[A, a]:

    • If a ∈ FIRST(α), then A → α in M[A, a].

    • If ε ∈ FIRST(α) and a ∈ FOLLOW(A), then A → α in M[A, a].

    • If ε ∈ FIRST(α) and $ ∈ FOLLOW(A), then A → α in M[A, $].

    • Else error.

  • Example Grammar: A → (B) | a, B → B,B | A

    • FIRST: FIRST(A) = {(, a}, FIRST(B) = {(, a}

    • FOLLOW: FOLLOW(A) = {), ,}, FOLLOW(B) = {), ,}

    • Table: (Construct using rules above. Grammar is LL(1) if no conflicts).

Bottom-Up Parsing

Starts from input string, reduces to start symbol using productions in reverse.

• Shift-Reduce Parsing: Uses a stack and input buffer.

  • Shift: Move next input token onto stack.

  • Reduce: Pop RHS of production from stack, push LHS.

• LR Parsing Family: Most powerful deterministic bottom-up parsers.

  • LR(k): L = left-to-right scan, R = rightmost derivation (in reverse), k = lookahead tokens.

  • Comparison:

    | Parser | Construction | Table Size | Power | | :--- | :--- | :--- | :--- | | SLR(1) | FOLLOW sets of LHS | Smallest | Least (may have spurious conflicts) | | LALR(1) | Merged LR(1) states | Medium | Between SLR & LR | | LR(1)/CLR(1) | Full LR(1) states | Largest | Most powerful (no conflicts if grammar is LR(1)) |

  • Example Grammar: S → L = R | R, R → L, L → *R | id

    • CLR(1) Table Construction: (Standard algorithm: build LR(1) items, compute GOTO/ACTION). Result has no conflicts → grammar is LR(1).

  • Example Grammar for SLR: S → S + A | A, A → A B | B, B → B * | a | b

    • Compute FOLLOW(S)={$$\displaystyle , +}`, `FOLLOW(A)={+, $$}, FOLLOW(B)={*, +, $}.

    • Build state machine, then SLR table using FOLLOW for reductions. Check for shift-reduce/reduce-reduce conflicts.

Operator Precedence Parser

• Theory: For a subset of CFGs (operator grammars) where no production has two adjacent non-terminals on RHS.

• Method: Define precedence relations (<·, =·, ·>) between terminals based on grammar.

• Parsing: Uses a stack. Compare top-of-stack terminal with next input terminal using precedence table to decide shift/reduce.

• Limitation: Less powerful than LR, cannot handle all constructs (e.g., if-then-else ambiguity).

[!TIP] Exam Focus: Constructing predictive, SLR, and CLR(1) tables is very frequent. Practice step-by-step: compute FIRST/FOLLOW → build canonical collection → fill ACTION/GOTO. Know differences between SLR/LALR/LR.

IV. Syntax-Directed Translation & Semantic Analysis

Syntax-Directed Definitions (SDD)

Associates attributes with grammar symbols and semantic rules with productions.

• Attributes:

  • Synthesized: Computed from children's attributes in parse tree. Flows upward.

  • Inherited: Computed from parent/siblings' attributes. Flows downward/ sideways.

• Types of SDDs:

  • S-attributed: Only synthesized attributes. Evaluated in bottom-up (LR) parsing.

  • L-attributed: Inherited attributes restricted: X → Y₁ Y₂ ... Yₖ, inherited attrs of Yᵢ can depend on:

    1. Attributes of X (parent).

    2. Attributes of Y₁...Yᵢ₋₁ (left siblings).

    3. Not on Yᵢ₊₁...Yₖ (right siblings) or their descendants.

    • Can be evaluated in top-down (LL) or bottom-up (LR) order.

• Dependency Graph: For a parse tree node, draw edges from each attribute's defining occurrence to its used occurrences. A cycle → circular definition (error).

  • Example: For A → B C, with inherited B.i = A.sym and synthesized A.s = B.s + C.s, edges: A.sym → B.i, B.s → A.s, C.s → A.s.

Translation Schemes

SDD with embedded semantic actions placed within production RHS. Shows order of evaluation.

• Converting L-attributed to Scheme: Place inherited attribute calculations before the symbol they belong to. Place synthesized after.

  • Example: A → {B.in = A.in;} B {A.s = B.s + 1;}.

• Case/Switch Statement Scheme:

  
  switch E {
  
      case 1: S1; break;
  
      case 2: S2; break;
  
      ...
  
      default: Sd;
  
  }
  
  

  Translation:

  
  E → E1 { gen("if E1.val == 1 goto L1"); ... gen("goto Ldefault"); }
  
    | E2 { gen("if E2.val == 2 goto L2"); ... }
  
    | ...
  
    | Ed { gen("goto Ldefault"); }
  
  

  (Simplified: generate code to test each case value and jump).

Semantic Analysis

• Type Systems:

  • Type Checking: Verify operator-operand compatibility (e.g., int + bool error).

  • Type Conversion (Coercion): Implicit conversion to expected type.

    • Widening (safe): int → float.

    • Narrowing (may lose info): float → int (often requires explicit cast).

  • Example: float f; int i; f = i; → implicit widen i to float.

• Polymorphic Functions & Overloading:

  • Overloading: Same name, different parameter types (e.g., print(int), print(float)). Resolved at compile-time by signature matching.

  • Polymorphism: Same name, same interface but different implementations (e.g., virtual functions in C++). Often resolved at runtime (dynamic dispatch).

  • Compiler's Task: For overloading, build symbol table entries for each signature. At call site, match argument types to select correct function.

[!TIP] Exam Focus: Distinguish S- vs L-attributed. Draw dependency graphs. Write translation scheme for switch. Explain type conversion with examples.

V. Intermediate Code Generation

Three-Address Code (TAC)

• Definition: Sequence of simple statements with at most one operator per statement.

• General Form: x = y op z (or x = op y, goto L, if x relop y goto L, param, call, return).

• Why "Three-Address"? Each statement has three addresses (operands/result), though some have fewer.

Forms of TAC

1. Quadruples: (op, arg1, arg2, result).

   • Example: a + a*(b-c) + (b-c)*d

     
     ( -, b, c, t1 )
     
     ( *, a, t1, t2 )
     
     ( -, b, c, t3 )   // Common subexpr not yet eliminated
     
     ( *, t3, d, t4 )
     
     ( +, t2, t4, t5 )
     
     ( =, t5, -, a )
     
     

2. Triples: (op, arg1, arg2); results referenced by position (no separate result field). Can be explicit (list of triples) or implicit (referenced by pointer).

   • Example: Same expression.

     
     1: ( -, b, c )
     
     2: ( *, a, 1 )
     
     3: ( -, b, c )   // Duplicate!
     
     4: ( *, 3, d )
     
     5: ( +, 2, 4 )
     
     a = 5
     
     

   • Problem: Duplicate computation (triples 1 & 3). DAG solves this.

3. Indirect Triples: List of pointers to triples. Allows optimization by reordering pointer list without moving triple data.

   • [ &t1, &t2, &t3, &t4, &t5 ] where t1=( -, b, c ), etc.

Directed Acyclic Graphs (DAGs)

• Definition: A DAG for an expression is a directed graph where:

  • Leaf nodes = identifiers/constants.

  • Interior nodes = operators.

  • Each node represents a value.

  • Key Property: Common subexpressions are represented by a single node (shared).

• Construction: Process expression (postorder). For each node:

  • If operand is leaf, create node.

  • If operator, check if node (op, left-child, right-child) already exists in current node list.

    • Yes: Use existing node (common subexpr found).

    • No: Create new node.

• Examples:

  1. a + a*(b-c) + (b-c)*d

     
             +
     
            / \
     
           +   d
     
          / \
     
         *   a
     
        / \
     
       a   -
     
          / \
     
         b   c
     
     

     • (b-c) appears once (shared node).

     • TAC from DAG: t1 = b - c; t2 = a * t1; t3 = t2 + t1*d; a = t3 + a? Wait, careful:

     • Correct DAG:

       
             +
       
            / \
       
           *   +
       
          / \ / \
       
         a  - a  d
       
           / \
       
          b   c
       
       

     • Nodes: -(b,c) shared by both * and +? No, (b-c)*d uses d, not a. Let's build:

       • b-c → node N1.

       • a * N1 → node N2.

       • N1 * d → node N3.

       • N2 + N3 → node N4.

       • N4 + a → node N5 (but a is leaf).

       • Final DAG root is + with children N4 and a.

     • TAC: t1 = b - c; t2 = a * t1; t3 = t1 * d; t4 = t2 + t3; a = t4 + a? That's not the original expression. Original: a + (a*(b-c)) + ((b-c)*d).

     • Correct: a + t2 + t3 → (a + t2) + t3.

     • DAG:

       
             +
       
            / \
       
           +   t3
       
          / \
       
         a   t2
       
             |
       
             *
       
            / \
       
           a   t1
       
               |
       
               -
       
              / \
       
             b   c
       
       

     • TAC: t1 = b - c; t2 = a * t1; t3 = t1 * d; t4 = a + t2; a = t4 + t3.

  2. p + p*(q-r) + (q-r)*s

     • q-r → node N1 (shared).

     • p * N1 → node N2.

     • N1 * s → node N3.

     • p + N2 → node N4.

     • N4 + N3 → node N5.

     • DAG root N5.

     • TAC: t1 = q - r; t2 = p * t1; t3 = t1 * s; t4 = p + t2; p = t4 + t3 (assuming result in p).

  3. a*b + (c/(d/e))*d

     • d/e → N1.

     • c / N1 → N2.

     • N2 * d → N3.

     • a * b → N4.

     • N4 + N3 → N5.

     • TAC: t1 = d / e; t2 = c / t1; t3 = t2 * d; t4 = a * b; a = t4 + t3.

Backpatching

• Purpose: Handle jumps in boolean expressions and control flow (if, while) where target address is unknown until later.

• Mechanism: For a jump if x relop y goto _, generate a placeholder and maintain a list of pending jumps that need this target.

• Lists:

  • makelist(i): Returns list containing just index i of a quadruple.

  • merge(p1, p2): Concatenates two lists.

  • backpatch(list, target): Fills target field of all quadruples in list.

• Example for if (a < b) S else T:

  1. a < b → generates if a < b goto _ → M1 = makelist(nextquad).

  2. S code generated.

  3. S ends with goto _ → M2 = makelist(nextquad).

  4. backpatch(M1, quad(S)+1) (jump to T if false).

  5. T code generated.

  6. backpatch(M2, nextquad) (jump after T).

Different Intermediate Forms for d = (a-b) + (a-c) + (a-c)

• Naive TAC (no CSE):

  
  t1 = a - b
  
  t2 = a - c
  
  t3 = t1 + t2
  
  t4 = a - c   // Duplicate!
  
  t5 = t3 + t4
  
  d = t5
  
  

• With CSE (using DAG):

  
  t1 = a - c   // Compute once
  
  t2 = a - b
  
  t3 = t2 + t1
  
  d = t3 + t1
  
  

• Quadruples:

  
  (-, a, b, t1)
  
  (-, a, c, t2)   // t2 is common subexpr
  
  (+, t1, t2, t3)
  
  (+, t3, t2, t4)
  
  (=, t4, -, d)
  
  

• Triples:

  
  1: (-, a, b)
  
  2: (-, a, c)
  
  3: (+, 1, 2)
  
  4: (+, 3, 2)
  
  d = 4
  
  

[!TIP] Exam Focus: Constructing DAGs for given expressions is extremely frequent (seen in 3 papers). Practice step-by-step: identify common subexpressions, build DAG, then generate TAC. Understand backpatching lists for control flow.

VI. Symbol Tables

Purpose & Operations

• Purpose: Store information about identifiers (name, type, scope, line number, size, address/register, etc.) for use by all phases.

• Operations:

  • insert(name, type, ...): Add new entry (often at declaration).

  • lookup(name): Find entry for name (at use).

  • delete(name) or delete_scope(scope_id): Remove entries (e.g., end of scope).

  • print_table(): For debugging/error messages.

Data Structures for Implementation

Example: Symbol Table for Sample Program

int x;          // Global scope

void f(int y) { // Scope f

    int z;

    x = y + z;  // x: global, y: param, z: local

}

Hash Table (per scope):

• Global Scope Table:

  | Name | Type | Scope | Addr | | :--- | :--- | :--- | :--- | | x | int | global | R1 | | f | func | global | addr_f |

• Scope f Table (on top of stack):

  | Name | Type | Scope | Addr | | :--- | :--- | :--- | :--- | | y | int | f (param) | R2 | | z | int | f (local) | R3 |

• Lookup x in f: Search f table → not found → search global → found at R1.

[!TIP] Exam Focus: Compare data structures (time/space). Explain scope management with stack of tables. Be ready to draw symbol table for a given nested program.

VII. Error Handling

Lexical vs. Syntactic Errors

Error Recovery Strategies

1. Panic Mode: Simplest. On error, discard input tokens until a synchronizing token (e.g., ;, }) is found. Loses some input, but guarantees progress.

2. Phrase-Level Recovery: Enumerate common errors at a point and provide corrective actions (insert/delete/replace tokens). Requires knowledge of common mistakes.

3. Error Productions: Add augmented productions to grammar for common errors (e.g., missing_semicolon → S). Parser uses these to parse erroneous input and report specific error.

4. Global Correction: (Theoretical) Find minimal number of changes (insert/delete/replace) to make input valid. Uses Levenshtein distance. Impractical for real compilers due to cost.

Error Handling Phase in Compiler

• Not a separate phase. Error detection/recovery is integrated into each phase.

• Lexical: Report illegal character; use panic mode to skip.

• Syntax: Parser uses error routines on parsing table conflict. Reports line/column, expected vs. found token.

• Semantic: Type checker reports type mismatch; may insert conversion or flag error.

• Goal: Maximize number of errors detected per compilation, minimize cascading errors (one error causing many false positives).

[!TIP] Exam Focus: Differentiate lexical vs. syntactic errors with examples. List recovery strategies (panic mode most common). Explain how errors are reported (line numbers, expected tokens).

VIII. Runtime Environments

Activation Records (AR)

• Definition: The storage layout for a single procedure invocation (call). Also called stack frame.

• Typical Layout (grows downwards):

  
  -------------------  <- SP (Stack Pointer) after call
  
  | Actual Params    |   (passed by caller)
  
  -------------------
  
  | Return Address   |   (where to jump after return)
  
  -------------------
  
  | Control Link     |   (pointer to caller's AR, for non-local access)
  
  -------------------
  
  | Access Link      |   (pointer to AR of lexically enclosing scope, for nested procedures)
  
  -------------------
  
  | Saved Registers  |   (caller-saved/callee-saved)
  
  -------------------
  
  | Local Variables  |   (including temporaries)
  
  -------------------
  
  | ...              |
  
  -------------------  <- FP (Frame Pointer) points here (fixed during call)
  
  

• Example (Nested):

  
  procedure A;
  
    var x: int;
  
    procedure B;
  
      var y: int;
  
      begin ... end;
  
    begin ... end;
  
  

  • Call to B from A: B's AR has Access Link pointing to A's AR (to access x). Control Link points to A's AR (for return).

Storage Allocation Strategies

Procedure Calls

• Parameter Passing:

  • Call-by-Value: Copy value of actual param to formal param. Changes in callee not visible to caller.

  • Call-by-Reference: Pass address of actual param. Callee accesses original variable. Changes visible to caller. (int &x in C++, var in Pascal).

  • Call-by-Value-Result (Copy-in/Copy-out): Copy in at start, copy out at end. Like value, but changes visible (but tricky with aliases).

• Return Values: Typically returned in a designated register (e.g., eax in x86) or via pointer parameter.

• Stack Unwinding: On return, restore saved registers, pop AR (reset SP to Control Link), jump to return address.

[!TIP] Exam Focus: Draw activation record for nested procedures (show access/control links). Compare stack vs heap allocation. Explain parameter passing methods with examples.

IX. Optimization

Basic Blocks & Flow Graphs

• Basic Block: A sequence of consecutive statements with:

  1. Single entry (first statement only).

  2. Single exit (last statement only, a jump).

  3. No jumps into or out of the middle.

• Construction: Partition TAC into blocks by leaders (first statement, target of jump, statement after jump).

• Flow Graph: Nodes = basic blocks. Edges = possible control flow (fall-through or jump).

• Characteristics of Basic Blocks: Used for local optimization (within block). All statements execute if entry executed.

• Reducible vs. Non-Reducible Flow Graphs:

  • Reducible: Can be constructed by structured constructs (if, while, for). Has no jumps into loops from outside. Most programming languages produce reducible graphs. Easier for analysis.

  • Non-Reducible: Contains arbitrary jumps (e.g., goto into loops). Harder to analyze, may require more complex algorithms.

Loop Optimization

• Invariant Code Motion (Code Motion): Move loop-invariant statements (compute same value each iteration) outside the loop.

  • Condition: Statement S is inside loop L, and for all paths through L, S's operands are unchanged before S.

  • Example:

    
    for(i=0; i<n; i++) {
    
        x = y * z;   // Invariant if y,z not changed in loop
    
        a[i] = x + i;
    
    }
    
    

    Optimized:

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

• Induction Variables: Variable x is induction if it changes by a constant each iteration (e.g., i in for loop).

• Strength Reduction: Replace expensive operations (multiplication) with cheaper ones (addition) using induction variables.

  • Example: x = i * 8 in loop where i increments by 1.

    • Introduce t = 0; each iteration: t = t + 8, x = t. Replaces *8 with +8.

Global Optimizations

• Constant Folding: Evaluate constant expressions at compile time.

  • 3 * 4 → 12, 'A' + 1 → 'B'.

• Constant Propagation: If x = 5, then replace uses of x with 5.

• Common Subexpression Elimination (CSE): Eliminate duplicate computations of same expression. Use DAGs or value numbering.

• Variable Propagation (Copy Propagation): Replace y = x followed by ... x ... with ... y .... Simplifies expressions.

• Dead Code Elimination: Remove statements whose computed values are never used (e.g., x = 5; where x not used later).

• Strength Reduction: As above, but applied globally (e.g., x*2 → x+x, x*4 → x<<2).

Peephole Optimization

• Local optimization on a small sliding window (peephole) of target code (e.g., 3-5 instructions).

• Examples:

  • Redundant load/store elimination: mov ax, x; mov x, ax → delete second.

  • Branch optimization: jmp L1; L1: ... → delete jmp if L1 immediately follows.

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

  • Sequence reduction: push a; push b; add → push (a+b) if possible.

• Pros: Simple, fast, effective.

• Cons: Local view may miss global opportunities.

Dependency Graphs for Optimization

• Data Dependencies: Between statements Sᵢ and Sⱼ.

  • Flow Dependence (True): Sⱼ uses value defined by Sᵢ. (Sᵢ → Sⱼ)

  • Anti-Dependence: Sⱼ defines variable that Sᵢ uses. (Sⱼ → Sᵢ)

  • Output Dependence: Both Sᵢ and Sⱼ define same variable. (Sᵢ ↔ Sⱼ)

• Instruction Scheduling: Use dependency graph to reorder independent instructions to avoid stalls (e.g., fill delay slots). Topological sort of graph gives valid orderings.

[!TIP] Exam Focus: Loop optimization (invariant code motion, strength reduction) with step-by-step example is crucial. Know definitions of all global optimizations (CSE, constant folding/propagation, dead code). Explain peephole with examples. Draw dependency graph for small code fragment.

X. Advanced Topics (Brief Notes)

Operator Precedence Parser

• For: Operator grammars (no two adjacent non-terminals in RHS).

• Method: Define precedence relations (<·, =·, ·>) between terminals.

  • a <· + if a has higher precedence than +.

  • + =· + if + is left-associative.

  • + ·> a if + has lower precedence than a.

• Parsing: Stack holds terminals. Compare stack-top with next-input using precedence table.

  • stack-top <· next → shift.

  • stack-top ·> next → reduce by some production A → α where α's terminals match stack top.

  • = → equal (for productions like E → E + E, + relates to +).

• Example: Grammar E → E + E | E * E | id. Precedence: * > +, both left-assoc. Relations: id <· +, + <· *, + =· +, * =· *, * ·> id, etc.

Bootstrapping

• Self-Compilation: Writing a compiler C for language L in language L itself.

• Process:

  1. Write interpreter for L in machine code or another language M.

  2. Write compiler C₁ for L in M (or a subset of L).

  3. Use C₁ to compile compiler C₂ (written in L) to machine code.

  4. Now C₂ is a native compiler for L.

• Cross-Compilation: Compiler runs on host A but generates code for target B. First step when no native compiler exists for B. Uses bootstrapping eventually.

Polymorphic Functions & Overloading

• Overloading: Same function name, different parameter types. Resolved at compile-time by matching argument types to function signatures in symbol table.

  • Example: max(int, int), max(float, float).

• Polymorphism (Parametric): Function works for any type (e.g., template <typename T> T max(T a, T b)). Type is instantiated at call site.

• Compiler's Role: For overloading, build signature table. At call, perform type matching (best fit). For polymorphism, generate type-specific code (instantiation) or use generic representations.

KEY FORMULAS & ALGORITHMS

FIRST Set Computation

FIRST(X):

  if X is terminal: FIRST(X) = {X}

  if X is non-terminal:

    for each production X → Y1 Y2 ... Yk:

      add FIRST(Y1) to FIRST(X)

      if ε ∈ FIRST(Y1) then add FIRST(Y2), ... until non-nullable

      if all Y1..Yk nullable, add ε

  if X → ε is a production, add ε

FOLLOW Set Computation

FOLLOW(S): {$} (S is start symbol)

FOLLOW(A) for non-terminal A:

  for each production ... B → ... A α ...:

    add FIRST(α) \ {ε} to FOLLOW(A)

    if ε ∈ FIRST(α) or α is empty:

      add FOLLOW(B) to FOLLOW(A)

LR(1) Item & Canonical Collection

• LR(1) Item: [A → α·β, a] where a is lookahead terminal. Means: we have parsed α, expecting β, and if we reduce A→α, the next token should be a.

• Closure(I): Add items for non-terminals after · with all possible lookaheads (from FIRST of remaining string).

• GOTO(I, X): Move · past X in all items of I, then take closure.

• Canonical Collection: Start with closure({[S' → ·S, $]}). Repeatedly apply GOTO for all symbols until no new states.

Three-Address Code Forms Summary

DAG Construction Algorithm (for expression)

function create_node(op, left, right):

  if node(op, left, right) exists in node list:

    return existing node

  else:

    create new node, add to list, return it

function leaf(value):

  if value is identifier/constant:

    if leaf node exists: return it

    else: create new leaf, return it

• Process expression in postorder (children before parent).

COMMON PITFALLS & EXAM TIPS

[!TIP] Parsing Tables: The #1 exam trap is incorrect FIRST/FOLLOW leading to wrong table. Double-check:

• FIRST(A) includes terminals only (not ε initially).

• FOLLOW(A) includes terminals only (not ε, but $).

• For A → α, if ε ∈ FIRST(α), use FOLLOW(A) for reductions in SLR/LALR.

• SLR uses FOLLOW for all reductions → may have spurious conflicts.

• CLR(1) uses specific lookaheads from LR(1) items → more precise.

[!TIP] DAGs: Students often forget to share nodes for identical subexpressions. Remember: same operator, same children → same node. Draw DAG clearly with shared nodes.

[!TIP] Activation Record: Know the purpose of each field. Access Link vs Control Link is a common question. Access Link = lexical parent (for non-local variable access). Control Link = dynamic caller (for return).

[!TIP] Loop Optimization: For invariant code motion, prove invariance: all operands must be unchanged in the loop. If an operand is a local variable that is assigned inside the loop, it's not invariant.

[!TIP] Lex vs Parser: Lex handles patterns (RE → DFA). Parser handles structure (CFG → parse tree). Lex returns tokens; parser builds tree. They communicate via symbol table for id/keywords.

[!TIP] S- vs L-attributed: If all attributes are synthesized → S-attributed (bottom-up). If inherited allowed but only from parent/left siblings → L-attributed (can do top-down or bottom-up). L-attributed covers most language constructs (e.g., inherited type in declarations).

Final Note: This unit is highly practical. For exams, be prepared to construct (parsing tables, DAGs, TAC, symbol tables) and explain concepts with examples. Always trace a small expression (like a + a*(b-c) + (b-c)*d) through all relevant phases—it appears repeatedly in past papers.