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

I. Lexical Analysis

Input Buffering

• Purpose: To efficiently read the source program character by character, minimizing I/O operations.

• Implementation: Uses two buffers (lexemeBegin, forward pointers) of size N. When forward reaches end of buffer, the buffer is reloaded.

• Sentinels: A special character (EOF) is placed at the end of each buffer to avoid checking boundary conditions on every character read.

• Scheme: lexemeBegin marks start of current token, forward scans ahead. After token recognition, lexemeBegin is advanced to forward.

Token Recognition

• Identifiers vs Keywords:

  • Pattern: Identifiers typically match [a-zA-Z_][a-zA-Z0-9_]*.

  • Process: Lexical analyzer first checks if the scanned string matches any keyword in a fixed table. If not, it's classified as an identifier.

  • Example: int → keyword; myVar123 → identifier.

• Lexical Patterns & Finite Automata: Each token pattern is represented by a Regular Expression and converted to a Deterministic Finite Automaton (DFA) for efficient recognition.

Regular Expressions

• Formal Representation: Concise notation for token patterns (e.g., digit -> [0-9], id -> letter (letter|digit)*).

• Example (Exam Focus): Regular expression for strings with odd number of a and odd number of b:

$$ (aa^*bb^* + bb^*aa^*)(aa^* + bb^*)^* $$

*   `aa*bb*` = odd `a`s followed by odd `b`s.

*   `bb*aa*` = odd `b`s followed by odd `a`s.

*   `(aa* + bb*)*` = any number (even/zero) of additional odd `a` or odd `b` blocks.

Lexical Errors

• Detection: Character not belonging to any token pattern (e.g., @ in C).

• Handling: Report error, discard offending character, and resume scanning.

Lex Tool

• Purpose: Generates lexical analyzers from regular expression specifications.

• Simple Program (Identifier Recognition):

  
  %{
  
  #include <stdio.h>
  
  %}
  
  %%
  
  [a-zA-Z_][a-zA-Z0-9_]*   { printf("Identifier: %s\n", yytext); }
  
  [ \t\n]+                 ; /* ignore whitespace */
  
  .                        { printf("Invalid char: %c\n", *yytext); }
  
  %%
  
  int main() { yylex(); return 0; }
  
  

[!TIP] Exam Tip: For regex problems, break into cases (odd a/odd b, odd b/odd a) and handle interleaving with Kleene star.

II. Syntax Analysis (Parsing)

Parsing Techniques

LR Parsing Variants (Detailed Comparison)

[!TIP] Common Pitfall: SLR uses FOLLOW(A) for all reductions of A, while LALR/LR(1) use precise lookaheads. SLR may have spurious conflicts.

SLR Parsing Table Construction (Example Steps)

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

2. Build LR(0) Items: Compute closure and goto.

3. Construct ACTION/GOTO:

   • Shift: On a (terminal), goto state j → ACTION[i, a] = shift j.

   • Reduce: For item A -> β. in state i, for each a in FOLLOW(A), ACTION[i, a] = reduce A->β.

   • Accept: On $$\displaystyle ` for `S' -> S.` → `ACTION[i, $$] = accept.

   • Goto: GOTO[i, A] = j for item A -> β.Aγ.

4. Check for Conflicts: Multiple actions for same cell → grammar not SLR(1).

Syntax Errors & Recovery

• Detection: Parser encounters no valid action (blank entry in table).

• Recovery Strategies:

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

  • Phrase Level: Insert/delete tokens to make parser progress.

  • Error Productions: Augment grammar with common error patterns.

Predictive Parsing

• Table (M[A, a]): For non-terminal A and terminal a, entry is production A -> α if a is in FIRST(α), or A -> ε if ε in FIRST(α) and a in FOLLOW(A).

• Construction: Compute FIRST and FOLLOW sets. Fill table accordingly.

• Requirement: Grammar must be non-left-recursive and non-ambiguous.

III. Semantic Analysis

Type Systems

• Type Checking: Verifies operator-operand type compatibility.

  • Example: int + float → convert int to float (type coercion).

• Type Conversion:

  • Implicit (Coercion): Done by compiler (e.g., int to float).

  • Explicit (Cast): Programmer-specified (e.g., (float)i).

Syntax-Directed Translation

• Attributes: Values associated with grammar symbols.

  • Synthesized: Computed from children (bottom-up).

  • Inherited: Passed from parent/siblings (top-down).

• L-attributed Definitions: A restricted form where inherited attributes can only come from left siblings and parent. Allows top-down evaluation (used in predictive parsers).

Intermediate Code Generation: Three-Address Code (TAC)

• Form: x = y op z (at most 3 addresses per instruction).

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

  
  t1 = p + q
  
  if t1 == 1 goto L1
  
  if t1 == 2 goto L2
  
  if t1 == 3 goto L3
  
  goto L4
  
  L1: x = x + 1
  
  L2: y = y + 2
  
  L3: z = z + 3
  
  L4: c = c - 1
  
  

  Note: Fall-through behavior implies cases are not mutually exclusive jumps unless break is present.

Intermediate Representations: Quadruples vs Triples

Name Resolution: Function Overloading

• Resolution Time: Compile-time (static binding).

• Process: Based on function signature (name + parameter types). Compiler selects the most specific matching function.

• Example: print(int) vs print(string) → call resolved by argument types.

IV. Intermediate Code Representation & Optimization

Directed Acyclic Graphs (DAGs)

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

  • Leaf nodes are identifiers/constants.

  • Interior nodes are operators.

  • Common subexpressions are represented by a single node.

• Construction (Exam Focus): Build from expression using hash table to detect identical subexpressions (same operator, same children).

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

  
  Step 1: t1 = b - c
  
  Step 2: t2 = a * t1
  
  Step 3: t3 = t1 * d
  
  Step 4: a + t2 + t3
  
  DAG: Node `-` (b,c) shared by `*` (a, -) and `*` (-, d).
  
  

• Application: Common Subexpression Elimination (CSE). If node exists, reuse it instead of recomputing.

Basic Blocks

• Definition: A sequence of consecutive statements with:

  1. Single entry (first statement executed).

  2. Single exit (last statement causes jump).

• Formation: Partition code by leaders (first statement, target of jump, statement after jump). Each leader starts a new block.

• Control Flow Graph (CFG): Nodes = basic blocks; edges = possible flow of control.

Optimization Techniques

• Constant Folding: Evaluate constant expressions at compile time.

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

• Loop Optimization:

  • Invariant Code Motion: Move loop-invariant calculations outside.

    
    for(i=0; i<n; i++) {
    
        x = y*z + a[i]; // y*z is invariant
    
    }
    
    // Optimized:
    
    t = y*z;
    
    for(i=0; i<n; i++) x = t + a[i];
    
    

  • Strength Reduction: Replace expensive op with cheaper one (e.g., x*8 → x<<3).

  • Loop Unrolling: Duplicate loop body to reduce jump overhead.

• Peephole Optimization: Local optimization on small instruction window (2-5 instructions).

  • Examples:

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

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

    3. Jump-to-jump: goto L1; L1: goto L2 → goto L2.

V. Runtime Environment & Storage Management

Activation Records (AR)

• Definition: The data structure created at procedure call to manage execution of that call.

• Components (Typical Layout):

  
  [Actual Parameters]
  
  [Return Address]
  
  [Control Link (Access Link)]
  
  [Saved Machine Registers]
  
  [Local Variables]
  
  [Temporaries]
  
  

• Example: For proc(x, y) called from main, AR contains values for x, y, return address to main, pointer to main's AR (control link), and proc's locals.

Storage Allocation Strategies

Procedure Calls

• Call Mechanism:

  1. Caller evaluates actual parameters.

  2. Caller pushes return address, old FP, and possibly parameters onto stack.

  3. Control transfers to callee.

  4. Callee sets up its AR (FP points to old FP).

• Return Mechanism:

  1. Callee places return value (if any) in designated location.

  2. Callee restores caller's registers, pops AR, jumps to return address.

• Parameter Passing Methods:

  • Pass-by-Value: Copy actual value.

  • Pass-by-Reference: Copy address (callee can modify actual).

  • Pass-by-Value-Result (Copy-in/Copy-out): Copy in at call, copy out at return.

Advanced Runtime Features

• Polymorphic Functions (Runtime Handling):

  • Definition: Function that behaves differently based on runtime type of arguments.

  • Runtime Handling: Requires dynamic dispatch (e.g., virtual function tables in C++). Compiler generates code to look up correct function address at runtime.

• Function Overloading (Compile-time Resolution):

  • Resolved during compilation based on static types of arguments. No runtime overhead.

VI. Symbol Table Management

Purpose & Scope

• Purpose: Central repository for information about identifiers (name, type, scope, address, etc.). Used in all phases (lexical to code generation).

• Scope: Supports nested scopes (functions within functions) and separate namespaces (labels, variables).

Data Structures

• Organization for Scopes: Stack of hash tables (one per scope). On entering scope, push new table; on exit, pop. Lookup searches from top of stack downward.

VII. Error Handling

Error Detection Phases

Error Reporting & Recovery

• Reporting: Should be precise (line/column), understandable, and non-intrusive.

• Recovery Strategies:

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

  • Phrase Level: Insert/delete single token to correct error (e.g., missing ;). Requires local correction.

  • Error Productions: Add grammar rules like stmt -> error ; to catch and recover from common errors.

  • Global Correction: Minimum number of insertions/deletions to make program valid (expensive, rarely used).

[!TIP] Exam Focus: Distinguish lexical (invalid chars) vs syntactic (structure) vs semantic (meaning) errors with examples.

VIII. Compiler Phases: Integrated Example

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

t1 = x / y

t2 = x - z

t3 = y + t2

t4 = t1 * t3

a = t4

``` |

| 5. Optimization (DAG/CSE) | DAG: t2 = x - z is unique. No common subexpressions. Constant folding not applicable. | | 6. Code Generation | Target assembly (e.g., x86): ```

mov eax, x

cdq

idiv y      ; eax = x/y

mov ebx, eax

mov eax, x

sub eax, z

add eax, y

imul eax, ebx

mov a, eax

``` |

[!TIP] Exam Question Pattern: "Show output generated by each phase" → List tokens, show parse tree/AST, show TAC, mention optimizations applied, show target code snippet.

Summary of High-Frequency Exam Topics (from DEC 2024 & JUN 2025):

1. DAG Construction (2+ questions) – Practice with expressions containing common subexpressions like (b-c).

2. Loop Optimization (2+ questions) – Know invariant code motion, strength reduction with clear examples.

3. SLR/LALR/LR Comparison & Tables (2+ questions) – Be able to construct SLR table for small grammar.

4. Activation Records & Storage Allocation – Compare stack vs heap, draw AR diagram.

5. Three-Address Code (TAC) – Generate for switch, if-then-else, loops. Know quadruple/triple formats.

6. Backpatching – For boolean expressions and if/while (fill in jump addresses).

7. Basic Blocks – Identify from code, draw CFG.

8. Constant Folding & Peephole – Apply to small instruction sequences.

9. Predictive Parsing – Construct table for given grammar (eliminate left recursion first).

10. Lexical Analysis – Write Lex program for identifiers, explain sentinel buffering.