UNIT 5: Compiler Design – Short Notes

1. Lexical Analysis

Role and Importance

• First phase of compilation.

• Reads input characters, groups them into lexemes, and produces tokens.

• Removes whitespace/comments, handles error reporting for invalid characters.

• Benefits of separation: Simplifies syntax analysis, improves compiler modularity, allows use of specialized tools (Lex/Flex).

Finite Automata (FA) for Token Recognition

• NFA (Non-deterministic): Multiple transitions on same input, ε-transitions allowed.

• DFA (Deterministic): Single transition per input, no ε-moves. More efficient for implementation.

• Regular expressions are converted to NFA (Thompson's construction), then to DFA (subset construction), minimized for efficiency.

Example: Regular expression for strings with odd number of a and odd number of b:

$$(a(ba)^*b \mid b(ab)^*a) \cup (a(ba)^*a(ba)^*b \mid b(ab)^*b(ab)^*a)$$

A simpler approach: Odd a and odd b implies total length is even, and both counts odd. Can be represented as:

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

Regular Expressions for Language Specification

• Used to describe token patterns (identifiers, numbers, operators).

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

Lex/Flex Implementation

• Structure of a Lex program:

  
  definitions
  
  %%
  
  rules
  
  %%
  
  user subroutines
  
  

• Recognizing identifiers and keywords:

  • Define pattern for identifiers: [a-zA-Z_][a-zA-Z0-9_]*

  • Keywords listed explicitly before identifier pattern to give them precedence.

  • Example:

    
    "if"    { return IF; }
    
    "else"  { return ELSE; }
    
    [a-zA-Z_][a-zA-Z0-9_]* { yylval = lookup(yytext); return IDENTIFIER; }
    
    

Input Buffering

• Sentinel method: Use a special character (e.g., \0) to mark end of buffer, avoiding bounds checks.

• Two-buffer scheme: Split input into two equal halves; when pointer reaches end of first, reload second and switch. Handles arbitrarily long tokens efficiently.

2. Syntax Analysis

Overview of Parsing Techniques

Predictive Parsing

• Predictive parsing table: M[Non-terminal, Terminal] → production or error.

• Construction:

  1. Compute FIRST and FOLLOW sets.

  2. For production 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].

• Example: Grammar A → (B) | a, B → B,B | A. Not LL(1) due to left recursion in B.

Operator Precedence Parsing

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

• Algorithm:

  1. Push $ (end marker) onto stack.

  2. Let a = current input token, b = top stack terminal.

  3. If b <· a, shift a onto stack.

  4. If b ·> a, pop b and reduce by a production A → β where β contains no non-terminals.

  5. If b = a, shift/reduce for matching = (e.g., parentheses).

• Limitation: Only works for operator grammars (no two adjacent non-terminals in RHS).

LR Parsing Family

• General LR:

  • States represent LR(1) items: [A → α·Bβ, a] (dot position, lookahead a).

  • Canonical collection of LR(1) items via GOTO and CLOSURE.

  • Parsing table: ACTION[i, a] = shift/reduce/accept/error; GOTO[i, A] = state.

SLR(1)

• Uses FOLLOW of LHS non-terminal for reduce actions.

• Construction:

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

  2. For reduce item A → α· in state i, for each a in FOLLOW(A), set ACTION[i, a] = reduce A → α.

• Check SLR(1) correctness: No conflicts in ACTION table. Weaker than LALR/CLR.

LALR(1)

• Merge LR(1) states with same core (same LR(0) item) but different lookaheads.

• Combines lookaheads of merged states.

• Comparison:

  | Parser | States | Power | Example | |--------|--------|-------|---------| | SLR(1) | Fewest | Weakest | May have spurious conflicts | | LALR(1) | Moderate | Intermediate | Used in Yacc/Bison | | CLR(1) | Most | Strongest | No false conflicts |

Canonical LR(1) / CLR(1)

• Full LR(1) items with lookaheads.

• No state merging; most precise.

• Larger tables but avoids LALR ambiguities.

Parse Tree for Ambiguous Grammar

• Grammar: E → E+E | E*E | a | b | c

• Ambiguity: a+b*c has two parse trees (left/right associativity, precedence).

• Resolution: Use precedence (* > +) and associativity (left for both) to get unique tree:

  
      E
  
     /|\
  
    E + E
  
    |   |
  
    a   E
  
        |\
  
        E * E
  
        |   |
  
        b   c
  
  

FIRST and FOLLOW Sets

• FIRST(X):

  1. If X is terminal, FIRST(X) = {X}.

  2. If X → ε is production, add ε to FIRST(X).

  3. If X → Y₁...Yₖ, add FIRST(Y₁) (excluding ε). If all Yᵢ derive ε, add ε.

• FOLLOW(A):

  1. If S is start symbol, add $ to FOLLOW(S).

  2. If B → αAβ, add FIRST(β) \ {ε} to FOLLOW(A).

  3. If B → αA or B → αAβ with ε ∈ FIRST(β), add FOLLOW(B) to FOLLOW(A).

Error Handling in Syntax Analysis

• Syntactic errors: Missing operators, unmatched parentheses, unexpected token.

• Recovery strategies:

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

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

  • Error productions: Augment grammar with productions for common errors.

3. Syntax-Directed Translation & Intermediate Code

Attribute Grammars

• S-attributed: Only synthesized attributes (computed from children).

  • Evaluated in bottom-up parsing.

  • Example: E → E₁ + T { E.val = E₁.val + T.val }

• L-attributed: Synthesized + inherited attributes (from parent/siblings).

  • Inherited attributes passed left-to-right during parsing.

  • Can be evaluated in both top-down and bottom-up.

Bottom-up Evaluation of Attributes (S-attributed)

• Each parse tree node has a synthesized attribute.

• Values computed as reduction occurs in LR parsing.

• Example:

  
  E → E₁ + T
  
  E.val = E₁.val + T.val
  
  

  When reducing E₁ + T to E, use values from E₁ and T.

Translation Schemes for Switch/Case

• Syntax-directed translation:

  
  switch (E) {
  
    case c₁: S₁;
  
    case c₂: S₂;
  
    ...
  
    default: S_d;
  
  }
  
  

• Intermediate code:

  
  E.code
  
  if E ≠ c₁ goto L1
  
  S₁.code
  
  goto L_end
  
  L1: if E ≠ c₂ goto L2
  
  S₂.code
  
  goto L_end
  
  ...
  
  L_d: S_d.code
  
  L_end:
  
  

Intermediate Code Forms

Directed Acyclic Graph (DAG)

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

• Construction:

  1. Leaf nodes for variables/constants.

  2. Interior nodes for operators; if identical operator and operands exist, reuse node.

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

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

  DAG: Node for t1 used twice; a used twice but as different operands.

Backpatching

• For boolean expressions and flow-of-control (if, while).

• Boolean expressions generate jumps with unfilled addresses.

• Backpatching list: Maintain lists of quadruple indices needing addresses.

• Example for if (B) S:

  1. B.code generates (jtrue, B.true, _, _) and (jfalse, B.false, _, _).

  2. S.code generated.

  3. Backpatch B.true list to start of S.code.

  4. B.false list points to next instruction after S.

Type Conversion

• Implicit/explicit conversions in intermediate code.

• Example: int i; float f; f = i + 2.5;

  • Generate TAC: t1 = inttofloat(i), t2 = 2.5, t3 = t1 + t2, f = t3.

4. Runtime Environments & Storage Allocation

Symbol Tables

• Purpose: Store identifier attributes (type, scope, address, etc.).

• Scope management: Nested scopes via stack of symbol tables or static parent links.

• Data structures:

  | Structure | Search Time | Insert Time | Notes | |-----------|-------------|-------------|-------| | Linear list | O(n) | O(1) | Simple, slow for large | | Binary Search Tree | O(log n) | O(log n) | Ordered | | Hash table | O(1) avg | O(1) avg | Most common, collisions handled |

Activation Records (AR)

• Structure:

  
  [Return address]
  
  [Dynamic link (old AR pointer)]
  
  [Parameters]
  
  [Local variables]
  
  [Temporaries]
  
  

• Example: Nested procedure P calls Q:

  
  AR for P:
  
    ...
  
    AR for Q:
  
      return addr
  
      dynamic link → AR P
  
      params
  
      locals
  
  

Storage Allocation Strategies

Parameter Passing Mechanisms

• Call-by-value: Copy argument value.

• Call-by-reference: Pass address; callee modifies caller's variable.

• Call-by-value-result (copy-in copy-out): Like value, but copy back on return.

Polymorphic Functions & Overloading

• Polymorphic: Function works with multiple types (e.g., print(int), print(float)).

• Overloading: Same name, different parameter types.

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

5. Code Optimization

Basic Blocks

• Definition: Sequence of statements with single entry (first) and single exit (last). No jumps inside except at end.

• Construction:

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

  2. Form block from leader to next leader-1.

• Flow graph: Nodes = basic blocks; edges = possible control flow.

• Reducible flow graph: Can be constructed by repeatedly splitting edges; most programming languages yield reducible graphs.

Local Optimizations (within a basic block)

Loop Optimizations

1. Code motion (loop-invariant code motion):

   • Move statements that compute same value each iteration outside loop.

   • Example:

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

     → Move x = y*z before loop.

2. Induction variable simplification:

   • Replace induction variables with linear functions of loop counter.

   • Example: j = i + 1 inside loop; replace uses of j with i+1.

3. Strength reduction:

   • Replace expensive operations (multiplication) with cheaper (addition).

   • Example: x = i * 8 → x = i << 3 (bit shift).

Peephole Optimization

• Principle: Examine small window (peephole) of target code for redundant/inefficient patterns.

• Examples:

  • Redundant load/store: MOV R1, R2; MOV R2, R1 → delete.

  • Algebraic: x = x * 1 → delete.

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

Global Data Flow Analysis (Brief)

• Purpose: Gather information across basic blocks for global optimizations (e.g., reaching definitions, live variables).

• Equations: For each node n, IN[n] = ∪ OUT[p] for predecessors p; OUT[n] = f(IN[n], n).

• Used for CSE, dead code elimination across blocks.

6. Error Handling

Lexical Phase Errors

• Examples:

  • Invalid character: @ in identifier.

  • Unterminated string: "hello (no closing ").

  • Illegal escape sequence: \x in string.

• Recovery: Delete/replace invalid char, report line/column.

Syntactic Phase Errors

• Examples:

  • Missing operator: a b + c (expected * or + between a and b).

  • Unmatched parentheses: (a + b (missing )).

  • Unexpected token: if x then y else (missing statement after else).

• Recovery: Panic mode (skip to ; or }), error productions (e.g., S → error).

7. Additional Specialized Topics

Bootstrapping

• Definition: Using a compiler to compile itself.

• Methods:

  • Cross-compilation: Compile on machine A for machine B.

  • Bootstrap: Write simple compiler (in machine code) for language L, then use it to compile more advanced compiler written in L.

Dependency Graphs in Optimization

• Nodes = statements; edge S₁ → S₂ if S₂ uses variable defined in S₁.

• Used for code motion: A statement can be moved out of loop if all its dependencies are loop-invariant and it dominates all uses.

Input Buffering (Detailed)

• Two-buffer scheme:

  • Input divided into two halves of size N.

  • lexemeBegin and forward pointers.

  • When forward reaches end of first half, reload second half and swap.

  • Sentinel: Special char (e.g., \0) at buffer end to avoid checking bounds on each character read.

Operator Precedence Parser (Detailed Algorithm)

1. Initialize stack with $.

2. While input not $:

   • Let a = current input token, b = top stack terminal.

   • If b <· a: shift a onto stack.

   • If b ·> a: pop b and reduce by production A → β where β is string of terminals popped.

   • If b = a: shift/reduce for matching = (e.g., parentheses).

   • Else: syntax error.

3. Accept when stack = $$\displaystyle ` and input = ` $$.

Exam Tips:

• Regular expressions: Practice converting odd/even constraints.

• LR tables: Always compute canonical collection first; SLR uses FOLLOW, LALR/CLR use lookaheads.

• DAG construction: Identify common subexpressions by matching operator and operands (order matters for non-commutative).

• Backpatching: Maintain lists for true/false in boolean expressions; for if, backpatch true list to then-part.

• Activation record: Know layout for nested procedures (static vs dynamic links).

• Loop optimization: Code motion requires loop-invariant check (no definitions in loop, no uses before statement).