Compiler Design (AL-703 (A)) - Unit 5 Short Notes

UNIT 5: Compiler Design – Advanced Topics & Optimization

I. Lexical Analysis

Input Buffering

• Purpose: To efficiently read the input stream character-by-character without making system calls for each character.

• Schemes:

  1. Two-Buffer Scheme: Input is divided into two equal-sized buffers. The lexer reads from one while the other is being filled. A sentinel character (e.g., EOF) marks the buffer's end to avoid constant boundary checks.

  2. Sentinel Implementation: Appending a special character (e.g., eof) at the end of each buffer simplifies the lexeme recognition loop by eliminating explicit if checks for buffer limits.

• Key Concept: Reduces I/O overhead, crucial for large source files.

Recognition of Identifiers and Keywords

• Process:

  1. Pattern Matching: Lexer uses a ** Deterministic Finite Automaton (DFA)** derived from regular expressions to recognize the pattern letter (letter | digit)* for identifiers.

  2. Token Identification: The lexeme is first matched against the identifier pattern.

  3. Symbol Table Check: The lexeme is then looked up in the symbol table. If found as a reserved keyword (e.g., if, while), the token type is set to that keyword. Otherwise, it's an ID token, and a new entry may be created.

• Example: Lexeme "int" matches identifier pattern but is found in keyword table → Token: KEYWORD_int.

Regular Expressions for Language Specification

• Definition: A compact notation to describe a set of strings (a language).

• Common Operators: | (alternation), * (Kleene star/closure), + (positive closure), ? (optional), . (any character), [ ] (character class), ^ (beginning), $ (end).

• Example (Odd a's and odd b's): (b*ab*a)*b*ab*a (One of many valid expressions).

Lexical Phase Errors

• Definition: Errors detected during scanning, before parsing.

• Common Types:

  • Illegal Character: Character not in the language's character set (e.g., @ in C).

  • Unterminated Comment/String Literal: EOF encountered before closing delimiter.

  • Overflow: Numeric constant too large for its intended type.

• Handling: Lexer reports error with line/column number and attempts recovery (e.g., skip to next whitespace).

II. Syntax Analysis

Predictive Parsing

• Type: Top-down, non-backtracking parsing using a parsing table.

• Requirements: Grammar must be LL(1) (Left-to-right scan, Leftmost derivation, 1 token lookahead). Requires elimination of left-recursion and left-factoring.

• Mechanism: Uses a stack and a parsing table M[A, a] (where A is non-terminal, a is terminal). Based on current stack top and input token, it decides to expand or match/report error.

LR Parsing (SLR, LALR, LR)

• Core: Bottom-up parsing using a shift-reduce algorithm with a state machine (constructed from an LR(0) or LR(1) automaton).

• Parsing Table: Consists of ACTION (shift/reduce/accept/error) and GOTO (state transition) functions.

Differences among SLR, LALR, and LR Parsers

Construction of LR Parsing Tables (General Steps)

1. Augment Grammar: Add S' -> S.

2. Build LR(0)/LR(1) Automaton: Create items (productions with •), compute closure, and goto transitions.

3. Define States: Each state is a set of items.

4. Fill ACTION Table:

   • Shift: On a (terminal), ACTION[s, a] = shift t if goto(s, a)=t.

   • Reduce: On a (terminal), ACTION[s, a] = reduce A->β if A->β is a completed item in s and a ∈ lookahead set.

   • Accept: On $, if S'->S• is in state s.

   • Error: Otherwise.

5. Fill GOTO Table: GOTO[s, A] = t for non-terminal A.

Syntactic Phase Errors

• Definition: Errors due to violation of grammar rules (missing/extra/misplaced tokens).

• Common Types:

  • Missing Symbol: if (x) y++; (missing ;).

  • Extra Symbol: int int x;.

  • Mismatched Delimiters: { ... ( ... } ... ).

  • Unexpected Token: switch (x) { case 1: ... default: ... } (missing case keyword).

• Handling: Parser reports error at synchronization point (often the unexpected token) and attempts recovery (e.g., panic mode: skip tokens until a synchronizing token like ;, }).

III. Semantic Analysis

Type Conversion

• Definition: Implicit or explicit conversion of one data type to another.

• Categories:

  • Widening (Promotion): int → float (safe, preserves value).

  • Narrowing (Casting): float → int (may lose precision).

• Implementation: Semantic actions in syntax-directed definitions. Type rules are applied during parsing/translation. Type checking ensures operands of operators are compatible.

Polymorphic Functions

• Definition: A single function name that can be applied to arguments of different types.

• Mechanism: The specific function to call is determined at compile-time (overloading) or run-time (overriding/generics).

• Example (C++): max(int a, int b) and max(float a, float b).

Function Overloading

• Definition: Defining multiple functions with the same name but different parameter types/lists in the same scope.

• Resolution: Compiler selects the best match based on argument types at the call site.

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

L-Attributed Definitions

• Definition: A class of syntax-directed definitions (SDDs) where attributes can be evaluated in a single left-to-right pass of a parse tree.

• Rule: For a production A -> X1 X2 ... Xn, each semantic rule for A's synthesized attributes can only depend on:

  • Attributes of X1...Xn.

  • Inherited attributes of A (passed from parent).

  • Inherited attributes of X1 (passed from left siblings X1...Xi-1).

• Use: Enables translation during top-down (predictive) or bottom-up (LR) parsing without building the full parse tree.

IV. Intermediate Code Generation

Three-Address Code (TAC)

• Definition: A sequence of statements of the form x = y op z (at most three addresses/operands per statement). It is a linearized representation of the syntax tree.

• Properties: Simple to generate and optimize. Uses temporary variables (t1, t2, ...).

• Example: a = b * -c + d → t1 = -c; t2 = b * t1; a = t2 + d;

Quadruples and Triples

• Quadruple: A 4-tuple (op, arg1, arg2, result). Result field holds address of result.

  • Example: (+, b, c, t1)

• Triple: A 3-tuple (op, arg1, arg2). No result field; result is referred to by its position in the triple array.

  • Example: (+, b, c) → result is triple (1).

  • Advantage: Avoids temporary names. Disadvantage: Hard to optimize (can't move statements easily).

Directed Acyclic Graphs (DAGs)

• Definition: A graph representation of a basic block where common subexpressions are shared (nodes represent values, edges represent computations).

• Construction for Expressions:

  1. Create a leaf node for each variable/constant.

  2. For an operator op with operands arg1, arg2:

     • If a node (op, arg1, arg2) already exists, use its existing node.

     • Else, create a new node (op, arg1, arg2).

  3. The final node represents the expression's value.

• Applications in Optimization:

  • Common Subexpression Elimination: Sharing nodes eliminates redundant calculations.

  • Constant Folding: If both children of an operator are constants, compute and replace with a constant node.

  • Dead Code Elimination: Nodes not reachable from the final output can be removed.

[!TIP] DAG Construction Example (Dec 2024):

Expression: a + a*(b-c) + (b-c)*d

1. Nodes: a, b, c, d.

2. Compute t1 = b - c → Node (-, b, c).

3. Compute t2 = a * t1 → Node (*, a, t1).

4. Compute t3 = t1 * d → Node (*, t1, d).

5. Compute t4 = a + t2 → Node (+, a, t2).

6. Final: t5 = t4 + t3 → Node (+, t4, t3).

Backpatching for Control Flow Statements

• Problem: Generating TAC for conditional/unconditional jumps (if, goto, ? :) where the target label is unknown until later.

• Solution: Use lists of unfilled jumps (true-list, false-list, next-list).

  1. For if (B) S1 else S2:

     • Evaluate B → B.true, B.false lists.

     • Backpatch B.true to S1.code.

     • Emit goto → add to S1.nextlist.

     • Backpatch B.false to S2.code.

     • S.nextlist = merge(S1.nextlist, S2.nextlist).

  2. Backpatch(list, target): Fills all (j____, _, _, _) in list with target.

Translation of Switch Statements

• Approach: Translate into a sequence of if-else if or a jump table.

• TAC Example:

  
  switch p+q {
  
    case 1: x=x+1; break;
  
    case 2: y=y+2; break;
  
    case 3: z=z+3; break;
  
    default: c=c-1;
  
  }
  
  

  • Compute t1 = p + q.

  • Emit if t1 == 1 goto L1

  • Emit if t1 == 2 goto L2

  • Emit if t1 == 3 goto L3

  • Emit goto Ldefault

  • L1: x = x + 1; goto Lend

  • L2: y = y + 2; goto Lend

  • L3: z = z + 3; goto Lend

  • Ldefault: c = c - 1

  • Lend:

V. Optimization

Basic Blocks and Flow Graphs

• Basic Block: A sequence of consecutive statements with:

  1. Single Entry: Control enters only at the first statement.

  2. Single Exit: Control leaves only after the last statement.

• Construction:

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

  2. Each leader starts a new block; block ends at next leader - 1.

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

Peephole Optimization

• Definition: Local optimization on a small sliding window (peephole) of target code.

• Common Patterns:

  | Inefficient Pattern | Optimized Replacement | | :--- | :--- | | MOV R1, R1 | (delete) | | MOV R1, c1; MOV R1, c2 | MOV R1, c2 | | ADD R1, 0 | (delete) | | MUL R1, 1 | (delete) | | LOAD R1, a; STORE a, R1 | *(delete)* | | JMP L1; L1: ... | *(delete JMP)* | | L1: ...; JMP L2; L2: ... | *(delete JMP L2)* |

Loop Optimizations

• Goal: Reduce execution time of loops (most critical for performance).

• Key Techniques:

  1. Loop Invariant Code Motion: Move calculations that produce the same result in every iteration outside the loop.

     • Example: for(i=0;i<n;i++) x = y*z + a; → Move y*z out.

  2. Induction Variable Elimination: Replace variables that change by a constant amount (induction variables) with a single variable and stronger loop exit condition.

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

     • Example: x = i * 4 → x = x + 4 (if x starts at 0).

  4. Loop Unrolling: Replicate loop body multiple times to reduce branch overhead.

  5. Loop Fusion/Fission: Combine/split loops for better cache locality.

Constant Folding and Propagation

• Constant Folding: Evaluate constant expressions at compile-time.

  • Example: 3 * 4 + 5 → 17.

• Constant Propagation: Replace variables known to hold constant values with the constants themselves.

  • Example: a = 5; b = a + 3; → b = 5 + 3 → (folding) b = 8.

• Application: Primarily performed on Three-Address Code or DAGs.

VI. Runtime Environment

Activation Records and Procedure Calls

• Activation Record (AR) / Stack Frame: Data structure for a single procedure invocation. Contains:

  • Return Address

  • Actual Parameters (or pointer to them)

  • Control Link (static link - pointer to caller's AR)

  • Access Link (non-local variable access)

  • Saved Machine Registers

  • Local Variables & Temporaries

• Procedure Call Steps:

  1. Caller pushes arguments and return address.

  2. Control transfers to callee.

  3. Callee allocates space for locals (adjusts stack pointer).

  4. Callee executes; on return, it deallocates locals, restores registers, jumps to return address.

  5. Caller may pop arguments.

Storage Allocation Strategies

• Stack Allocation:

  • Mechanism: LIFO allocation. ARs are pushed/popped with procedure calls/returns.

  • Use Case: Local variables in procedural languages (C, Pascal). Size known at compile-time.

  • Advantages: Efficient, automatic deallocation.

  • Disadvantages: No free(); cannot support arbitrary free().

• Heap Allocation:

  • Mechanism: Dynamic, non-LIFO. Memory managed by malloc/free (C) or new/delete (C++).

  • Use Case: Dynamic data structures (linked lists, trees), objects with lifetime beyond scope.

  • Management: Requires a memory manager (free lists, garbage collection).

  • Advantages: Flexible lifetime.

  • Disadvantages: Fragmentation, overhead, potential memory leaks.

Symbol Tables and Data Structures

• Purpose: Store information (attributes) about each identifier (name, type, scope, address, etc.).

• Required Operations: insert(name, attributes), lookup(name), delete(scope).

• Data Structures:

  1. Linear List (Unordered/Ordered): Simple, but lookup is O(n).

  2. Binary Search Tree (BST): lookup O(log n). Does not handle scopes well.

  3. Hash Table: Most common. lookup/insert average O(1). Uses hash function on identifier name. Collision handling via chaining (linked lists) or open addressing.

  4. Lexical Scoping: Implemented via symbol table stack (push on block entry, pop on exit). Each block/function has its own hash table/scope.

VII. Error Handling

Error Handling Phase

• Not a separate phase! Error detection/recovery is integrated into lexical, syntax, and semantic analysis phases.

• Goals: Report error clearly (location, type), recover to find more errors (avoid "cascade").

• Strategies:

  • Panic Mode: Skip tokens until a synchronizing token (;, }).

  • Phrase-Level Recovery: Insert/delete tokens to allow parsing to continue (requires knowledge of common errors).

  • Error Productions: Add erroneous productions to grammar (e.g., missing_semi -> /* empty */).

  • Global Correction: Find minimal sequence of changes (insert/delete/replace) to make program valid (expensive, rarely used).

Types of Compiler Errors

VIII. Compiler Phases Overview

[!TIP] Exam Focus: Be prepared to trace the output of each phase for a given small code snippet (as in Jun 2025). Know the exact structure of activation records, quadruples, and DAGs. Distinguish clearly between SLR, LALR, LR parsing. Explain loop optimization with a concrete example (e.g., invariant code motion). Contrast stack vs. heap allocation with use cases.