Compiler Design (IT-603 (A)) - Unit 3 Short Notes

UNIT 3: Compiler Design – Exam-Focused Short Notes

1. Compiler Phases Overview

A compiler transforms source code into target code through sequential phases:

Single-pass vs. Multi-pass Compilation:

• Single-pass: Combines phases in one traversal; limited optimization; used for simple languages (e.g., early Pascal).

• Multi-pass: Separate passes for each phase; enables extensive optimization; standard for modern compilers.

[!TIP]

Past papers frequently ask for phase roles (DEC 2024, MAY 2023). Remember: lexical analysis is separated from syntax analysis for simplicity and efficiency.

2. Lexical Analysis

Role: First phase; converts raw character stream into meaningful tokens.

Token Specification:

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

• Keywords: Reserved words (e.g., if, while).

• Operators: +, -, *, /, =, etc.

• Constants: Integer, float, character, string literals.

• Strings: "([^"\\]|\\.)*" (handles escape sequences).

Regular Expressions for Complex Patterns:

• Odd number of a and odd number of b:

$$\boxed{(a(ba)^*b(ab)^*) + (b(ab)^*a(ba)^*)}$$

This regex generates strings with odd counts of both a and b (though it implies equal counts; a more complex DFA-based regex exists).

Finite Automata:

• NFA → DFA conversion via subset construction.

• DFA used for efficient token recognition (each state represents a set of NFA states).

LEX/Flex Structure:

%{

  // Declarations (C code)

%}

%%

  // Rules: pattern { action }

[a-zA-Z_][a-zA-Z0-9_]*  { return IDENTIFIER; }

[0-9]+                   { return INTEGER; }

"+"|"-"|"*"|"/"          { return OPERATOR; }

%%

  // User code

Input Buffering:

• Sentinel method: Use a sentinel character (e.g., \0) at buffer end to avoid bounds checks.

• Two-buffer scheme: Split input into two halves; allows lookahead for multi-character tokens (e.g., >=).

Separation from Syntax Analysis:

• Advantages: Simpler lexer (regex vs. CFG), efficiency (lexer can be hand-optimized), portability (tokenization independent of language syntax).

Lexical Errors:

• Invalid characters (e.g., @ in C).

• Unclosed strings/comments.

• Handling: Skip invalid character, report error with line number; often panic mode (discard until whitespace).

[!TIP]

DEC 2024 asked for lexical vs. syntactic errors. Lexical errors are character-level (invalid tokens); syntactic errors are structure-level (grammar violations).

3. Syntax Analysis

Context-Free Grammars (CFGs):

• Production rules: A → α where A is non-terminal, α is string of terminals/non-terminals.

• Parse Tree: Hierarchical representation of derivation.

• Ambiguity: Multiple parse trees for same string (e.g., E → E+E | E*E | id for id+id*id).

Parsing Techniques:

• Top-down: Start from start symbol; expand non-terminals.

  • Recursive Descent: Direct coding of productions; may require left-factoring.

  • Predictive Parsing: Use FIRST/FOLLOW sets to select production without backtracking (LL(1)).

• Bottom-up: Start from tokens; reduce to start symbol.

  • Shift-reduce: General framework; LR parsers are efficient implementations.

  • LR Parsing: Uses parsing table; most powerful (LR(1)/LALR(1)/SLR(1)).

FIRST and FOLLOW Sets:

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

• FOLLOW(X): Set of terminals that can appear immediately after X in a sentential form.

• Computation:

  1. FIRST(A):

     • If A → aα, add a.

     • If A → ε, add ε.

     • If A → Bα, add FIRST(B) (excluding ε); if ε ∈ FIRST(B), add FIRST(α).

  2. FOLLOW(A):

     • If S → αAβ, add FIRST(β) (excluding ε).

     • If S → αA or FIRST(β) contains ε, add FOLLOW(S).

     • For start symbol S, add $ (end marker).

Parsing Table Construction:

• SLR(1): Use FOLLOW(A) for reductions on A → α. May have conflicts if FOLLOW(A) contains multiple lookaheads.

• LALR(1): Merge LR(1) states with identical core (same item set without lookahead). Smaller tables than LR(1), fewer conflicts than SLR.

• LR(1)/CLR(1): Each item includes lookahead; largest tables, most powerful.

Comparison of SLR, LALR, LR:

Operator Precedence Parsing:

• Define precedence relations: a < b (a has lower precedence), a = b, a > b.

• Construct parse table from relations; shift-reduce based on precedence.

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

Ambiguity Resolution:

• Dangling else: Associate else with nearest if (precedence rule: else binds tighter).

• Grammar refactoring: Left-factoring, left-recursion elimination for predictive parsing.

[!TIP]

JUN 2025 & MAY 2023 frequently ask for parsing table construction (SLR/LR). Remember: SLR uses FOLLOW for reductions; LR(1) uses precise lookaheads.

4. Symbol Table Management

Role: Stores identifier attributes (name, type, scope, memory location, etc.) for all phases.

Attributes:

• Name: Identifier string.

• Type: int, float, array[10], etc.

• Scope: Global, local, block-nested.

• Memory: Offset in activation record, register allocation.

• Other: Line number, parameter count, etc.

Data Structures:

Collision Handling in Hash Tables:

• Chaining: Buckets as linked lists.

• Open Addressing: Linear probing, quadratic probing, double hashing.

Scope Management:

• Block-structured languages (e.g., C, Pascal): Use symbol table stack.

  • Enter new scope → push new table.

  • Exit scope → pop table; references resolve by searching from top down.

• Nested procedures: Use static links (access links) in activation records to reach non-local variables.

Operations:

• insert(name, attributes): Add new entry (check for duplicates in current scope).

• lookup(name): Search from current scope outward.

• delete(scope): Remove all entries for a scope.

[!TIP]

DEC 2024 asked for symbol table data structures. Hash tables are most common due to speed; collisions handled via chaining.

5. Syntax-Directed Translation and Semantic Analysis

Attribute Grammars:

• Synthesized Attributes: Computed from children’s attributes (bottom-up).

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

• S-attributed: Only synthesized attributes (e.g., expression evaluation).

• L-attributed: Synthesized + inherited with restrictions (inherited from left siblings only). Allows translation during top-down parsing.

Bottom-up Evaluation of S-Attributes:

• Postorder traversal of parse tree.

• Example: For E → E1 + T, E.val = E1.val + T.val.

Converting L-attributed to Translation Scheme:

• Inherited attributes passed as parameters.

• Example: For A → B C with inherited A.i, set B.i = A.i, C.i = f(B.s).

Dependency Graphs:

• Nodes: attribute occurrences.

• Edges: X.f → Y.g if g depends on f.

• Acyclic → evaluation order exists; cyclic → undefined semantics.

Syntax-Directed Translation Schemes:

• Expressions: E → E1 + T { E.val = E1.val + T.val }

• Assignments: S → id = E { gen(id.place = E.place) }

• Control Statements:

  • if: Use backpatching for boolean expression true/false lists.

  • while: S → while (B) S1; backpatch B.true to S1, B.false to next.

  • Switch-case: Generate jump table; each case label points to corresponding code.

Type Checking and Conversion:

• Implicit conversion (coercion): e.g., int to float in float f = 5;.

• Explicit conversion: Cast operators (e.g., (int)x).

• Overloading resolution: Select function/operator based on argument types during semantic analysis.

Backpatching:

• For boolean expressions and control flow:

  • True list: Jump targets when condition true.

  • False list: Jump targets when condition false.

• Process:

  1. Generate code with placeholders (_).

  2. Maintain lists for each boolean subexpression.

  3. For if (B) S: backpatch B.true to S; B.false to next.

  4. For while (B) S: backpatch B.true to S, B.false to after loop; loop backpatch.

[!TIP]

JUN 2025 asked for backpatching with flow-of-control statements. Remember: if uses two lists; while uses backpatch to loop start.

6. Intermediate Code Generation

Three-Address Code (TAC):

• Characteristics: At most three operands per instruction; temporary variables.

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

Representations:

Translation Examples:

• Arithmetic: d = (a-b) + (a-c) + (a-c) → quadruples with common subexpression elimination.

• Boolean: if (a < b || c < d) → B1: a < b? → true_list1, false_list1; B2: c < d? → true_list2, false_list2; merge true lists; false list = union.

• Control Structures:

  • if (B) S1 else S2:

    
    B.code → ... with true/false lists
    
    backpatch(B.true, S1.code)
    
    backpatch(B.false, S2.code)
    
    

  • switch p+q { case 1: x=x+1; case 2: y=y+2; ... } → generate jump table based on p+q value.

• Procedure Calls:

  • Parameter passing: call p(a,b) → param a; param b; call p.

  • Return value: return e → t = e; return t.

Directed Acyclic Graphs (DAGs):

• Definition: Directed graph with no cycles; nodes represent operations/values; leaves are variables/constants.

• Properties: Common subexpressions share nodes; enables optimization (e.g., CSE).

• Construction:

  1. Leaf nodes for variables/constants.

  2. Internal nodes for operators; if node exists, reuse it.

  3. Example:

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

 - Nodes: `a`, `b`, `c`, `d`, `t1=b-c`, `t2=a*t1`, `t3=a+t2`, `t4=t1*d`, `t5=t3+t4`.

 - DAG: `a` and `t1` reused; `t1` node used in `t2` and `t4`.

[!TIP]

DEC 2024 & JUN 2025 asked for DAG construction. Remember: reuse existing nodes for identical subexpressions; leaves are identifiers/constants.

7. Runtime Environments

Storage Allocation Strategies:

Activation Record (AR) Structure:

|------------------------|
| Actual parameters      | ← Caller pushes

|------------------------|
| Return address         |
|------------------------|
| Control link (dynamic) | → Caller’s AR

|------------------------|
| Access link (static)   | → Parent’s AR (for nested procs)

|------------------------|
| Local variables        |
|------------------------|
| Temporaries            |
|------------------------|

• Example: Nested procedure P inside Q; P accesses Q’s locals via static link.

Procedure Calls and Returns:

• Caller actions: Push args, return addr, old FP; set new FP.

• Callee actions: Save registers, allocate local vars.

• Return: Restore registers, pop AR, jump to return addr.

Parameter Passing Mechanisms:

• Call-by-value: Copy argument value; callee modifications invisible.

• Call-by-reference: Pass address; callee modifies original.

• Copy-restore (call-by-value-result): Copy in on entry, copy out on exit; issues with aliasing.

Non-local Variable Access:

• Static links: Each AR points to immediate enclosing scope’s AR; traverse links to find variable.

• Displays: Array of pointers to ARs of each nesting level; direct access.

Polymorphic Functions:

• Functions that work with multiple types (e.g., generics in Java).

• Implemented via type descriptors passed as hidden parameters.

Memory Management:

• Garbage Collection: Reclaim unreachable heap objects.

  • Mark-and-sweep: Mark reachable objects, sweep unmarked.

  • Copying: Divide heap, copy live objects to other half.

[!TIP]

DEC 2024 asked for activation records and stack vs. heap. Stack for procedures (LIFO); heap for dynamic objects (arbitrary order).

8. Code Optimization

Goals: Improve execution speed, reduce size/power without changing behavior.

Basic Blocks:

• Definition: Sequence of statements with single entry (first) and single exit (last); no jumps inside.

• Construction: Partition code at leaders (first statement, target of jump, after jump).

• Flow Graphs: Nodes = basic blocks; edges = control flow between exits/entries.

• Reducible Flow Graphs: Only loops with single entry (natural for structured programs); important for optimization (e.g., loop detection).

Optimization Techniques:

Loop Optimizations:

• Unrolling: Duplicate loop body to reduce branch overhead.

• Fusion: Combine adjacent loops with same bounds.

• Fission: Split loop to improve cache locality.

• Induction Variable Elimination: Replace variables that change linearly (e.g., i=i+1) with canonical form.

DAGs in Optimization:

• Construct DAG for basic block; eliminate common subexpressions (shared nodes).

• Example: For a + a*(b-c) + (b-c)*d, DAG shows b-c computed once.

Dependency Graphs:

• Data Dependencies: Flow (true), anti, output.

• Control Dependencies: Statement execution depends on predicate.

• Used to guide reordering safely.

[!TIP]

JUN 2025 asked for peephole optimization; MAY 2023 asked for loop optimization. Remember: constant folding is a form of local optimization; loop unrolling reduces branch cost.

9. Error Handling

Error Types:

• Lexical: Invalid characters, malformed numbers.

• Syntactic: Missing ;, mismatched parentheses.

• Semantic: Type mismatch, undeclared variable.

• Logical: Infinite loop (not caught by compiler).

Detection Points:

• Lexical: During tokenization.

• Syntactic: During parsing (parse error).

• Semantic: During semantic analysis (type checking, scope resolution).

Recovery Strategies:

Error Reporting:

• Meaningful messages: "Unexpected token '+' at line 15".

• Include line number, column, error type.

• Avoid cascading errors (recover quickly).

Dedicated Error Handling Phase?

• Not a separate phase; integrated throughout compilation.

• Error recovery often in parser (syntax-directed).

[!TIP]

DEC 2024 asked about error handling phase. Emphasize: recovery strategies are embedded in parser; panic mode is simplest.

10. Additional Specialized Topics

Bootstrapping:

• Concept: Self-compilation; compiler written in its own language.

• Stages:

  1. Write compiler C1 in machine code (or another language).

  2. Use C1 to compile C2 (written in source language) → C2 in machine code.

  3. Now C2 can compile itself (C2 compiles C2).

• Cross-compiler: Runs on machine A, generates code for machine B.

Operator Precedence Parsers:

• Define precedence relations: a < b (a has lower precedence), a = b, a > b.

• Parse table: Rows/columns are terminals; entries: shift (<, =), reduce (>), blank (error).

• Example: For E → E+E | E*E | id, * > +, so id * id + id reduces id*id first.

Type Conversion:

• Implicit (coercion): Compiler inserts conversions (e.g., int → float in float f = 5;).

• Explicit: Cast operators (e.g., (int)3.14).

• Example: In int i; float f; i = f; → implicit conversion float→int (may lose precision).

Function Overloading:

• Multiple functions with same name but different parameter types.

• Resolution: During semantic analysis, select best match based on argument types (e.g., print(int) vs print(float)).

• Ambiguity: If no unique best match, error.

Reducible Flow Graphs:

• Definition: Flow graph where every cycle has a single entry node (loop header).

• Properties: Natural for structured programs (no goto into loops).

• Importance: Enables loop optimization (e.g., code motion, induction variables).

• Comparison: Non-reducible graphs (from arbitrary goto) hinder optimization.

Input Buffering:

• Beyond sentinel method: Two-buffer scheme with lexeme pointer and forward pointer.

• Allows lookahead for multi-character tokens (e.g., >=, >>=).

• Sentinel avoids bounds check but requires copying when buffer wraps.

[!TIP]

JUN 2025 asked for reducible flow graphs and input buffering. Reducible graphs have single-entry loops; input buffering uses two buffers for efficient lookahead.