UNIT 5: Compiler Design - Short Notes

Based on RGPV Past Exam Analysis (Compiler Design Papers: Jun 2025, Dec 2024, May 2023, May 2022, Dec 2024, Jun 2025)

1. Compiler Overview and Structure

Phases of a Compiler (with typical output for id1 = id2 + id3 * 50):

1. Lexical Analysis: Token stream → [id1, =, id2, +, id3, *, 50]

2. Syntax Analysis: Parse tree (e.g., → id1 = (id2 + (id3 * 50)))

3. Semantic Analysis: Annotated parse tree with type info (e.g., all id are int)

4. Intermediate Code Generation: Three-address code (TAC) like t1 = id3 * 50; t2 = id2 + t1; id1 = t2

5. Optimization: Optimized TAC (e.g., constant folding if 50 is literal)

6. Code Generation: Target machine code (e.g., x86 assembly)

7. Symbol Table Management: Updated entries for id1, id2, id3

8. Error Handling: Reports errors if any (e.g., undeclared id3).

[!TIP]

Frontend vs. Backend Model:

• Frontend: Language-dependent (lexical, syntax, semantic analysis, IR generation).

• Backend: Machine-dependent (optimization, code generation).

• Advantage: Modularity, reuse of frontend for multiple targets.

• Disadvantage: Overhead in IR translation.

Compiler Construction Tools:

• LEX: Generates lexical analyzers from regex specifications.

• YACC: Generates parsers (LALR) from CFG grammars.

Cross-Compiler: Compiles on one machine for another (e.g., GCC on x86 generating ARM code).

Interpreter vs. Compiler:

Pre-processing: Macro expansion, file inclusion (#include), conditional compilation (#ifdef). Done before compilation.

2. Lexical Analysis

Role: Read source code, tokenize, remove whitespace/comments, handle lexical errors.

Regular Expressions for Tokens:

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

• Integer constant: [0-9]+

• Keyword: if|else|while|... (exact strings)

• Operator: +|\-|\*|/|==|...

Finite Automata:

• NFA → DFA via subset construction.

• Limitations: Cannot count (e.g., balanced parentheses () require PDA).

LEX Tool: Specification file with three sections:

1. Definitions: Regex macros (e.g., digit [0-9]).

2. Rules: pattern { action } (e.g., {digit}+ { yylval = atoi(yytext); return NUMBER; }).

3. User Code: C/C++ functions.

Input Buffering: Sentinel method – two buffers, each with sentinel \0 at end to avoid bounds check per character read.

Token Recognition:

• Keywords stored in a hash table.

• Identifier pattern matched first, then checked against keyword table.

• Whitespace/comments discarded.

Lexical Errors: Invalid characters, unterminated comments. Recovery: delete/insert character, panic mode.

3. Syntax Analysis (Parsing)

Context-Free Grammar (CFG): $$\displaystyle G = (V, T, P, S) $$ where $V$ = non-terminals, $T$ = terminals, $P$ = productions, $S$ = start symbol.

• Derivation: Leftmost/rightmost.

• Parse Tree: Hierarchical structure.

Ambiguity: String with multiple parse trees.

Example: E → E + E | E * E | id is ambiguous for id + id * id.
Resolution: Grammar rewriting (enforce precedence), error productions.

Grammar Transformations:

1. Left Recursion Elimination:

   $$\displaystyle A \rightarrow A\alpha \mid \beta $$ becomes $$\displaystyle A \rightarrow \beta A' $$, $$\displaystyle A' \rightarrow \alpha A' \mid \varepsilon $$.

2. Left Factoring:

   $$\displaystyle A \rightarrow \alpha\beta_1 \mid \alpha\beta_2 $$ becomes $$\displaystyle A \rightarrow \alpha A' $$, $$\displaystyle A' \rightarrow \beta_1 \mid \beta_2 $$.

First & Follow Sets:

• $\text{First}(X)$: Set of terminals starting strings derived from $X$.

• $\text{Follow}(A)$: Set of terminals appearing immediately after $A$ in sentential forms.

• Used in predictive parsing and LL(1) table construction.

Top-Down Parsing:

• Recursive Descent: Non-backtracking if grammar is LL(1); backtracking if ambiguous.

• Predictive Parsing: Use parsing table $M[A, a]$ (action for non-terminal $A$, token $a$).

• LL(1) Grammar Properties:

  \boxed{\begin{aligned} &\text{1. No left recursion.} \ &\text{2. Left-factored.} \ &\text{3. For } A \rightarrow \alpha \mid \beta: \ &\quad \text{First}(\alpha) \cap \text{First}(\beta) = \emptyset \ &\text{4. If } \varepsilon \in \text{First}(\alpha), \text{ then } \text{First}(\alpha) \cap \text{Follow}(A) = \emptyset. \end{aligned}}

Bottom-Up Parsing (LR Parsing):

• LR(0) Items: $$\displaystyle [A \rightarrow \alpha \bullet \beta] $$.

• Closure: Add items for non-terminals immediately after •.

• Goto: Move • over a grammar symbol.

• SLR Parsing Table: Use $\text{Follow}(A)$ for reductions of $$\displaystyle A \rightarrow \alpha $$.

• LALR Parsing: Merge states with same core (reduces table size vs LR(1)).

• LR(1) Parsing: Items include lookahead: $$\displaystyle [A \rightarrow \alpha \bullet \beta, a] $$.

Comparison of SLR, LALR, LR(1):

Error Recovery in LR Parsing:

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

• Error productions: Add productions like S → error to recover.

• Phrase-level: Local corrections (insert/delete tokens).

4. Syntax-Directed Translation (SDT)

Attributes: Properties of grammar symbols.

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

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

Dependency Graph: Nodes = attribute values; edges = dependencies. Must be acyclic for evaluation.

Annotated Parse Tree: Parse tree with attribute values at nodes.

S-Attributed Definitions: All attributes are synthesized.

Example: Expression evaluation:

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

L-Attributed Definitions: Inherited allowed but must satisfy:

1. Inherited attributes depend only on parent and left siblings.

2. No circular dependencies.

Example: Code generation with inherited symbol table for nested scopes.

SDT for Infix to Postfix:

E → E1 + T { print('+'); }

E → T

T → T1 * F { print('*'); }

T → F

F → ( E )

F → id { print(id); }

Computing Values: Traverse parse tree bottom-up, evaluate synthesized attributes.

5. Type Checking

Role of Type Checker: Ensure type consistency, report type errors (mismatch, undeclared).

Type Systems:

• Static vs Dynamic: Compile-time (C, Java) vs runtime (Python).

• Strong vs Weak: Strong (no unsafe implicit conversions, e.g., Java) vs weak (e.g., C allows int* to void*).

Type Expressions: Built from base types (int, float) using constructors:

• Array: array(n, T)

• Function: func(T1, T2) → T3

• Pointer: ptr(T)

Type Equivalence:

• Name equivalence: Same declaration (e.g., two typedefs).

• Structural equivalence: Same structure (e.g., two structs with identical fields).

Type Conversion:

• Implicit (coercion): Hierarchy: char → int → float → double.

• Explicit: Casts (e.g., (float)i).

Polymorphic Functions:

• Ad-hoc polymorphism: Overloading (e.g., + for int and float).

• Parametric polymorphism: Generics (e.g., List<T> in C++ templates).

Function Overloading Resolution: Based on number and types of arguments; best match (exact > promotion > conversion).

6. Intermediate Code Generation

Need for IR: Machine-independent optimization, easier target code generation.

Three-Address Code (TAC) Forms:

• Assignment: x = y op z

• Copy: x = y

• Unary: x = op y

• Indexed: x = y[i]

• Conditional: if x relop y goto L

• Unconditional: goto L

• Procedure: param x; call p, n; return y

Quadruples vs Triples vs Indirect Triples:

TAC Generation:

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

• Control Structures: Use backpatching for forward references.

Directed Acyclic Graphs (DAGs):

• Construction Algorithm for Basic Block:

  1. For each statement x = y op z:

     • If node for y op z exists, reuse it; else create new node.

     • Set x to point to that node.

     • Mark x as defined.

  2. Remove dead nodes (no uses).

• Applications:

  • Common Subexpression Elimination (CSE): Reuse existing node.

  • Constant Folding: Evaluate constant operations at node creation.

  • Dead Code Elimination: Remove nodes with no uses.

Backpatching:

• Concept: Handle forward references in boolean expressions and jumps.

• Maintain lists of quadruple indices for true and false branches.

• Algorithms:

  • Boolean Expressions: For E → E1 or E2:

    • Backpatch E1.false to start of E2.

    • E.true = merge(E1.true, E2.true), E.false = E2.false.

  • Conditional Statements: if E then S1 else S2:

    • Backpatch E.true to S1 code, E.false to S2 code.

    • nextlist = merge(S1.nextlist, S2.nextlist).

  • Loops: while E do S:

    • Backpatch S.nextlist to E code, E.false to after loop.

7. Run-Time Environment

Activation Record (AR):

Structure (typical layout):

• Return address

• Control link (dynamic chain: caller’s AR)

• Access link (static chain: for nested procedures)

• Parameters

• Local variables

• Temporaries

• Return value (sometimes)

Storage Allocation Strategies:

Symbol Tables:

• Purpose: Store identifier info (name, type, scope, address).

• Organizations:

  • Linear list: Simple, $O(n)$ search.

  • Hash table: $O(1)$ average, collisions.

  • Binary search tree: $O(\log n)$, ordered.

• Scopes: Global, local, nested (handle with multiple tables or scope fields).

Parameter Passing Mechanisms:

• Call-by-value: Copy argument value; callee changes not visible.

• Call-by-reference: Pass address; changes visible.

• Call-by-value-result: Copy in at call, copy out at return (copy-restore).

Procedure Calls:

1. Caller pushes arguments (registers/stack).

2. Caller jumps to callee.

3. Callee sets up AR, executes.

4. Return value in register/AR.

5. Callee restores registers, returns.

Dynamic Storage Allocation: Heap management (malloc/free), garbage collection (mark-sweep, copying).

8. Code Optimization

Principles: Preserve program semantics, improve execution time/space.

Sources of Optimization:

• Local: Within a basic block.

• Global: Across basic blocks (control flow).

• Interprocedural: Across procedures.

• Loop: Most impactful (executed repeatedly).

Local Optimizations on Basic Blocks:

1. Common Subexpression Elimination (CSE):

   t1 = a * b; ... t2 = a * b; → t2 = t1;

2. Copy Propagation:

   x = y; ... a = x + 5; → a = y + 5; (then eliminate x if possible).

3. Constant Folding:

   x = 3 + 5 * 2; → x = 13;

4. Dead Code Elimination:

   Remove assignments whose results are never used.

Loop Optimizations:

1. Loop-Invariant Code Motion (Hoisting):

   Move computations unchanged across iterations outside loop.

   Example: t = a * b; inside loop where a,b constant → move before loop.

2. Induction Variables & Strength Reduction:

   • Induction variable: changes by constant each iteration (e.g., i = i + 1).

   • Strength reduction: replace expensive op (multiplication) with cheaper (addition).

     i * 4 → t = t + 4 (with t initialized to i*4).

3. Loop Unrolling: Duplicate loop body to reduce overhead (briefly).

Peephole Optimization:

• Scan small window (3–5 instructions), replace with equivalent faster sequence.

• Examples:

  • Redundant load: load r1, a; load r1, a; → remove second.

  • Jump to jump: goto L1; L1: goto L2; → goto L2;

  • Algebraic: x = x + 0; → delete.

Optimization Using DAGs:

• Construct DAG for basic block (see Section 6).

• Identify common subexpressions (shared nodes) and constants (folded nodes).

Basic Blocks:

• Definition: Sequence of TAC with single entry (first statement) and single exit (last statement).

• Characteristics:

  • No jumps except at end.

  • No jumps into middle.

• Construction:

  1. Identify leaders: first statement, targets of goto, statements following goto.

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

9. Code Generation

Issues in Code Generation:

1. Instruction Selection: Map IR to machine instructions (tree covering).

2. Register Allocation: Assign variables to limited registers.

3. Evaluation Order: Minimize register spills.

Register Allocation Strategies:

• Graph Coloring:

  1. Build interference graph (nodes = variables, edge if live together).

  2. Color graph with $k$ colors ($k$ = number of registers).

  3. Spilling: If not $k$-colorable, spill variable to memory.

• Linear Scan:

  • Order variables by first use.

  • Assign registers linearly; spill on conflict.

  • Faster but less optimal than graph coloring.

Basic Block Code Generation:

• Use DAG: traverse in order (postorder for dependencies), generate instructions per node.

• Handle jumps/labels: for conditional, generate compare and branch.

Code Generation for Expressions:

• Consider operator precedence/associativity.

• Generate code for subexpressions, combine with operator.

Example: R = (p + q) - ((r + s) - t)

TAC: t1 = p + q; t2 = r + s; t3 = t2 - t; t4 = t1 - t3; R = t4

Code (x86-like): mov eax, p; add eax, q; mov ebx, r; add ebx, s; sub ebx, t; sub eax, ebx; mov R, eax

Control Statements:

• if: if a < b goto L1; goto L2; L1: ... L2:

• switch: Jump table or compare chain.

• while: L1: if condition goto L2; goto L3; L2: body; goto L1; L3:

Procedure Calls:

• Pass parameters (registers/stack).

• Save caller-saved registers.

• Jump to callee.

• Callee sets up AR, executes.

• Return value in register/AR.

• Restore callee-saved registers.

10. Error Handling

Lexical Errors:

• Detection: Invalid characters, unterminated comments/strings.

• Recovery:

  • Panic mode: Skip to next valid token.

  • Deletion/Insertion: Delete/insert character to resynchronize.

Syntactic Errors:

• Detection: Parsing failure (unexpected token).

• Recovery:

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

  • Error productions: Add grammar rules with error token (e.g., if → if error then ...).

  • Phrase-level: Local corrections (insert missing ;, delete extra token).

Semantic Errors:

• Type mismatches, undeclared variables, scope errors.

• Detected during semantic analysis.

• Recovery: Assign default type, skip to next statement, continue.

Role of Error Handling Phase: Report errors with line numbers, attempt recovery to find multiple errors per compilation, avoid cascade errors.

11. Supporting Concepts and Analysis

Flow Graph:

• Nodes: Basic blocks.

• Edges: Control flow (possible transfers).

• Construction:

  1. Partition TAC into basic blocks.

  2. For each block $B$, add edge from $B$ to first statement of each successor (next sequential or jump target).

Basic Blocks: See Section 8 for construction.

Constant Folding: Evaluate constant expressions at compile time.

Example: x = 3 + 5 * 2; → x = 13;

Areas of Code Optimization:

• Machine-independent: DAG, CSE, constant propagation (applies to any target).

• Machine-dependent: Register allocation, instruction selection (target-specific).

• Interprocedural: Inlining, parameter passing across calls (requires whole-program analysis).

[!TIP]

Exam Focus:

• Parsing: Practice constructing SLR/LALR tables (frequent 7m questions).

• Intermediate Code: TAC for expressions/control structures, DAG construction, backpatching algorithms.

• Optimization: Local vs global, loop optimizations (invariant code motion, strength reduction).

• Storage Allocation: Activation record structure, stack vs heap comparison.

• SDT: Difference between S-attributed and L-attributed, write SDT for infix to postfix.

• LEX: Write simple programs for token recognition.

• Type Checking: Type conversion, overloading resolution.

• Code Generation: Register allocation strategies (graph coloring, linear scan).

• Error Handling: Recovery strategies for lexical/syntactic errors.