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

I. Compiler Structure and Phases Overview

A compiler is a program that translates source code written in a high-level language into an equivalent target language (typically machine code). Its purpose is to abstract hardware details, enable portability, and enforce language semantics.

The compiler operates as a sequence of phases, each transforming the program representation:

Cross-cutting concerns:

• Symbol Table: Central repository for identifier information (name, type, scope, address). Managed across phases.

• Error Handling: Each phase detects and reports errors specific to its domain; recovery strategies vary.

[!TIP]

Example Trace: For a = (x/y) * (y + x - z)

• Lexical: [id(a), =, (, id(x), /, id(y), ), *, (, id(y), +, id(x), -, id(z), )]

• Syntax: AST with = at root, right child is * node, etc.

• Semantic: Types checked (assume all numeric), x/y yields numeric.

• Intermediate (TAC):

t1 = x / y

t2 = y + x

t3 = t2 - z

t4 = t1 * t3

a = t4

• Optimization: If x,y,z are constants, fold; else minimal.

• Code Generation: Load/store instructions for target architecture.

II. Lexical Analysis

Role: First phase; reads input characters, groups them into lexemes, and produces a stream of tokens with token type and optional attribute (e.g., lexeme for identifiers).

Regular Expressions (RE): Used to describe token patterns.
Example: Language of strings with odd number of a and odd number of b.

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

An RE:

\[ (a(ba)^*b(ab)^*) \cup (b(ab)^*a(ba)^*) \]

Explanation: Strings must start and end with different letters to have odd counts; inner parts maintain parity.

Lex/Flex Implementation:

A simple Lex program to recognize identifiers (assuming identifiers start with letter, followed by letters/digits):

%{
#include "y.tab.h"  /* token definitions from parser */

%}

%%

[a-zA-Z][a-zA-Z0-9]* { yylval.str = strdup(yytext); return IDENTIFIER; }

[0-9]+               { yylval.num = atoi(yytext); return CONSTANT; }

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

[ \t\n]             ; /* skip whitespace */

.                   { return yytext[0]; } /* default: return char */

%%

[!TIP]

Identifiers vs Keywords: Lexical analyzer first matches the longest possible lexeme. If the lexeme matches a keyword pattern (e.g., if, while), it returns the keyword token; otherwise, it returns IDENTIFIER. Keywords are usually reserved words listed explicitly in the lexer.

Token Recognition:

• Constants: Integer, float, string literals (RE: [0-9]+, [0-9]*\.[0-9]+, \"[^\"]*\").

• Operators & Delimiters: Single/multi-character (+, ==, ;, {).

Input Buffering:

To avoid reading each character from disk, use double buffering with a sentinel:

• Two buffers of size N.

• lexemeBegin points to start of current lexeme.

• forward scans ahead.

• When forward reaches end of buffer, load next buffer; sentinel EOF at end of each buffer avoids boundary checks.
  Efficiency: Reduces I/O overhead; scanning is O(n) time.

III. Syntax Analysis

Role: Verify token stream conforms to language grammar; build parse tree/AST.

Context-Free Grammars (CFG): \( G = (V, T, P, S) \), where \( V \) nonterminals, \( T \) terminals, \( P \) productions, \( S \) start symbol.

Top-Down Parsing:

• Recursive Descent: Write a procedure for each nonterminal; may require backtracking (not efficient for LL(1)).

• Predictive Parsing: LL(1) parser using parsing table \( M[NT, T] \).

  Construction:

  1. Compute FIRST and FOLLOW sets.

  2. For production \( A \rightarrow \alpha \):

     • For each \( a \in \text{FIRST}(\alpha) \), add \( A \rightarrow \alpha \) to \( M[A, a] \).

     • If \( \epsilon \in \text{FIRST}(\alpha) \), for each \( b \in \text{FOLLOW}(A) \), add \( A \rightarrow \alpha \) to \( M[A, b] \).

  Handling Left Recursion: Eliminate immediate left recursion:

  \( A \rightarrow A\alpha \mid \beta \) becomes

  \( A \rightarrow \beta A' \), \( A' \rightarrow \alpha A' \mid \epsilon \).

  Example: Grammar

  
  A -> (B) | a
  
  B -> B,B | A
  
  

  Eliminate left recursion in B:

  B -> A B', B' -> ,A B' | ε. Then compute FIRST/FOLLOW and parsing table.

Bottom-Up Parsing:

• Shift-Reduce: Uses stack; shift tokens, reduce by productions.

• LR Parsing: Most powerful deterministic bottom-up.

  Types:

  | Parser | Table Size | Power | Construction | |--------|------------|-------|--------------| | SLR | Smallest | Weakest | Uses FOLLOW sets for reductions. | | LALR | Medium | Medium | Merges LR(0) states with same cores. | | LR(1) | Largest | Strongest | Uses lookahead in items. |

  SLR Parsing Table Construction (example grammar from Jun 2025):

  
  S -> S + A | A
  
  A -> A B | B
  
  B -> B * | a | b
  
  

  Steps:

  1. Augment grammar: add \( S' \rightarrow S \).

  2. Build LR(0) items (canonical collection).

  3. Construct ACTION/GOTO tables.

  4. For reduce actions, use FOLLOW(S) for \( S' \rightarrow S \), FOLLOW(A) for \( A \rightarrow B \), etc.

  [!TIP]

  SLR vs LALR vs LR: SLR may have conflicts if FOLLOW set has extra symbols; LALR merges states to reduce table size but may introduce conflicts; LR(1) is conflict-free if grammar is LR(1).

Error Handling in Syntax Analysis:

• Detection: Mismatch in parsing table (no entry), stack underflow, unable to shift/reduce.

• Recovery:

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

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

IV. Semantic Analysis

Role: Ensure program meaning is consistent; enforce language rules (type checking, scope).

Type Systems:

• Type Checking: Verify operator-operand compatibility.

• Type Conversion:

  • Implicit (Coercion): Automatic conversion (e.g., int + float → float).

  • Explicit (Cast): Programmer-specified (e.g., (int)x).

  Example: float f; int i; i = f; → implicit conversion; f = (float)i; → explicit.

Symbol Tables:

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

• Scope Management: Nested scopes (functions, blocks) require hierarchical lookup.

• Data Structures:

  | Structure | Lookup | Insert | Scope Handling | |-----------|--------|--------|----------------| | Linear List | O(n) | O(1) (prepend) | Difficult for nested scopes. | | Hash Table | O(1) avg | O(1) avg | Use separate chaining per scope or stack of hash tables. | | Tree | O(log n) | O(log n) | Natural for nested scopes (each scope node has symbol table). |

  Implementation for Nested Scopes: Maintain a scope stack; each new block pushes a new symbol table (hash table or tree). On exit, pop.

Attribute Grammars:

• Synthesized Attributes: Computed from children (bottom-up). Example: expression value.

• Inherited Attributes: Computed from parent/siblings (top-down). Example: type of identifier from declaration.

• L-Attributed Definitions: A restricted form where inherited attributes depend only on:

  1. Parent's inherited attributes.

  2. Sibling's synthesized attributes to the left.

  Allows evaluation in a single left-to-right pass (suitable for top-down parsing).

  Example: In decl → type id_list, id_list inherits type from type.

Overloading and Polymorphism:

• Function Overloading: Same name, different parameter types. Resolved at compile time by matching argument types.

• Polymorphic Functions: Functions that work with multiple types (generics).

  Implementation:

  • Type Inference: Deduce type from usage (e.g., f(x) where x is int → f instantiated for int).

  • Monomorphization: Generate separate code for each used type.

  Example: template <typename T> T max(T a, T b) { return a > b ? a : b; } → max<int>, max<float> generated.

Semantic Error Detection: Type mismatches, undeclared variables, incompatible operations.

V. Intermediate Code Generation

Role: Bridge between high-level language and target code; platform-independent, easier to optimize.

Three-Address Code (TAC):

• Statements: x = y op z or x = op y or goto L or if x relop y goto L.

• Types:

  • Quadruples: (op, arg1, arg2, result)

    Example: (+, a, b, t1).

    Pros: Easy to optimize (result address explicit).

    Cons: Extra space for result field.

  • Triples: (op, arg1, arg2); result implied by position.

    Example: (+, a, b) stored at index i; refer as (i).

    Pros: Saves space; no temporary names.

    Cons: Harder to optimize (indirect references).

  • Indirect Triples: Quadruples stored separately; triple list stores pointers to quadruples → easier reordering.

Example: TAC for 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

switch t1

  case 1: x = x + 1

  case 2: y = y + 2

  case 3: z = z + 3

  default: c = c - 1

Implementation: Compute t1, then jump via table indexed by t1.

Directed Acyclic Graphs (DAGs):

• Definition: Graph with nodes for subexpressions, edges for operand dependencies; no cycles. Common subexpressions share nodes.

• Construction (example: a + a*(b-c) + (b-c)*d):

  1. Leaf nodes: a, b, c, d.

  2. b-c → node - with children b, c (call it node n1).

  3. a * n1 → node * with children a, n1 (node n2).

  4. n1 * d → node * with children n1, d (node n3).

  5. a + n2 → node + with children a, n2 (node n4).

  6. n4 + n3 → root node + with children n4, n3.

  [!TIP]

  Optimization via DAG: Common subexpression (b-c) computed once (node n1). Code generation: compute n1 first, then use its value.

Backpatching:

• Purpose: Generate code for boolean expressions and control flow with unknown jump targets (filled later).

• Mechanism: Maintain lists of pending jumps ( quadruple indices where target address is unknown). When target known, backpatch all jumps in list.

• Example (for if (a < b) S1 else S2):

  
  ... code for a, b ...
  
  if a < b goto _   // quadruple index i, target unknown → list [i]
  
  ... code for S2 ...
  
  goto _           // index j, target unknown → list [j]
  
  ... code for S1 ...
  
  

  After generating S1 code, backpatch list [i] with address of S1 start. After S2, backpatch list [j] with address after S2.

VI. Code Optimization

Role: Improve IR for faster/smaller target code; local (within basic block) vs global (across blocks).

Local Optimization:

• Constant Folding: Evaluate constant expressions at compile time.

  Example: 3 + 4 * 5 → 23; x = 5 * 4 → x = 20.

• Peephole Optimization: Examine small window (peephole) of instructions; remove redundancies.

  Techniques:

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

  • Algebraic simplifications: x * 1 → x.

  • Unreachable code removal.

  Example:

  t1 = a * 0 → delete (always 0)

  t2 = t1 + b → t2 = b

Loop Optimization (global):

• Loop Invariant Code Motion: Move computations that yield same result each iteration outside loop.

  Example:

  
  for i=1 to n:
  
      x = a * b + c   // a*b invariant if a,b constant
  
  

  → Compute t = a*b before loop.

• Induction Variables: Variables whose value changes linearly with loop index. Replace with simpler expressions.

  Example: j = j + 1 inside loop → use loop index directly.

• Strength Reduction: Replace expensive operations (multiplication) with cheaper (addition).

  Example: x = i * 4 → maintain x via x = x + 4 each iteration.

Basic Blocks:

• Definition: Sequence of statements with single entry (first statement) and single exit (last statement). No jumps into middle, no jumps out except at end.

• Characteristics: Leader statements (first statement, target of jump, after jump) define block boundaries.

• Construction of Flow Graph:

  1. Identify leaders.

  2. Each leader starts a block; include subsequent statements until next leader.

  3. Edges: fall-through (next block), jump (target block).

• Role in Optimization: Basic blocks are units for local optimizations (peephole) and data flow analysis.

Data Flow Analysis (brief): Computes information flow across blocks (e.g., reaching definitions, live variables). Used for global optimizations like common subexpression elimination.

VII. Code Generation

Role: Map optimized IR to target machine code; challenges include instruction selection, register allocation, memory management.

Storage Allocation:

• Stack Allocation: For local variables, parameters, return addresses.

  Activation Record (AR) Layout (typical):

  
  |-----------------|
  

| Actual params | (caller pushes)

| Return address | | Control link (FP of caller) | | Access link (for nested scopes) | | Saved registers | | Local variables |

^

SP points here

- **Procedure Calls**: Caller pushes args, jumps to callee; callee sets up AR (saves FP, SP, etc.), on return restores.

- **Parameter Passing**:

  - **Call-by-value**: Copy argument value.

  - **Call-by-reference**: Pass address (aliasing possible).

  - **Call-by-value-result**: Copy in/out (like pass-by-reference but no aliasing during call).

- **Heap Allocation**: Dynamic memory (`malloc`, `new`). Managed by runtime system (free lists, garbage collection).  

**Comparison**:

| Aspect | Stack | Heap |
|--------|-------|------|
| Speed | Fast (pointer bump) | Slower (search free list) |
| Size | Fixed at compile time | Dynamic |
| Management | Automatic (call/return) | Manual/automatic (GC) |
| Use Case | Local variables, ARs | Objects, dynamic arrays |

**Activation Records** (example with nested calls):

```c

void A() {

  int x;

  B();  // call B

}
void B() {

  int y;

  C();  // call C

}
void C() { ... }

Call sequence: A → B → C. Each has its AR on stack; control links chain to caller's AR; access links for non-local variables (if nested scopes).

Procedure Calls:

• Calling Conventions: Define which registers are caller/callee saved, how args passed (registers/stack), return value location.

• Example (x86-64 System V): First 6 integer args in registers (RDI, RSI, ...), rest on stack; return value in RAX; RBX, RBP, R12-R15 callee-saved.

VIII. Error Handling in Compilers

Lexical Errors:

• Detection: Invalid characters (e.g., @ in identifier), unterminated string/comment.

• Recovery: Delete invalid character, continue; for unterminated string, insert closing quote at EOF or next delimiter.

Syntactic Errors:

• Detection: Missing delimiter (;, }), mismatched brackets, unexpected token.

• Recovery:

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

  • Phrase-Level: Insert/delete tokens to make token stream valid (e.g., insert missing ;).

  • Error Productions: Augment grammar with common error patterns.

Semantic Errors:

• Detection: Type mismatch (int = float without conversion), undeclared variable, incompatible operator.

• Recovery: Insert implicit conversion, assume default type, continue to find more errors.

Error Reporting:

• Meaningful Messages: Include line number, error type, offending token, expected tokens.

• Phase-Specific: Each phase reports errors with context (e.g., lexical: "invalid character '@' at line 5"; syntax: "missing ';' before '}'").

IX. Specialized Topics (Frequently Asked)

These are cross-cutting concepts emphasized in exams:

L-Attributed Definitions:

• Evaluation in Syntax-Directed Translation: Inherited attributes computed from parent and left siblings during parse (top-down). Suitable for syntax-directed translation schemes (SDTS) with embedded semantic actions.

  Example: In decl → type id_list, id_list inherits type from type; id_list can pass inherited type to each id.

Function Overloading:

• Resolution at Compile Time: Based on number and types of arguments.

  Process: Collect candidate functions, discard those with mismatched parameter count, then select best match (exact > promotion > conversion).

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

Polymorphic Functions:

• Implementation:

  • Generics (C++ templates, Java generics): Code generated per type (monomorphization) or type-erased (single code with type checks).

  • Type Inference: Deduce type from usage (e.g., auto x = expr;).

  Example: template <class T> T square(T x) { return x*x; } → square(5) generates int square(int).

Backpatching (detailed):

• Procedure for Control Flow:

  1. For boolean expressions, generate code with conditional jumps to true and false lists.

  2. For if (B) S1 else S2:

     • Code for B with true list L1, false list L2.

     • Backpatch L1 to S1 start.

     • Emit goto to S2 start; false list L2 backpatched to S2 start.

  3. For while (B) S:

     • L1: code for B → true list L2, false list L3.

     • Backpatch L2 to S start; after S, goto L1.

     • Backpatch L3 to after loop.

Basic Blocks (characteristics):

• Single entry, single exit.

• No jumps into middle; only at end.

• Can be represented as nodes in flow graph.

• Used for data flow analysis and local optimization (peephole within block).

[!TIP]

Exam Focus: DAG construction (Dec 2024, Jun 2025), SLR table (Jun 2025), TAC for switch (Dec 2024), activation records (Dec 2024), loop optimization (both papers), predictive parsing (Jun 2025), regular expressions (Dec 2024). Always show step-by-step for tables and DAGs.