UNIT 3: Compiler Design (Based on Past Exam Questions)

1. Introduction to Compilers

1.1 Definition and Purpose

A compiler is a program that translates source code written in a high-level language (source language) into an equivalent target language (usually machine code or assembly). Its primary purpose is to detect and report errors in the source program and generate efficient executable code.

1.2 Phases of a Compiler

A typical compiler is partitioned into a sequence of phases, each with a specific function:

1.3 Bootstrapping

• Concept: The process of using a simpler/older version of a compiler (or an interpreter) to compile a more advanced version of itself.

• Process: A minimal compiler (often written in assembly) for language L is used to compile a more feature-rich compiler (written in L). This new compiler can then compile even more advanced versions. It's essential for porting compilers to new architectures.

Exam Tip: Be ready to explain the "bootstrap loader" concept – a tiny program that loads the initial compiler.

2. Lexical Analysis

2.1 Role & Separation from Syntax Analysis

• Role: Simplifies syntax analysis by removing low-level details (whitespace, comments) and grouping characters into meaningful tokens (keywords, identifiers, operators).

• Reasons for Separation:

  1. Simplicity: Removes tedious, non-semantic details from syntax analyzer.

  2. Efficiency: Token recognition can be highly optimized (e.g., using Finite Automata).

  3. Portability: Device-dependent I/O and character set handling are isolated.

  4. Language Independence: Lexical rules change less often than syntactic rules.

2.2 Finite Automata & Regular Expressions

• Regular Expressions (RE): Concise notation for describing token patterns (e.g., id = letter (letter | digit)*).

• Finite Automata (FA): Abstract machines (DFA/NFA) that recognize REs. The lexical analyzer is essentially a DFA simulator.

  • Transition Diagram: Visual representation of FA states and transitions.

  • Transition Table: Tabular representation used in implementation.

2.3 LEX Tool

• Structure: A LEX program has three sections:

  1. Definitions: (REs, C code declarations).

  2. Rules: Pattern { Action } (e.g., letter(letter|digit)* { return ID; }).

  3. User Code: (C functions, main()).

• How it Works: LEX generates a C program (lex.yy.c) containing a DFA-based scanner (yylex() function). This function reads input, matches patterns, and executes associated actions.

Example Rule for Identifier & Arithmetic Operators:

%{

#include "y.tab.h" // Token definitions from parser

%}

%%

[a-zA-Z][a-zA-Z0-9]* { yylval = atoi(yytext); return ID; }

"+" { return PLUS; }

"-" { return MINUS; }

"*" { return MUL; }

"/" { return DIV; }

[ \t\n] ; // Ignore whitespace

. { return yytext[0]; } // Catch-all

%%

3. Syntax Analysis

3.1 Context-Free Grammars (CFGs)

• Definition: A formal grammar G = (N, T, P, S) where N = non-terminals, T = terminals, P = productions, S = start symbol.

• Capabilities: Precisely describes nested, recursive structures (matching parentheses, nested if-else).

• Limitations: Cannot express context-sensitive constraints (e.g., "variable must be declared before use").

3.2 Parsing Techniques: Top-down vs Bottom-up

3.3 Operator Precedence Parsing

• Principle: Uses precedence relations (<·, =, ·>) between adjacent terminals to find handles. Based on the fact that operators have inherent precedence.

• Steps:

  1. Insert # (end marker) at start/end.

  2. Scan stack top a and input b.

  3. Apply relation: if a <· b, shift b. If a ·> b, reduce by some A → α where α's RHS ends with a and starts with something ·> b.

• Limitation: Only works for operator grammars (no two adjacent non-terminals on RHS of any production).

3.4 Parser Types: LL, SLR, LR, LALR, CLR

3.5 Comparison: SLR vs LALR Parsers

3.6 FIRST & FOLLOW Sets: Computation

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

  • Rules:

    1. If X → aα, add a.

    2. If X → ε, add ε.

    3. If X → Y1Y2...Yk, add FIRST(Y1) (if ε ∉ FIRST(Y1) stop). If all Yi derive ε, add ε.

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

  • Rules:

    1. If A → αXβ, add FIRST(β) - {ε}.

    2. If A → αX or A → αXβ where ε ∈ FIRST(β), add FOLLOW(A).

    3. Repeat until no change.

3.7 Parsing Table Construction

For SLR(1):

1. Build LR(0) items (productions with · indicating parser position).

2. Construct canonical collection of LR(0) items (states).

3. ACTION table:

   • [Si, a] (shift): if [A → α·aβ] in state i and goto on a leads to state j.

   • [rj] (reduce by A → α): if [A → α·] in state i and a ∈ FOLLOW(A).

   • accept: if [S' → S·] in state i and input is $.

   • error: otherwise.

4. GOTO table: [i, A] = j if goto on non-terminal A from state i leads to j.

For CLR(1) / LR(1):

• Items are [A → α·β, a] where a is lookahead.

• Closure and goto operations propagate lookaheads.

• Reduction [A → α·, a] is placed only if a is in lookahead set. More precise, avoids SLR conflicts.

3.8 Parse Tree Construction & Ambiguity Elimination

• Ambiguous Grammar: A grammar where a string has multiple parse trees (e.g., E → E+E \| E*E \| id for a+b*c).

• Elimination: Use precedence & associativity rules to rewrite grammar or use parser with precedence.

  • Example: For a+b*c, standard math precedence (* > +) and left associativity.

  • Unambiguous Grammar:

    
    E → E + T \| T
    
    T → T * F \| F
    
    F → ( E ) \| id
    
    

  • Parse Tree: E (root) → E + T → T + T → id + T*F → id + id*id.

3.9 Checking Grammar for SLR(1) Correctness

1. Build canonical collection of LR(0) items.

2. Construct SLR(1) parsing table.

3. Check for conflicts:

   • Shift-Reduce (S/R): If an entry ACTION[i, a] would contain both Si and rj (where a ∈ FOLLOW(A) for reduction A → α), conflict exists.

   • Reduce-Reduce (R/R): If ACTION[i, a] would contain rj and rk for different A → α and B → β, conflict exists.

4. If no conflicts in any entry → Grammar is SLR(1).

4. Semantic Analysis

4.1 Syntax-Directed Definitions (SDDs)

• Definition: A CFG augmented with semantic rules/actions attached to productions. Defines attribute values for grammar symbols.

• Purpose: To evaluate semantic information (type, value, code) during parsing.

4.2 Attribute Types

• Synthesized Attributes: Values computed from children's attributes in the parse tree. Flow upward.

  • Example: E.val in E → E1 + T where E.val = E1.val + T.val.

• Inherited Attributes: Values computed from parent and/or siblings. Flow downward/sideways.

  • Example: L.in (type environment) in L → L1 , id where L.in = L1.in and id.type = L1.in.lookup(id.name).

4.3 S-attributed vs L-attributed Definitions

4.4 Dependency Graphs

• Definition: A directed graph where nodes represent attribute instances in a parse tree. An edge A → B means value of A is needed to compute B.

• Construction: For each semantic rule B = f(A1, A2, ...), add edges A1 → B, A2 → B, etc.

• Purpose: To check for circular dependencies (ill-formed SDD). Acyclic graph → attributes can be evaluated.

Example: For S → L = R with rules S.code = L.code || R.code || '=' and L.place = R.place, edges: L.code → S.code, R.code → S.code, R.place → L.place.

4.5 Bottom-up Evaluation of Attributes

• S-attributes: Trivial. When a reduction by A → α occurs, compute A's synthesized attributes from α's attributes (already on stack). Push A's values onto stack.

• L-attributes: More complex. Requires stack to hold inherited attributes of non-terminals. When reducing A → X Y Z:

  1. Inherited attributes of X are computed before X is reduced (using parent's inherited & Y,Z's synthesized).

  2. After X is reduced, its synthesized attributes are available.

  3. Repeat for Y, then Z.

4.6 Translation Schemes: Converting L-attributed Grammars

• Translation Scheme: CFG with embedded semantic actions (in curly braces {}) within RHS.

• Conversion Rule: Place inherited attribute computations as early as possible (before the non-terminal needing them is parsed).

  • Example: L → {L1.in = L.in;} L1 , id becomes L → L1 {L1.in = L.in;} , id in a top-down parser.

• Result: Scheme can be parsed top-down (LL) or bottom-up (LR) while evaluating attributes correctly.

4.7 Syntax-directed Translation for Case Statements

• Grammar:

  
  stmt → case expr of case_list end
  
  case_list → case_list case | case
  
  case → const ':' stmt
  
  

• Translation: Generate jump tables or conditional branches.

  • expr evaluated once, result saved.

  • For each case, compare expr.val with const.val. If equal, goto stmt.label.

  • If no match, goto default (if exists) or error.

• Backpatching: Used to fill in jump addresses after code generation.

4.8 Backpatching

• Purpose: To generate unresolved jumps (goto L) during intermediate code generation and fill in actual addresses later.

• Mechanism:

  • Maintain a list of pending jump locations (quadruple indices) for each boolean expression or control structure.

  • When the target label's address is known, backpatch the list to that address.

• Example: For if (a == b) goto L1; ... L1: ..., initially if generates (if a == b goto -) and returns list [-]. Later, when L1 is defined, makelist(nextquad) is used and backpatch(list, L1.quad) fills - with L1's quad number.

5. Intermediate Code Generation

5.1 Forms of Intermediate Representation

5.2 Generating Intermediate Code for Expressions

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

• Quadruples (using grammar E → E+T \| T, T → T*F \| F, F → (E) \| id):

  
  1:  -   a   b   t1
  
  2:  -   a   c   t2
  
  3:  +   t1 t2  t3
  
  4:  -   a   c   t4
  
  5:  +   t3 t4  t5
  
  6:  =   t5 -   d
  
  

  (Note: (a-c) computed twice → common subexpression for optimization).

6. Symbol Table Management

6.1 Purpose & Operations

• Purpose: Central repository for identifier information (name, type, scope, address, size, line number).

• Operations:

  • insert(name, attributes): Add new entry.

  • lookup(name): Find entry.

  • delete(name) / delete_scope(scope): Remove entries (for scope exit).

6.2 Data Structures for Implementation

Exam Tip: Hash tables are most common in practice due to speed. Symbol table often uses multiple scopes (nested hash tables or stack of hash tables).

7. Runtime Storage Organization

7.1 Activation Records (AR) / Stack Frames

• Structure: (Typically grows downward on stack)

  
  ↑
  
  | Actual parameters |
  

| Return address | | Control link (FP) | | Access link (for non-local vars) | | Local variables | | Temporaries | | ... |

↓ (Stack Pointer SP)

```

• Components:

  • Local Data: Variables, temporaries.

  • Machine Status: Return address, saved registers.

  • Control Link: Pointer to caller's AR (old FP).

  • Access Link: Pointer to lexical parent's AR (for nested scopes).

  • Parameters: Passed by caller.

7.2 Storage Allocation Strategies

7.3 Heap Storage Allocation

• Strategies:

  1. First-fit: Allocate first hole large enough.

  2. Best-fit: Allocate smallest hole large enough.

  3. Worst-fit: Allocate largest hole.

• Management Issues:

  • Fragmentation: External (holes between allocated blocks), Internal (allocated block larger than requested).

  • Compaction: Moving allocated blocks to gather free space (costly, requires updating pointers).

  • Garbage Collection: Automatic reclamation of unreachable heap objects.

8. Code Optimization

8.1 Basic Blocks & Flow Graphs

• Basic Block: A maximal sequence of consecutive statements with:

  1. Single entry (first statement only).

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

• Construction:

  1. Identify leaders (first statement, target of jump, statement after jump).

  2. Start new block at each leader.

  3. Include following statements until next leader.

• Flow Graph: Nodes = basic blocks. Edges = possible control flow between blocks (fall-through & jumps).

8.2 Reducible vs Non-Reducible Flow Graphs

8.3 Optimization Techniques

• Loop Optimization:

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

    • Example: for(i=0;i<n;i++) x = a*b + c[i]; → move a*b out.

  • Induction Variable Elimination: Replace induction variables (change by constant each iteration) with a single variable.

    • Example: i and j = 2*i → use only i, compute j as needed or eliminate.

• Common Subexpression Elimination (CSE): Compute expression once, reuse result.

  • Example: t1 = a+b; ... t2 = a+b; → replace t2 with t1.

• Variable Propagation (Copy Propagation): Replace uses of a variable with its defined constant or another variable.

  • Example: x = 5; ... y = x+2; → y = 5+2.

• Strength Reduction: Replace expensive operations (*, /) with cheaper ones (+, -).

  • Example: x = i*8; → x = i<<3; or loop i*4 → maintain x and add 4 each iteration.

8.4 Optimization of Basic Blocks (Local)

• Performed within a single basic block (no control flow).

• Techniques:

  1. Constant Folding: Evaluate constant expressions at compile time (2+3 → 5).

  2. Algebraic Simplifications: x*1 → x, x+0 → x.

  3. Dead Code Elimination: Remove statements whose results are never used.

  4. CSE & Copy Propagation (as above, within block).

8.5 Data Flow Analysis Concepts

• Goal: Gather global information about how values flow through the program.

• Key Concepts:

  • Data Flow Equations: Define how information propagates along edges (IN[n] = union(OUT[p]) for predecessors p).

  • Direction: Forward (e.g., reaching definitions) vs Backward (e.g., live variables).

  • Fixed Point Iteration: Repeatedly apply equations until no change (convergence).

  • Meet Operator: ∩ (intersection) for must problems, ∪ (union) for may problems.

• Examples:

  • Reaching Definitions: Set of defs that may reach a point (forward, may).

  • Live Variables: Variables that may be used before next definition (backward, may).

  • Available Expressions: Expressions whose values are already computed and not killed (forward, must). Used for CSE.

Exam Tip: Be able to draw a flow graph from code, identify loops (using dominators), and apply local optimizations to a basic block. Know the difference between must and may analysis.