UNIT 2: COMPILER DESIGN - SHORT NOTES

I. INTRODUCTION & COMPILER OVERVIEW

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

Phases of a Compiler (Linear Pass Model)

1. Lexical Analysis (Scanning): Reads input characters, groups them into lexemes, and produces a stream of tokens.

2. Syntax Analysis (Parsing): Organizes tokens into a hierarchical structure (parse tree/abstract syntax tree) according to the language's grammar.

3. Semantic Analysis: Checks for semantic consistency (e.g., type checking) and enriches the parse tree with semantic information (e.g., symbol table entries).

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

5. Optimization: Transforms intermediate code for improved performance (speed, size) without changing its meaning.

6. Code Generation: Maps intermediate code to the target machine's instruction set, producing the object code.

7. Symbol Table Management: A central data structure storing information about identifiers (name, type, scope, address, etc.) accessed by multiple phases.

8. Error Handling: Detects and reports errors at various phases, attempts recovery.

[!TIP] Separation of Lexical & Syntax Analysis

• Simplicity: Reduces the complexity of the parser.

• Efficiency: Lexical analysis can use specialized, fast techniques (e.g., finite automata).

• Portability: Lexical analyzer is often the only machine-dependent part.

• Tool Reuse: Standard lexical analyzer generators (LEX/Flex) can be used.

Bootstrapping

The process of using a compiler to compile itself.

• Cross-Compilation: Compiler on machine A generates code for machine B.

• Bootstrapping Phases:

  1. Write a simple compiler (C1) for language L in machine code or another language.

  2. Use C1 to compile a more advanced compiler (C2) written in L.

  3. Use C2 (or C2 compiled by C1) to compile itself, achieving self-hosting.

II. LEXICAL ANALYSIS

Core Concepts

• Token: A category of lexemes (e.g., id, num, +, if).

• Pattern: A rule describing the lexemes of a token (specified by regular expressions).

• Lexeme: A sequence of characters matching a pattern.

Regular Expressions (RE)

Basic operators: | (union), · (concatenation), * (Kleene star), +, ?. Examples:

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

• Integer: [0-9]+

• Even number of as: (b*ab*ab*)*

Finite Automata (FA)

• NFA (Nondeterministic FA): Can have ε-transitions and multiple moves on same input.

• DFA (Deterministic FA): Single move per state/input. No ε-transitions.

• Conversion: RE → ε-NFA (Thompson's Construction) → Subset Construction → DFA.

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

Input Buffering

• Two-Buffer Scheme: Divides input into two buffers (size N). Reduces overhead of reading each character.

• Sentinel Method: Append a special character (e.g., #) to the end of each buffer to avoid explicit end-of-buffer checks for lexemeBegin and forward pointers.

LEX/Flex Tool

A lexical analyzer generator.

%{

/* C declarations */

%}

%%

"if"    { return IF; }

[a-z]+  { yylval.id = lookup(yytext); return ID; }

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

"+"     { return PLUS; }

.       { return yytext[0]; } /* Catch-all */

%%

/* User code (main, yyerror, etc.) */

Lexical Errors

• Invalid character (e.g., @ in identifier).

• Unterminated string/comment.

• Handling: Typically, the scanner skips the offending character and continues, reporting an error message.

III. SYNTAX ANALYSIS

Context-Free Grammars (CFG)

A 4-tuple G = (V, T, P, S):

• V: Set of non-terminals (syntactic variables).

• T: Set of terminals (tokens).

• P: Set of productions A → α.

• S: Start symbol.

Derivations:

• Leftmost: Replace leftmost non-terminal at each step.

• Rightmost: Replace rightmost non-terminal at each step.

• Parse Tree: Graphical representation of derivation, internal nodes are non-terminals, leaves are terminals.

Ambiguity

A grammar is ambiguous if a string has more than one parse tree (or leftmost/rightmost derivation).

Example: E → E+E | E*E | a | b | c is ambiguous for a+b*c.

Resolution: Use precedence (* over +) and associativity (left for both) rules, or rewrite grammar.

Grammar Transformations

• Eliminating Left Recursion:

  Immediate: A → Aα | β → A → βA', A' → αA' | ε

  Indirect: Reorder non-terminals.

• Left Factoring:

  A → αβ1 | αβ2 → A → αA', A' → β1 | β2

FIRST & FOLLOW Sets

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

• If X → ε, include ε.

• For X → Y1Y2...Yk, add FIRST(Y1) (excluding ε). If FIRST(Y1) contains ε, add FIRST(Y2), etc. FOLLOW(A): Set of terminals that can appear immediately to the right of A in some sentential form.

• $ (end-of-input) is in FOLLOW(S).

• If A → αBβ, add FIRST(β) \ {ε} to FOLLOW(B).

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

[!TIP] Predictive Parsing (LL(1)) requires:

1. Grammar is non-left-recursive.

2. Grammar is left-factored.

3. For any two productions A → α | β, FIRST(α) ∩ FIRST(β) = ∅.

4. If α ⇒* ε, then FIRST(α) ∩ FOLLOW(A) = ∅.

Top-Down Parsing

• Recursive Descent: A set of mutually recursive procedures, one per non-terminal. May require backtracking (not LL(1)).

• Predictive Parsing (LL(1)): Uses a parsing table M[A, a] (A: non-terminal, a: terminal). No backtracking.

  Table Construction: For each production A → α:

  1. For each a ∈ FIRST(α), add A → α to M[A, a].

  2. If ε ∈ FIRST(α), for each b ∈ FOLLOW(A), add A → α to M[A, b].

Bottom-Up Parsing (Shift-Reduce)

Builds parse tree from leaves (tokens) to root (start symbol).

• Handle: A substring that matches the RHS of a production, whose reduction is part of a reverse rightmost derivation.

• LR Parsers: The most powerful shift-reduce parsers, using LR(k) tables (Left-to-right scan, Rightmost derivation, k lookahead).

LR Parsing Table Construction

1. Canonical Collection of LR(0)/LR(1) Items: An LR(1) item is [A → α·Bβ, a] where a is lookahead.

2. GOTO(I, X): Set of items reachable from state I on symbol X.

3. ACTION & GOTO Tables:

   • ACTION[s, a]:

     • shift t if GOTO(s, a) = t (for terminal a).

     • reduce A → β if [A → α·Aβ, a] in state s and GOTO(s', A) = s' (for LR(0) items).

     • accept if [S' → S·, $] in state s.

     • error otherwise.

   • GOTO[s, A] = t for non-terminal A.

Parser Types

[!TIP] SLR vs LALR: SLR uses FOLLOW(A) for all reductions of A. LALR merges states with identical cores (same A → α·) but different lookaheads, then uses the union of lookaheads for reductions. This resolves many false SLR conflicts.

Operator Precedence Parsing

A simple bottom-up parser for operator grammars (no production has two adjacent non-terminals).

• Precedence Relations: a < b (a yields to b), a = b (a matches b), a > b (a takes precedence over b).

• Algorithm: Maintain stack. Compare top-of-stack terminal with current input token using precedence relation.

• Limitations: Cannot handle all CFGs (e.g., no non-adjacent non-terminals), limited to operator grammars.

Syntactic Errors & Recovery

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

• Phrase-Level Recovery: Use error productions (e.g., A → error) in grammar to handle common mistakes.

• Global Correction (Least-Cost): Find minimal sequence of insertions/deletions to make input valid (expensive, rarely used).

IV. SYNTAX-DIRECTED TRANSLATION & SEMANTIC ANALYSIS

Attribute Grammars

A CFG augmented with attributes and semantic rules.

• Synthesized Attributes: Values computed from children's attributes (bottom-up).

• Inherited Attributes: Values passed from parent or siblings (top-down).

S-Attributed Definitions

• All attributes are synthesized.

• Evaluated during bottom-up parsing (e.g., LR parsing).

• Example: Computing the value of an expression.

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

L-Attributed Definitions

• Attributes can be synthesized or inherited, but for any production A → X1 X2 ... Xn:

  • Inherited attributes of Xi depend only on:

    1. Attributes of A (parent).

    2. Attributes of X1...X(i-1) (left siblings).

• Can be evaluated during top-down parsing (e.g., recursive descent) or bottom-up (with careful ordering).

• Conversion to Translation Scheme: Place semantic actions immediately before the symbol whose inherited attribute they compute or after the last symbol for synthesized attributes.

Dependency Graph

• Nodes: attribute occurrences in a parse tree.

• Edges: From an attribute occurrence to another if its semantic rule depends on it.

• Evaluation: Must be in topological order (no cycles → grammar is non-circular).

Backpatching

A technique for handling boolean expressions and control flow in code generation, where target addresses are not known initially.

• Boolean Expressions: Maintain lists of unresolved jump addresses (true-list, false-list).

  
  B → B1 || B2   { B.truelist = merge(B1.truelist, B2.truelist);
  
                   B.falselist = B2.falselist; }
  
  B → B1 && B2   { B.truelist = B2.truelist;
  
                   B.falselist = merge(B1.falselist, B2.falselist); }
  
  

• Control Flow Statements:

  • if B then S1: Backpatch B.truelist with S1.nextlist.

  • if B then S1 else S2: Backpatch B.truelist with S1.code, B.falselist with S2.code.

  • while B do S: Generate S.nextlist → backpatch to B's code; backpatch B.truelist to S.code, B.falselist to next.

Syntax-Directed Translation Schemes

• Conditional (if-then-else):

  
  if B then S1 else S2
  
  → B.true → L1, B.false → L2
  
  → S1.code, goto L3
  
  L1: S2.code
  
  L3:
  
  

• Loops (while):

  
  while B do S
  
  → L1: B.code, B.true → L2, B.false → L3
  
  → L2: S.code, goto L1
  
  L3:
  
  

• Switch/Case Statements:

  Generate jump table based on expression value. For each case constant c_i, generate if (expr == c_i) goto L_i. Default case at the end.

Type Conversion

• Implicit (Coercion): Compiler automatically converts (e.g., int to float in float f = 5;).

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

• In Expressions: Follow a type hierarchy (e.g., char < short < int < long < float < double). Operands are promoted to the highest type.

V. INTERMEDIATE CODE GENERATION

Need for IR

• Machine independence.

• Easier to analyze and optimize.

• Bridges high-level language and target machine.

Three-Address Code (TAC)

A sequence of statements of the form x = y op z (or x = op y, goto L, if x relop y goto L). Example: d = (a-b) + (a-c) + (a-c)

t1 = a - b

t2 = a - c

t3 = t1 + t2

t4 = t2 + t3

d = t4

Quadruples, Triples, Indirect Triples

Directed Acyclic Graphs (DAG)

• Nodes: Variables, constants, or results of operations.

• Edges: From operands to operation.

• Purpose: Represent expressions for common subexpression elimination.

• Construction: Builds upon triples. Identical nodes (same operation, same operands) are merged.

Example: Construct DAG for p + p*(q-r) + (q-r)*s

1. Leaf nodes: p, q, r, s.

2. q-r → node n1.

3. p * n1 → node n2.

4. n1 * s → node n3.

5. p + n2 → node n4.

6. n4 + n3 → root n5.

   • n1 (for q-r) is shared → common subexpression eliminated.

   • Final code: t1 = q - r, t2 = p * t1, t3 = t1 * s, t4 = p + t2, t5 = t4 + t3.

Code Generation for Statements

• Assignments: Direct TAC generation.

• Conditionals: Use backpatching. if B then S1 else S2 → B.true → S1.code, B.false → S2.code.

• Loops: while B do S → L1: B.code, B.true → L2, B.false → L3; L2: S.code, goto L1; L3:.

• Switch Statements:

  1. Evaluate expr.

  2. Generate if expr == c1 goto L1, if expr == c2 goto L2, etc.

  3. goto Ldefault.

  4. L1: code1; goto Lend; L2: code2; ...; Ldefault: default_code; Lend:.

• Procedure Calls:

  • Evaluate arguments.

  • Generate param statements.

  • call p, n (n = number of params).

  • return (optional value).

VI. SYMBOL TABLES

Purpose

• Store information about identifiers (name, type, scope, dimension, address, etc.).

• Support insert, lookup, delete operations.

Data Structures

1. Linear Lists:

   • Unordered: Simple, but slow lookup (O(n)).

   • Ordered (Sorted): Binary search possible (O(log n)), but insertion costly (O(n)).

2. Hash Tables:

   • Hash Function: h(name) = (sum of ASCII values) mod table_size.

   • Collision Resolution:

     • Chaining: Buckets with linked lists.

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

   • Average lookup/insert: O(1) if load factor low.

3. Binary Search Trees (BST): Average O(log n), but can degenerate.

4. Tries (Prefix Trees): Efficient for string keys, especially with common prefixes.

Scope Management (Block-Structured Languages)

• Nested Scopes: Inner scope can hide outer scope's identifier.

• Organization: Use a stack of hash tables. Each block entry pushes a new hash table; exit pops it.

• Global Table: Can maintain a global hash table with a scope number or access link (static chain) to resolve non-local references.

VII. ERROR HANDLING

Types of Errors

Detection & Reporting

• Each phase detects errors in its domain.

• Good Error Message: Should indicate location (line/column), nature of error, and possibly suggestion.

• Error Recovery: Allows further analysis (more errors found per compilation).

Recovery Strategies

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

2. Phrase-Level Recovery: Use error productions in grammar. E.g., S → error ; recovers from missing semicolon.

3. Global Correction (Least-Cost): Compute minimal edit script (insert/delete/replace) to make input valid. Computationally expensive (O(n³)).

VIII. RUNTIME ENVIRONMENTS

Storage Allocation Strategies

Activation Record (AR) / Frame

Structure for a procedure call (varies by language/architecture):

|---------------------------|
| Actual parameters (caller) |
| Return address            |
| Control link (dynamic)    | → Previous AR (for nested procedures)

| Access link (static)      | → Enclosing scope's AR (for non-locals)

| Saved machine registers   |
| Local variables           |
| Temporary variables       |
|---------------------------|

• Calling Sequence: Caller pushes args, jumps to callee. Callee pushes return addr, control link, etc.

• Parameter Passing:

  • Call by Value: Copy argument value.

  • Call by Reference: Pass address (aliasing possible).

  • Call by Value-Result (Copy-Restore): Copy in on call, copy out on return.

Stack vs Heap

• Stack: Fast allocation/deallocation (pointer move), no fragmentation, size fixed at compile-time (or grows dynamically but contiguous).

• Heap: Flexible, but allocation/deallocation slower (search free list), prone to fragmentation.

Polymorphic Functions & Overloading

• Polymorphism: Function works with multiple types.

  • Compile-time (Ad-hoc): Function Overloading (same name, different signatures). Resolution based on static types of arguments.

  • Runtime (Parametric/Subtype): Templates/generics (C++, Java) or inheritance (Java, C#). Resolution at runtime (dynamic dispatch).

• Overloading Example:

  
  int max(int a, int b) { ... }
  
  float max(float a, float b) { ... }
  
  max(3, 5) → int version; max(3.0f, 5.0f) → float version.
  
  

IX. CODE OPTIMIZATION

Need & Goals

• Improve execution speed, reduce code size, lower power consumption.

• Must preserve program semantics (preservation of correctness).

Basic Blocks

• A sequence of statements with:

  1. Single entry (first statement executes only if control enters here).

  2. Single exit (last statement transfers control out).

• Construction: Partition code by leader statements (first stmt, targets of jumps, statements following jumps). Each leader starts a new block.

Flow Graphs

• Nodes = Basic Blocks.

• Directed edges = possible control flow between blocks (fall-through and jumps).

Reducible vs Non-Reducible Flow Graphs

• Reducible: All loops have a single entry (natural loops). Most structured programs.

• Non-Reducible: Contains "irreducible" loops (e.g., multiple entry points from goto). Harder to optimize.

Loop Optimization Techniques

1. Loop Detection: Find natural loops (header dominates all members, back-edge exists).

2. Invariant Code Motion: Move calculations that produce same result on every iteration outside the loop.

   
   Before: while(i<n) { x = y*z; ... }
   
   After:  t = y*z;
   
           while(i<n) { x = t; ... }
   
   

3. Strength Reduction: Replace expensive operation (*) with cheaper (+).

   
   Before: for(i=0; i<n; i++) a[i] = 10*i;
   
   After:  t = 0;
   
           for(i=0; i<n; i++) { a[i] = t; t += 10; }
   
   

4. Induction Variables: Variables whose values change by a constant each iteration. Can be eliminated or replaced.

5. Loop Unrolling: Replicate loop body to reduce branch overhead.

Global Optimizations

• Common Subexpression Elimination (CSE): Reuse previously computed value (using DAGs).

• Copy Propagation: Replace x = y with uses of x by y.

• Dead Code Elimination: Remove statements whose results are never used.

• Constant Propagation & Folding:

  • Propagation: If x = 5, replace x with 5 in subsequent code.

  • Folding: Evaluate constant expressions at compile time.

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

• Variable Propagation: Similar to copy propagation but for more complex assignments.

• Code Motion: Move invariant code out of loops (see above).

Peephole Optimization

• Local optimization on a small window (peephole) of target code.

• Examples:

  • Redundant load/store elimination.

  • Unreachable code removal.

  • Algebraic simplifications (x*1 → x).

  • Jump-to-jump elimination.

X. ADDITIONAL TOPICS (FREQUENTLY ASKED)

Input Buffering (Detailed)

• Problem: Reading each character from input stream is slow.

• Two-Buffer Scheme: Two buffers of size N. lexemeBegin points to start of current lexeme, forward scans ahead.

• Sentinel Method: Append a special character (e.g., #) to each buffer. Allows checking forward against lexemeBegin+N-1 without explicit bound check for most cases. When forward hits sentinel, refill buffer.

Operator Precedence Parser (Detailed)

• Grammar Requirement: Operator Grammar (no two adjacent non-terminals in any production).

• Precedence Relations Table: For terminals a, b:

  • a < b: a yields to b (push b).

  • a = b: a matches b (pop both).

  • a > b: a takes precedence (pop a and reduce).

  • No relation: Error.

• Algorithm:

  1. Push $ (end marker) onto stack.

  2. Let a = top terminal on stack, b = next input token.

  3. While a != $$\displaystyle ` or `b != $$:

     • If a < b or a = b: push b, get next token.

     • If a > b: pop a and reduce (pop matching = symbols).

     • Else: error.

• Limitations: Cannot handle non-operator grammars (e.g., A → (A)).

Capabilities of CFG

• Can Express: Recursion, nested structures, most programming language constructs (e.g., balanced parentheses, if-else, loops).

• Cannot Express: Context-sensitive features (e.g., variable must be declared before use, type compatibility). These require semantic analysis.

• Limitation: CFGs cannot enforce constraints like "same identifier used in declaration and use" without attributes/symbol tables.

Steps to Compute FIRST & FOLLOW

FIRST(X):

1. If X is terminal, FIRST(X) = {X}.

2. If X → ε is a production, add ε to FIRST(X).

3. For X → Y1 Y2 ... Yk:

   • Add FIRST(Y1) \ {ε}.

   • If ε ∈ FIRST(Y1), add FIRST(Y2) \ {ε}, and so on.

   • If ε is in all FIRST(Yi), add ε to FIRST(X).

FOLLOW(A):

1. Add $ to FOLLOW(S).

2. For each production B → α A β:

   • Add FIRST(β) \ {ε} to FOLLOW(A).

3. For each production B → α A or B → α A β where ε ∈ FIRST(β):

   • Add FOLLOW(B) to FOLLOW(A).

Basic Block Construction

1. Identify Leaders:

   • First instruction.

   • Target of a goto/branch.

   • Instruction immediately following a goto/branch.

2. Form Blocks: From each leader to the next leader (exclusive).

3. Compute Successors: First instruction of next block (fall-through) and all branch targets.

Dependency Graph (in Optimization)

• Nodes: Program statements or expressions.

• Edges: From statement S1 to S2 if S1 computes a value used by S2.

• Use: Determine evaluation order, identify independent statements for parallelization, detect loops for optimization.

Backpatching (Detailed Flow)

For boolean expressions generating jumps:

• B → B1 or B2:

  • B.truelist = merge(B1.truelist, B2.truelist)

  • B.falselist = B2.falselist

• B → B1 and B2:

  • B.truelist = B2.truelist

  • B.falselist = merge(B1.falselist, B2.falselist)

• B → not B1:

  • B.truelist = B1.falselist

  • B.falselist = B1.truelist

• Backpatch(list, target): Fill all addresses in list with target.

\boxed{\text{These notes cover all high-frequency topics from past RGPV exams (Dec 2024, Jun 2025, May 2023).}}