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

UNIT 4: COMPILER DESIGN - EXAM-FOCUSED SHORT NOTES

Based on analysis of Compiler Design - DEC 2024 and Compiler Design - JUN 2025 papers.

1. LEXICAL ANALYSIS (SCANNER)

Regular Expressions & Languages

• Definition: A regular expression is a pattern describing a set of strings (a regular language).

• Construction Example: Language of strings with odd number of 'a' and odd number of 'b'.

  • Odd 'a': a(ba*ba*)*

  • Odd 'b': b(ab*ab*)*

  • Combined (using intersection property): (a(ba*ba*)*) ∩ (b(ab*ab*)*) → Can be expressed as:

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

> [!TIP] Past papers frequently ask for construction of RE for specific parity conditions (odd/even counts).

Lexical Analyzer Implementation

• Role: Reads source characters, groups them into lexemes, and produces tokens (type, attribute).

• Recognizing Identifiers & Keywords:

  1. Pattern for identifiers (e.g., [a-zA-Z_][a-zA-Z0-9_]*).

  2. Lexeme is matched against identifier pattern.

  3. Conflict: Lexeme might match both an identifier pattern and a keyword (e.g., "if").

  4. Resolution: Maintain a keyword table. If lexeme matches a keyword, return that keyword token; else, return identifier token with pointer to symbol table entry.

• Lex/Flex Tool: Simple program structure:

  
  %{
  
  /* C declarations */
  
  %}
  
  %%
  
  pattern1    { action1 }  // e.g., [a-zA-Z_][a-zA-Z0-9]* { return IDENTIFIER; }
  
  pattern2    { action2 }  // e.g., "if" { return IF; }
  
  %%
  
  /* C support code */
  
  

• Input Buffering:

  • Purpose: Efficiently read ahead to identify longest possible lexeme.

  • Technique: Sentinel Method. Use a buffer with a special sentinel character (e.g., EOF) at the end of each buffer. Allows one-character lookahead without boundary checks.

  • Diagram:

    DiagramCANVAS: Two-buffer scheme with sentinel at end of each buffer, pointers lexemeBegin and forward.

Lexical Phase Errors

• Definition: Errors detected during scanning, before parsing.

• Examples:

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

  • Unterminated string literal ("hello).

  • Invalid character constant ('\n' is valid, '\k' is not).

2. SYNTAX ANALYSIS (PARSING)

Parsing Techniques & Grammars

• Top-Down (Predictive Parsing):

  • Starts with start symbol, derives strings.

  • Uses parsing table M[Non-terminal, Terminal] to choose production.

  • Construction: For grammar A → α | β:

    • For each terminal a in FIRST(α), add A → α to M[A, a].

    • If ε ∈ FIRST(α), for each b in FOLLOW(A), add A → α to M[A, b].

• Bottom-Up (LR Parsing):

  • Starts with input, reduces to start symbol.

  • Uses ACTION (shift/reduce) and GOTO (state transition) tables.

  • LR(0) Items: [A → α・β] where ・ marks parser's position.

Comparison: SLR vs LALR vs LR Parsers

[!TIP] Key Difference: SLR uses FOLLOW set for all reductions, which can cause false conflicts. LALR merges states with same core but preserves lookaheads, reducing spurious conflicts. LR(1) is precise but large.

SLR Parsing Table Construction (Example)

Grammar:

S → S + A | A

A → A B | B

B → B * | a | b

Steps:

1. Augment: S' → S.

2. Build LR(0) automaton (states 0,1,2,...).

3. ACTION Table:

   • If [A → α・aβ] in state i and goto(i,a)=j, set ACTION[i,a]=shift j.

   • If [A → α・] in state i, for each a ∈ FOLLOW(A), set ACTION[i,a]=reduce A→α.

   • If [S' → S・] in state i, set ACTION[i,$]=accept.

4. GOTO Table: goto(i, A) = j for non-terminal A.

5. Conflict Check: If any entry has multiple actions → grammar not SLR(1).

3. INTERMEDIATE CODE GENERATION

Three-Address Code (TAC)

• Definition: Intermediate representation where each instruction has at most three operands (e.g., x = y op z).

• Representation:

  1. Quadruples: (op, arg1, arg2, result). Easy for optimization, but temporary names are explicit.

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

  2. Triples: (op, arg1, arg2). No temporary names; refer to other triples by position. Can be explicit (store index) or implicit (pointer).

     • Example: Same as above → ( *, b, t1 ), ( +, (0), d ) where (0) refers to previous triple.

  • Difference Table:

    | Quadruples | Triples | | :--- | :--- | | Has a separate result field | No separate result; result is the triple itself | | Easier for code generation (direct addressing) | Saves space, but harder for optimization (need pointer chasing) | | Temporary names are explicit | Indirect referencing |

Directed Acyclic Graph (DAG)

• Definition: A graph representing an expression where interior nodes are operators and leaf nodes are variables/constants. Key Property: Acyclic → no cycles.

• Purpose: Optimize by eliminating common subexpressions and reducing number of operations.

• Construction (for expression E):

  1. Create leaf node for each variable/constant.

  2. For each operator, if an identical node (same operator, same children) exists, reuse it.

  3. Otherwise, create new node and attach.

• Example (DEC 2024):

$$E = a + a \times (b - c) + (b - c) \times d$$

*   Nodes: `a`, `b`, `c`, `d`, `-` (b,c), `*` (a, (-)), `+` (a, (*)), `*` ((-), d), `+` (previous +, last *)

*   **DAG**: `
DiagramCANVAS: Node 'a' and node (b-c) are shared. Final '+' node has two children: node1 (a + a*(b-c)) and node2 ((b-c)*d).
`

*   Optimized TAC: `t1 = b - c`, `t2 = a * t1`, `t3 = a + t2`, `t4 = t1 * d`, `a = t3 + t4` (assuming `a` is target).

Backpatching

• Purpose: Generate jumps for boolean expressions and flow-of-control statements (if, while) where target addresses are unknown until later.

• Mechanism:

  • Maintain a list of quadruple indices where address is pending.

  • For if B then S1:

    1. Generate TAC for B, leaving a placeholder if B goto _ → record index x in list L.

    2. Generate TAC for S1.

    3. **Backpatch(L, nextquad)** → fill all xwith address of first instruction ofS1`.

  • For if B then S1 else S2:

    1. B → list L1 for if B goto _.

    2. Generate S1 → next1.

    3. Generate goto _ → record index y in list L2.

    4. Backpatch L1 to next1.

    5. Generate S2 → next2.

    6. Backpatch L2 to next2.

• Example (JUN 2025): For while (B) S, maintain list for both entry and exit of loop.

4. CODE OPTIMIZATION

Fundamentals

• Definition: Transforming intermediate code to improve efficiency (speed, space) without changing meaning.

• Basic Block: A sequence of statements with:

  1. Single entry (first statement only).

  2. Single exit (last statement only).

  3. No jumps into the block, only out at the end.

  • Identification: Find leaders (first stmt, target of jump, stmt after jump). Each leader starts a new block.

Local Optimizations

• Constant Folding:

  • Evaluate constant expressions at compile time.

  • Example: x = 3 * 4 + 5 → x = 17.

• Peephole Optimization:

  • Examine a small window (peephole) of instructions and replace with faster/shorter sequence.

  • Techniques:

    1. Redundant load/store elimination: t1 = a; t2 = t1 → t2 = a.

    2. Unreachable code: goto L; ... L: x = y; (if L never reached).

    3. Algebraic simplifications: x = x * 1 → delete; x = x + 0 → delete.

    4. Sequence reduction: t1 = t2; t3 = t1 → t3 = t2.

  • Example: t1 = a * 0; t2 = t1 + b → t2 = b.

Loop Optimizations

• Code Motion (Loop Invariant Code Motion):

  • Move expressions that compute same value in every iteration outside the loop.

  • Example:

    
    while (i < n) {
    
        x = y * z + a[i];  // y*z is invariant
    
        ...
    
    }
    
    

    Optimized: t = y * z; while (...) { x = t + a[i]; }

• Induction Variable Elimination:

  • Replace multiple induction variables with a single one.

  • Example: i = 0; while (i < n) { j = i * 4; ... i = i + 1; } → Replace j with 4*i.

• Strength Reduction:

  • Replace expensive operations (multiplication, division) with cheaper ones (addition, shifts).

  • Example: x = i * 8 → x = i << 3.

Use of DAGs in Optimization

• DAG inherently eliminates common subexpressions.

• Also enables constant folding on leaf nodes and dead code elimination (nodes not used in final result).

5. RUNTIME ENVIRONMENT & MEMORY ALLOCATION

Activation Record (AR) / Frame

• Definition: Data structure managing a procedure call's runtime information.

• Contents (typical layout):

  
  [Actual Parameters]   // Caller pushes
  
  [Return Address]      // Caller pushes
  
  [Dynamic Link]        // Pointer to caller's AR (old frame pointer)
  
  [Local Variables]     // Callee allocates
  
  [Temporaries]         // Callee allocates
  
  [Saved Registers]     // Callee saves
  
  

  • Frame Pointer (FP): Points to a fixed location in AR (often to Dynamic Link).

  • Stack Pointer (SP): Points to top of stack.

• Example: For proc P(x) called from main, AR for P contains x, return addr to main, FP of main, locals of P.

Storage Allocation Strategies

[!TIP] Stack for control and non-recursive locals; Heap for persistent, dynamic-sized data.

Symbol Table Management

• Purpose: Store information about identifiers (name, type, scope, address, size).

• Data Structures:

  1. Linear List: Simple array/record. Search O(n). Good for small scopes.

  2. Hash Table: Key = identifier name. Buckets with chains. Average O(1) search/insert. Most common.

  3. Binary Search Tree: Ordered. Search O(log n). Supports range queries.

  4. Lexical Scoping: Nested symbol tables (each scope has a table, linked to enclosing scope). Used for block-structured languages (C, Pascal).

6. ERROR HANDLING

Compiler Error Handling Phase

• Function: Detect, report, and recover from errors in all phases to continue compilation.

• Strategies:

  1. Panic Mode: Discard tokens until a synchronizing token (e.g., ;, }) is found. Simple, prevents infinite loops.

  2. Phrase Level: Insert/delete tokens to synchronize at a particular grammar production. More sophisticated.

  3. Error Productions: Add special productions to grammar for common errors (e.g., missing semicolon).

  4. Global Correction: Find minimal changes to make program valid (expensive).

Error Types & Reporting

• Good Error Message: Should include line number, error type, offending token, and suggestion (e.g., "Line 10: expected ';' before '}' token").

7. PHASES OF COMPILATION (INTEGRATED VIEW)

Source: a = (x/y) * (y + x - z)

8. SPECIAL TOPICS & TOOLS (FREQUENT SHORT NOTES)

L-attributed Definitions

• Concept: Syntax-directed definition where attributes can be evaluated in one left-to-right pass of the parse tree.

• Rule: For production A → X1 X2 ... Xn, synthesized attributes of A can use any inherited attributes of Xs, but an inherited attribute of Xi can only depend on:

  1. Inherited attributes of A.

  2. Attributes of X1...X(i-1) (to the left).

• Usage: Enables top-down (recursive descent) or bottom-up (LR) translation schemes. Common for semantic actions in parsing.

Input Buffering in Lexical Analysis

• Purpose: Reduce I/O overhead and enable one-character lookahead for token recognition.

• Technique: Two-Buffer Scheme.

  • Divide input into two equal buffers.

  • Use sentinel (e.g., EOF) at end of each buffer.

  • Pointers: lexemeBegin (start of current token), forward (scans ahead).

  • When forward reaches sentinel, reload second half as first half.

  • Benefit: Boundary check only when crossing buffer halves.

Polymorphic Functions & Overloading

• Polymorphic Function: Function that works with arguments of multiple types (e.g., print(int), print(string)).

• Overloading Resolution:

  1. At compile time: Determine the most specific function matching argument types.

  2. Use type conversion (implicit) if exact match not found.

  3. If still ambiguous → compiler error.

• Example (JUN 2025): void f(int); void f(double); f(5); → calls f(int).

Peephole Optimization (Reiterated)

• Definition: Local optimization on a small sliding window of instructions.

• Common Reductions:

  • MOV R1, R1 → deleted.

  • ADD R1, 0 → deleted.

  • MUL R1, 1 → deleted.

  • LOAD R1, [x] followed by STORE [x], R1 → deleted if no intervening use of x.

  • JMP L1 followed by L1: → deleted.

Basic Blocks (Reiterated)

• Definition: A maximal sequence of consecutive statements with:

  • Single entry point (first statement only).

  • Single exit point (last statement only, which is a jump or fall-through).

• Identification Algorithm:

  1. Find leaders: First statement, targets of jumps, statements immediately after jumps.

  2. Each leader starts a new block.

  3. Block continues until next leader (exclusive).

• Use: Fundamental unit for control flow analysis and optimizations (like loop detection).

\boxed{\text{This document covers all high-frequency topics from DEC 2024 and JUN 2025 papers, aligned with the approved UNIT 4 blueprint.}}