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

UNIT 1: COMPILER DESIGN - EXAM-FOCUSED SHORT NOTES

1.0 INTRODUCTION TO COMPILERS & OVERVIEW

Definition: A compiler is a program that translates source code written in a high-level language into an equivalent target language (usually machine code or assembly).

Phases of a Compiler (with Primary Tasks):

1. Lexical Analysis (Scanner): Reads input stream, groups characters into tokens (identifiers, keywords, operators), removes whitespace/comments.

2. Syntax Analysis (Parser): Checks if token stream follows the language's grammar rules (CFG). Builds a parse tree or abstract syntax tree (AST).

3. Semantic Analysis: Checks for semantic consistency (type checking, scope rules). Uses a symbol table. Generates intermediate code annotations.

4. Intermediate Code Generation: Produces a platform-independent, low-level representation (e.g., Three-Address Code (TAC)).

5. Code Optimization: Improves intermediate code for efficiency (speed, size). Can be local or global.

6. Code Generation: Maps optimized intermediate code to target machine code. Manages storage allocation (registers, memory).

7. Symbol Table Management: Centralized data structure storing information about identifiers (name, type, scope, address).

8. Error Handling: Detects, reports, and recovers from errors at various phases.

[!TIP] Exam Focus: Be prepared to list phases in order and state the key output of each. Questions often ask for "phase-wise output" for a given expression.

Compiler Construction Tools:

• Lex/Flex: Generates lexical analyzers from regular expressions.

• Yacc/Bison: Generates parsers (LALR(1)) from context-free grammars.

• JavaCC, ANTLR: Modern, powerful parser generators for Java/other languages.

Passes & Bootstrapping:

• Single-pass Compiler: Combines analysis and synthesis in one pass. Simple, but limited optimization. Used for scripting languages.

• Multi-pass Compiler: Separate phases (passes). Enables complex optimization and better error recovery. Most production compilers.

• Bootstrapping: Technique of writing a compiler in the language it compiles. Involves stages:

  1. Write simple compiler (C0) for a subset of language L in another language.

  2. Use C0 to compile a more advanced compiler C1 (written in L) for full L.

  3. Now C1 can compile itself and other L programs.

2.0 LEXICAL ANALYSIS (SCANNER)

Role & Function:

• Input Buffering: Uses two buffers (lexemeBegin, forward) with a sentinel character to efficiently read ahead without system calls.

  
  [ Buffer 1 ] [ Buffer 2 ]
  
  ^            ^
  
  lexemeBegin  forward
  
  

• Token Recognition: Matches patterns defined by regular expressions. Keywords are recognized separately from identifiers (often via a hash table lookup).

Regular Expressions (RE) & Finite Automata (FA):

• RE to NFA: Using Thompson's construction (ε-transitions).

• NFA to DFA: Subset construction method.

• DFA Minimization: Merge equivalent states (using partitioning algorithm).

• Pattern Matching Example: Language of strings with odd number of a and odd number of b:

$$L = \{ w \in \{a,b\}^* \mid \#_a(w) \text{ odd} \land \#_b(w) \text{ odd} \}$$

**RE:** `(b(a|b)*a(a|b)*b(a|b)*)|(a(a|b)*b(a|b)*a(a|b)*)`

Lex/Flex Program Structure:

%{

/* C declarations (token definitions, includes) */

%}

/* Regular Expression Definitions */

DIGIT   [0-9]

ID      [a-zA-Z_][a-zA-Z0-9_]*

%%

{DIGIT}+      { yylval.num = atoi(yytext); return NUM; }

{ID}          { if (isKeyword(yytext)) return KEYWORD; else return ID; }

"+"|"-"|"*"|"/" { return yytext[0]; }

.             { /* Handle illegal character */ }

%%

/* User-defined functions (e.g., isKeyword) */

[!TIP] Common Pitfall: Keywords must be checked before identifiers in the rules section, or they will be tokenized as ID.

Lexical Errors & Handling:

• Error Types: Illegal character, unterminated comment/string, token too long.

• Recovery Strategies:

  • Panic Mode: Discard characters until a valid delimiter (whitespace, semicolon) is found.

  • Deletion: Delete a problematic character and continue.

  • Insertion: Insert a missing character (e.g., quote) and continue.

Key Distinction: Identifier vs. Keyword

• Identifier: User-defined name (variable, function). Pattern: [a-zA-Z_][a-zA-Z0-9_]*. Recognized by matching the general pattern, then checking against a keyword table.

• Keyword: Reserved word with fixed meaning (if, while, int). Recognized by having explicit rules before the identifier rule in Lex, or via a symbol table lookup that returns a specific token type.

3.0 SYNTAX ANALYSIS (PARSING)

Role & CFG:

• CFG: G = (V, T, P, S) where V = variables (non-terminals), T = terminals (tokens), P = productions, S = start symbol.

• BNF Example:

  
  <stmt> → if <expr> then <stmt> else <stmt>
  
         | while <expr> do <stmt>
  
         | { <stmt-list> }
  
  <expr> → <term> + <expr> | <term>
  
  <term> → <factor> * <term> | <factor>
  
  

• Parse Tree: Shows hierarchical structure. Derivation: Leftmost/Rightmost.

• Ambiguity: Grammar allows multiple parse trees for same string. Resolved by rewriting grammar or using parser with precedence (e.g., Yacc %left, %right).

Parsing Techniques:

Predictive Parsing (LL(1)):

1. Compute FIRST(α) for each production A → α.

2. Compute FOLLOW(A) for each non-terminal A.

3. Construct Parsing Table M[A, a]:

   • For each A → α and each a ∈ FIRST(α), set M[A, a] = A → α.

   • If ε ∈ FIRST(α), for each b ∈ FOLLOW(A), set M[A, b] = A → α.

4. Grammar is LL(1) iff: No entry in M has multiple productions.

LR Parsing (Bottom-Up Powerhouse):

• Core Idea: Shift tokens onto a stack until a handle (rightmost substring of a production) is found, then reduce.

• LR(0) Items: Production with a dot • showing parser's position: A → α•β.

• Canonical Collection: States are sets of LR(0) items. Closure and Goto functions build the state machine.

• Parsing Table: ACTION[i, a] (shift, reduce, accept, error) and GOTO[i, A] (state transition).

• Hierarchy of Power:

  LR(1) > LALR(1) > SLR(1) > LR(0)

  • LR(1): Uses 1-symbol lookahead in items. Largest tables, most powerful.

  • LALR(1): Merges LR(1) states with same core (ignoring lookahead). Used by Yacc/Bison. Good balance.

  • SLR(1): Uses FOLLOW(A) to decide reductions. Simpler but less powerful than LALR.

[!TIP] Exam Critical: You WILL be asked to construct an SLR or LALR parsing table. Steps:

1. Eliminate left-recursion, ensure grammar is suitable.

2. Augment grammar: S' → S.

3. Build canonical collection of LR(0) items.

4. For SLR: Use FOLLOW sets to fill reduce actions. For LALR: Merge states with same core first, then use lookaheads from original LR(1) items.

Parser Comparison (SLR vs. LALR vs. LR):

Syntactic Errors & Recovery:

• Detection: When ACTION[i, a] = error (no valid action).

• Recovery Strategies:

  • Panic Mode: Skip tokens until one in FOLLOW(current_nonterminal) is found.

  • Phrase Level: Insert/delete/replace a single token to synchronize (requires error productions).

  • Error Productions: Add productions like A → error to handle common mistakes.

4.0 SEMANTIC ANALYSIS

Role & Tasks:

• Type Checking: Verify operator-operand type compatibility. E.g., int + float → implicit conversion.

• Type Conversion:

  • Implicit (Coercion): Automatically performed (e.g., int to float in arithmetic).

  • Explicit (Casting): Programmer-specified (e.g., (float)x).

• Other Checks: Break/continue in loops, return type matching, argument count/type matching.

Symbol Table Management:

• Purpose: Store and retrieve identifier attributes (name, type, scope, line number, address, size).

• Data Structures:

  • Linear List (Unordered/Ordered): Simple, slow search (O(n)).

  • Hash Table: Most common. Fast average access (O(1)). Handles collisions (chaining, open addressing).

  • Binary Search Tree (BST): O(log n) access if balanced.

  • Lexical vs. Nested Scopes: For nested procedures, use display (array of pointers to activation records) or static links in activation records for non-local access.

Attribute Grammars:

• Synthesized Attributes: Values computed from children's attributes (bottom-up). E.g., expression value.

  
  E → E1 + T   { E.val = E1.val + T.val }
  
  

• Inherited Attributes: Values passed from parent/siblings (top-down). E.g., type of identifier in declaration.

  
  D → int X    { X.entry.type = int }  // Inherited from 'int'
  
  

• L-attributed Definitions: A restricted form where inherited attributes can only come from parent and left siblings. Suitable for top-down (LR) translation (e.g., in Yacc semantic actions). Most semantic actions in compilers are L-attributed.

Semantic Errors & Handling:

• Type Mismatch: float * string.

• Undeclared Variable: Use before declaration.

• Multiple Declaration: Same name in same scope.

• Handling: Report error with line number, identifier, and message. Use symbol table to track scope.

Advanced Semantic Concepts:

• Function Overloading: Same name, different parameter types. Resolution based on most specific match during compile time.

• Polymorphic Functions: Functions that work with multiple types (e.g., generics in Java, templates in C++). Type checking is deferred or uses constraints.

5.0 INTERMEDIATE CODE GENERATION

Need & Forms:

• Need: Machine-independent analysis/optimization before target code generation.

• Three-Address Code (TAC): x = y op z (at most 3 operands per instruction). Represents complex expressions as a sequence of simple operations.

Forms of TAC Representation:

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

Quadruples:

( *, b, c, t1 )

( -, 0, t1, t2 )  // assuming unary minus as 0 - t1

( +, t2, d, t3 )

( =, t3, -, a )

Triples:

( *, b, c )

( -, 0, (1) )

( +, (2), d )

( =, (3), a )

TAC for Control Flow Statements (Switch):

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;

}

TAC:

t1 = p + q

goto L1, L2, L3, L4 based on t1 value  // Jump table or if-else chain

L1: x = x + 1

    goto L5

L2: y = y + 2

    goto L5

L3: z = z + 3

    goto L5

L4: c = c - 1

L5:

Backpatching:

• Purpose: Fill in addresses of jump targets (for if, while, for) after they are known.

• Mechanism: Maintain lists of pending jumps (unresolved goto statements) for each boolean expression.

• Algorithm:

  1. For if (B) S1 else S2: Evaluate B → generates code with conditional jump to S1 and unconditional jump to S2. Backpatch B.true list to S1.code, B.false list to S2.code.

  2. For while (B) S: Generate label L1. Evaluate B → B.true jumps to S, B.false to L2. After S, generate goto L1. Backpatch B.true to S.code.

• Example: if (a < b) x = y; else x = z;

  
  if a < b goto L1
  
  goto L2
  
  L1: x = y
  
  L2: x = z
  
  

  Backpatch lists: B.true = [next instruction], B.false = [after L1].

Directed Acyclic Graph (DAG):

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

  • Leaves: Variables/constants (unique).

  • Interior Nodes: Operators. Children: Operands.

  • Key Property: Common subexpressions are shared (same node reused).

• Construction: Process expression tokens left-to-right.

  1. For variable/constant: create new leaf node (if not already present).

  2. For operator: create new node only if no existing node has same operator and same children (order matters for non-commutative ops).

• Application: Common Subexpression Elimination (CSE). The DAG directly shows which computations can be done once and reused.

• Example from DEC 2024:

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

**DAG Construction Steps:**

1.  `a` → node A.

2.  `b` → node B, `c` → node C.

3.  `b - c` → node `-`(B,C). Call it N1.

4.  `a * N1` → node `*`(A,N1). Call it N2.

5.  `a + N2` → node `+`(A,N2). Call it N3.

6.  `N1 * d` → node `*`(N1,D) where D is node for `d`. Call it N4.

7.  `N3 + N4` → node `+`(N3,N4). **Root.**

**Result:** Nodes `N1` (for `b-c`) is shared. Only 4 unique interior nodes instead of 5.

Translation of Program Constructs (Boolean Expressions):

• Boolean to TAC: Use relational ops (<, >, ==) that produce 0/1, or generate conditional jumps directly.

  • B1 && B2 → B1.true → B2; B1.false and B2.false are combined.

  • B1 || B2 → B1.false → B2; B1.true and B2.true are combined.

6.0 CODE OPTIMIZATION

Need & Classification:

• Machine-Independent: Applied to intermediate code (TAC, DAG). E.g., constant folding, CSE, dead code elimination.

• Machine-Dependent: Applied to target code. E.g., register allocation, instruction selection.

• Local: Within a basic block.

• Global: Across basic blocks (requires control flow graph).

Fundamental Optimizations:

• Constant Folding: Evaluate constant expressions at compile time.

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

• Constant Propagation: Replace variables with known constant values.

  • a = 5; b = a + 2; → b = 7

• Common Subexpression Elimination (CSE): Compute value once, reuse. DAG is key tool.

• Dead Code Elimination: Remove code whose result is never used (e.g., unreachable statements, assignments to unused variables).

Loop Optimization (Most Impactful):

Peephole Optimization:

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

• Common Reductions:

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

  2. Unreachable code: goto L1; ... L1: ... after a goto.

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

  4. Sequence reduction: t1 = t2; t2 = t3 → t1 = t3 (if t2 dead).

Basic Blocks & Flow Graphs:

• Basic Block: A straight-line code sequence with:

  1. Single entry (first instruction).

  2. Single exit (last instruction is goto, return, or falls through).

• Construction: Partition code into blocks by leaders (first instruction, target of jump, instruction after jump).

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

• Characteristics: Used for global optimization (data flow analysis).

7.0 RUNTIME ENVIRONMENT & STORAGE ORGANIZATION

Activation Record (AR) / Frame:

• Purpose: Store information for a single procedure invocation.

• Typical Layout (grows downwards):

  
  [ Actual Parameters ]   <-- Caller pushes
  
  [ Return Address ]
  
  [ Control Link (Dynamic Link) ]  // Points to caller's AR
  
  [ Access Link (Static Link) ]    // For nested scopes (non-local vars)
  
  [ Saved Registers ]
  
  [ Local Variables ]
  
  [ Temporaries ]
  
  [ ... ]                 <-- SP points here during execution
  
  

• Example with Nested Procedures:

  
  procedure P;
  
    var x: int;
  
    procedure Q;
  
      var y: int;
  
      begin ... end;
  
    begin ... Q ... end;
  
  

  • Q's AR has Access Link pointing to P's AR to access x.

Storage Allocation Strategies:

[!TIP] Key Difference: Stack is for control-driven allocation (procedure calls), Heap is for data-driven allocation (dynamic objects).

Procedure Calls:

• Call-by-Value: Formal parameter gets a copy of actual argument. Changes inside don't affect caller.

• Call-by-Reference: Formal parameter is an alias (pointer) to actual argument. Changes affect caller.

• Parameter Passing: Values (or addresses) are placed in the actual parameters section of the callee's AR.

• Return Value: Typically placed in a designated register (e.g., R0) or in caller's AR.

Memory Management & Garbage Collection:

• Scope vs. Lifetime:

  • Scope: Where in program text a name is visible (lexical).

  • Lifetime: Time during execution when storage is allocated.

• Garbage Collection: Automatic reclamation of heap memory for unreachable objects. Techniques:

  • Reference Counting: Count pointers to object; collect when count=0. (Fails on cycles).

  • Mark-and-Sweep: Pause program, mark reachable objects from roots, sweep unmarked.

  • Copying (Generational): Divide heap into young/old generations; copy live objects.

8.0 ERROR HANDLING

Compiler Error Types (by Phase):

Error Detection & Reporting:

• Detection Point: Each phase detects errors in its domain.

  • Lexical: Invalid character pattern.

  • Syntax: ACTION[i, a] = error.

  • Semantic: Type conflict in symbol table.

• Meaningful Messages: Should include:

  • Location: File, line number, column.

  • Nature: "Undeclared identifier 'x'", "Type mismatch: int vs float".

  • Context: Show line of code with error marked.

Error Recovery Strategies (Summary):

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

• Phrase Level (Local): Insert/delete/replace a single token to make the rest of the statement syntactically correct. Requires error productions.

• Error Productions: Add productions like stmt → error ; to the grammar. Parser reduces error when it encounters a problematic token.

• Global Correction: (Advanced) Find minimal number of changes (insert/delete/replace) to make program valid. Computationally expensive.

9.0 COMPILER DESIGN TOOLS & CASE STUDIES

Lex & Yacc (Flex & Bison) Workflow:

1. Write Lex file (*.l): Define patterns & actions (C code) for tokens.

2. Write Yacc file (*.y): Define grammar, precedence, semantic actions (C code).

3. Generate:

   • flex lexer.l → lex.yy.c (scanner function yylex()).

   • bison parser.y → parser.tab.c (parser function yyparse()) and parser.tab.h (token definitions).

4. Compile & Link: gcc lex.yy.c parser.tab.c -o compiler -lm.

5. Run: ./compiler < source.c.

Integrating Lex & Yacc:

• Yacc calls yylex() to get tokens.

• yylex() returns token type (defined in parser.tab.h).

• Token value (e.g., for NUM, ID) is stored in global variable yylval.

Step-by-Step Phase Output Example: Source: a = (x/y) * (y + x - z)

10.0 SPECIAL TOPICS (FREQUENT SHORT NOTES)

Quadruples vs. Triples:

Constant Folding:

• Definition: Evaluating constant expressions at compile time.

• Example: x = 2 + 3 * 4 → x = 14.

• When: During intermediate code generation or optimization phase.

• Limitation: Requires operands to be compile-time constants (literals or constant variables).

L-attributed Definitions:

• Definition: A class of attribute grammars where inherited attributes can only be inherited from parent and left siblings in the parse tree.

• Significance: Can be evaluated in a single left-to-right pass (suitable for LR parsing with semantic actions).

• Example Grammar (Simple Assignment):

  
  S → L = R
  
  L → * L1   { L1.inh = L.base + 1; L.base = L1.inh; }  // Inherited from parent L
  
  L → id     { L.base = address(id); }
  
  R → R1 + T { R.val = R1.val + T.val; }
  
  

  Here, L1.inh is inherited from its parent L. This is L-attributed.

Peephole Optimization Techniques:

1. Redundant Instruction Elimination: Remove loads/stores of same value.

2. Unreachable Code Removal: Delete code after unconditional jump.

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

4. Strength Reduction: x = y * 8 → x = y << 3.

5. Sequence Reduction: Combine t1 = t2; t2 = t3 → t1 = t3 if t2 dead.

6. Jump Chaining: goto L1; L1: goto L2 → goto L2.

Input Buffering in Lexical Analysis:

• Problem: read() system call is expensive.

• Solution: Use two large buffers (BUFF_SIZE), read one while scanning the other.

• Sentinel Method: Append a special sentinel character (e.g., EOF) at the end of each buffer. Allows checking for buffer boundary with a single test:

  
  if (forward == eof) { ... reload buffer ... }
  
  if (*forward == '\n') line_num++;
  
  

• Benefit: Eliminates need to check forward < limit on every character access.

Overloading of Functions:

• Definition: Multiple functions with same name but different parameter types.

• Resolution (Overload Resolution): At a call site, compiler selects the best match based on:

  1. Exact match (same type).

  2. Promotion (e.g., char → int).

  3. Standard conversion (e.g., int → float).

  4. User-defined conversion (if applicable).

  5. Ellipsis (...) (last resort).

• Example (C++):

  
  void f(int);    // #1
  
  void f(double); // #2
  
  f('a');         // Calls #1 (char promoted to int)
  
  f(3.14f);       // Calls #2 (float promoted to double)
  
  

RGPV EXAM STRATEGY:

1. High-Weightage Topics: DAG construction, SLR/LR table construction, TAC generation (especially for switch/loops), Lex program, Symbol Table structures, Activation Records, Backpatching.

2. Comparison Questions: SLR vs LALR vs LR; Stack vs Heap; Quadruples vs Triples.

3. Example-Based: Always illustrate answers with small, clear examples (like those from past papers).

4. Diagrams: Draw parse trees, DAGs, activation records, basic block flow graphs neatly.

5. Definitions: Start answers with crisp definitions (e.g., "A DAG is...").

Final Reminder: In exams, show all steps for table construction (FIRST/FOLLOW, canonical collection) and DAG building. Partial credit is awarded for correct methodology even if final answer has minor errors.