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

UNIT 1: Compiler Design - Core Concepts

I. Introduction & Compiler Overview

A compiler is a program that translates source code written in a high-level language into an equivalent target language (e.g., machine code). The compilation process is divided into distinct, sequential phases for modularity, ease of implementation, and optimization.

Phases of a Compiler & Their Roles:

Rationale for Phase Separation:

• Lexical vs. Syntax Separation: Simplifies syntax analysis (tokens vs. raw characters), allows lexical analyzer to be implemented separately (e.g., using Lex/Flex), and improves efficiency (lexical analysis is I/O intensive).

• Modular Design Benefits: Easier development, testing, debugging, and maintenance. Each phase has a clear interface. Enables independent optimization phases.

II. Lexical Analysis

Core Task: Convert a stream of characters into a stream of tokens.

1. Finite Automata & Regular Expressions

• Regular Expressions (Regex): Descriptive notation for token patterns.

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

  • Example Problem: Regex for strings with odd number of a and odd number of b.

    • Solution: (b(ab)*a)* | (a(ba)*b)*

• Finite Automata (FA): Mathematical model (states, transitions) that recognizes regex languages.

  • Deterministic (DFA): Single transition per input symbol. Efficient for implementation.

  • Non-deterministic (NFA): Multiple transitions possible. Easier to construct from regex.

  • Conversion: Regex → NFA (Thompson's construction) → DFA (subset construction) → Minimized DFA.

2. Lexical Analyzer Generator (LEX/Flex)

• LEX Program Structure:

  
  %{
  
  /* C declarations */
  
  %}
  
  %% 
  
  pattern   { action }   /* Rules */
  
  %%
  
  /* User code */
  
  

• Example: Recognize identifiers and arithmetic operators.

  
  %%
  
  [a-zA-Z_][a-zA-Z0-9_]*   { printf("ID: %s\n", yytext); }
  
  "+"|"-"|"*"|"/"          { printf("OP: %s\n", yytext); }
  
  [ \t\n]+                 { /* skip whitespace */ }
  
  .                        { printf("ERROR: %s\n", yytext); }
  
  %%
  
  

• Implementation: LEX compiler generates a C program (lex.yy.c) with a function yylex() that returns the next token.

3. Token Recognition

• Identifiers vs. Keywords: Lexical analyzer first matches the longest possible string. If it matches a keyword pattern (e.g., if, while), it returns the keyword token; otherwise, it returns an identifier token.

  • Example: ifcondition → Identifier ifcondition (not keyword if).

• Operators & Others: Handled by specific regex patterns. Ambiguous operators (e.g., == vs =) require longest-match rule.

4. Input Buffering

• Purpose: Reduce I/O overhead for reading source characters.

• Techniques:

  • Sentinel Method: Use a special character (sentinel, e.g., \0) at the end of buffer to simplify end-of-buffer checks. Reduces boundary condition checks.

  • Double Buffering (Two-Buffer Scheme): Use two buffers of size N. When pointer reaches end of first buffer, load second. Allows lookahead of up to N characters without missing tokens spanning buffers.

  • Lookahead: Essential for deciding token boundaries (e.g., >= vs >).

Common Pitfall: Forgetting that lexical analysis uses maximal munch (longest match) rule.

III. Syntax Analysis (Parsing)

Core Task: Check if token stream conforms to the language's Context-Free Grammar (CFG).

1. Context-Free Grammars (CFGs)

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

• Capabilities: Describe nested, recursive structures (e.g., balanced parentheses, if-else nesting).

• Limitations: Cannot express context-sensitive constraints (e.g., variable must be declared before use).

• Ambiguity: A grammar is ambiguous if a string has >1 parse tree (or leftmost/rightmost derivation).

  • Example: E → E+E | E*E | id for a+b*c is ambiguous (two parse trees: (a+b)*c vs a+(b*c)).

  • Elimination: Rewrite grammar to enforce precedence/associativity (e.g., separate E, T, F levels).

• Left Recursion Removal:

  • Direct: A → Aα | β becomes A → βA', A' → αA' | ε.

  • Indirect: Reorder productions to eliminate cycles.

2. Parsing Techniques

3. FIRST & FOLLOW Sets

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

  • Rules: If X → ε, then ε ∈ FIRST(X). If X → Y₁...Yₖ, add FIRST(Y₁); if ε ∈ FIRST(Y₁), add FIRST(Y₂), etc.

• FOLLOW(X): Set of terminals that can appear immediately to the right of X in some sentential form.

  • Rules: $ ∈ FOLLOW(S). If A → αXβ, add FIRST(β) \ {ε} to FOLLOW(X). If β ⇒* ε, add FOLLOW(A) to FOLLOW(X).

• Steps: Compute FIRST for all symbols, then FOLLOW using productions.

4. Parsing Table Construction (LR Family)

5. Parse Tree Construction for Ambiguous Grammar

• Grammar: E → E+E | E*E | id

• String: a+b*c

• Unambiguous Parse Tree (enforcing * over +):

  
      E
  
     /|\
  
    E + E
  
    |   |
  
    id  E
  
        |\
  
        E * E
  
        |   |
  
        id  id
  
  

  (Left associativity for +, right for * if needed, but precedence: * > +).

6. Comparison: SLR vs. LALR

Exam Tip: For parsing table construction, always:

1. Augment grammar (S' → S).

2. Compute LR(1)/LR(0) items.

3. Build canonical collection of states.

4. Construct ACTION/GOTO tables using lookahead.

IV. Syntax-Directed Translation & Semantic Analysis

1. Attribute Grammars

• Attributes: Values associated with grammar symbols (e.g., type, value).

• S-attributed:

  • All attributes are synthesized (computed from children's attributes).

  • Evaluated in bottom-up order during parsing.

  • Example: Computing expression value in an LR parser.

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

• L-attributed:

  • Attributes can be synthesized or inherited (passed from parent/siblings).

  • Inherited attributes evaluated top-down.

  • Can be implemented by top-down parsers (recursive descent) with attribute stacks.

  • Conversion to Translation Scheme: Replace inherited attributes with parameters.

    
    Original: L → *R   { L.inh = R.ptr; }
    
    Scheme: L → *R1   { L.ptr = new node("*", R1.ptr); }
    
    

• Difference:

  | Feature | S-attributed | L-attributed | | :--- | :--- | :--- | | Attribute Type | Only synthesized | Synthesized + inherited | | Evaluation Order | Bottom-up (post-order) | Top-down (pre-order) for inherited | | Parser Compatibility | Bottom-up (LR) | Both top-down & bottom-up |

2. Syntax-Directed Translation Schemes

• Case/Switch Statements:

  
  switch(E) { case C1: S1; case C2: S2; ... default: Sd; }
  
  

  Translation: Generate code to evaluate E, then jump to case labels via a jump table.

• Assignment Statements: id = E; → Generate code for E, then STORE result into id's address.

3. Type Systems

• Type Conversion:

  • Implicit (coercion): Automatically applied (e.g., int → float in 5 + 3.2).

  • Explicit (cast): Programmer-specified (e.g., (float)5).

• Type Checking: Semantic analysis verifies operator-operand type compatibility.

4. Dependency Graphs

• Definition: Directed graph where nodes are attribute occurrences, edges represent dependencies (from needed attribute to using attribute).

• Use: Determines order of attribute evaluation. Detects circular dependencies (ill-formed grammar).

• Example: For A → B C, with synthesized A.s = B.s + C.s, edges: B.s → A.s, C.s → A.s.

V. Intermediate Code Generation

1. Three-Address Code (TAC)

• Form: x = y op z (at most 3 addresses per instruction).

• Forms: x = y op z, x = op y, goto L, if x relop y goto L, param, call, return.

• Example for Switch:

  
  t1 = p + q
  
  switch t1 {
  
    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
  
  if t1 == 1 goto L1
  
  if t1 == 2 goto L2
  
  ...
  
  goto Ld
  
  L1: x = x + 1; goto Lend
  
  L2: y = y + 2; goto Lend
  
  ...
  
  Ld: c = c - 1
  
  Lend:
  
  

2. Intermediate Representations

3. Directed Acyclic Graphs (DAGs)

• Definition: Graph with nodes for subexpressions, edges for operand relationships, no cycles.

• Properties: Leaves are identifiers/constants; internal nodes are operators. Common subexpressions share nodes.

• Construction Steps:

  1. Create leaf nodes for variables/constants.

  2. For operator node op, check if node (op, left, right) exists; if yes, reuse; else create new.

  3. Return node representing entire expression.

• Example 1: a + a*(b-c) + (b-c)*d

  
      +
  
     / \
  
    +   *
  
   / \ / \
  
  a  *  d
  
     /\
  
    a  -
  
       / \
  
      b   c
  
  

  Nodes: a (leaf), b, c, - (b-c), * (a*(b-c)), + (a + ...), * ((b-c)*d), final +.

• Example 2: a*b + (c/(d/e))*d

  
      +
  
     / \
  
    *   *
  
   / \ / \
  
  a b  *  d
  
       / \
  
      /   e
  
     c
  
  

• Use in Optimization: DAGs naturally eliminate common subexpressions (e.g., (b-c) computed once).

4. Backpatching

• Concept: For boolean expressions and control flow, generate code with unfilled jumps (placeholders). Later, fill in actual addresses when known.

• Boolean Expressions: E → E1 or E2:

  • Generate code for E1, backpatch its true list to E2's code, false list = E1.false ∪ E2.false.

• Flow-of-Control Statements:

  • If: if (E) S

    1. E.true → S's code.

    2. E.false → next instruction after S.

  • While: while (E) S

    1. E.true → S's code, then back to E.

    2. E.false → after loop.

• Example: if a < b or c < d then x = y;

  • E1: a < b → if a < b goto L1 (true list = {L1}, false list = {next})

  • E2: c < d → if c < d goto L2 (true list = {L2}, false list = {next})

  • E = E1 or E2: merge false lists, true list = E1.true ∪ E2.true.

  • Backpatch E1.false to E2's code, E.false = E2.false.

  • x = y → x = y

  • Backpatch E.true to x = y.

VI. Optimization

1. Basic Blocks & Flow Graphs

• Basic Block: Sequence of statements with single entry, single exit. No jumps inside except at end.

• Construction from TAC:

  1. Identify leaders (first instruction, target of jump, instruction after jump).

  2. Each leader starts a new block; block ends before next leader.

• Characteristics: Control enters at first statement, exits at last (which may be conditional/unconditional jump).

• Flow Graph: Nodes = basic blocks, edges = possible control flow between blocks.

• Reducible vs. Non-reducible:

  • Reducible: Can be constructed by splitting loops (back edges) and sequences. Most programming languages produce reducible graphs.

  • Non-reducible: Contains irreducible loops (e.g., two overlapping loops). Harder to analyze.

2. Local Optimizations (within a basic block)

3. Loop Optimizations

• Loop-Invariant Code Motion: Identify expressions within loop that compute same value each iteration; move to pre-header.

• Induction Variables: Variables whose value changes by constant each iteration (e.g., i = i + 1). Can be eliminated or replaced.

4. Peephole Optimization

• Principle: Examine a small sliding window (peephole) of target code, replace inefficient sequences with better ones.

• Examples:

  • LOAD x; STORE x → delete.

  • LOAD c1; ADD c2 → LOAD (c1+c2).

  • JMP L1; L1: ... → delete JMP.

  • JMP L1; L1: JMP L2 → JMP L2.

5. Optimization of Basic Blocks

• Apply local optimizations (constant folding, CSE, copy propagation) to each basic block independently before global analysis.

VII. Symbol Tables

Role: Central data structure storing identifier attributes (name, type, scope, address, size, etc.). Used in all phases after lexical analysis.

Data Structures for Implementation:

Common Implementation: Hash table with chaining (collision resolution via linked lists) is most common due to average O(1) operations.

VIII. Runtime Environment & Storage Management

1. Activation Records (AR) / Stack Frames

• Purpose: Store information for a single procedure/function call.

• Typical Layout (grows downwards):

  
  -------------------  <- Top of stack (current AR)
  
  | Actual Parameters |   (passed by caller)
  
  -------------------
  
  | Return Address    |   (to continue after call)
  
  -------------------
  
  | Dynamic Link      |   (pointer to caller's AR)
  
  -------------------
  
  | Local Variables   |   (including temps)
  
  -------------------
  
  | Saved Registers   |
  
  -------------------
  
  | ...               |
  
  -------------------  <- Bottom of AR (frame pointer)
  
  

• Example: For proc P(x, y) called from main, AR for P contains values for x, y, return address to main, pointer to main's AR, and P's locals.

2. Storage Allocation Strategies

3. Procedure Calls

• Steps:

  1. Caller evaluates actual parameters.

  2. Caller pushes return address, old frame pointer, possibly parameters.

  3. Control transfers to callee (jump).

  4. Callee allocates space for locals, saves registers.

  5. Callee executes; on return, places return value (if any), restores registers, pops AR, jumps to return address.

• Parameter Passing Mechanisms:

  • Call-by-Value: Copy actual value; callee cannot modify caller's variable.

  • Call-by-Reference: Pass address; callee can modify caller's variable.

  • Call-by-Value-Result (copy-in copy-out): Copy in at start, copy out at end.

  • Call-by-Name: Textual substitution (thunks).

4. Polymorphism & Overloading

• Polymorphic Functions: Function that works with arguments of different types (e.g., print() for int, float, string). Implemented via dynamic dispatch (vtable in OOP) or generic code.

• Function Overloading: Same name, different parameter types. Resolved at compile-time based on argument types (static binding).

IX. Error Handling

1. Error Handling Phase

• Functions: Detect errors, report meaningful messages, recover to find more errors.

• Strategies: Panic mode, phrase-level recovery, error productions, global correction (least likely).

2. Error Types

3. Error Recovery

• Panic Mode: Discard tokens until a synchronizing token (e.g., ;, }) is found. Simple, may skip errors.

• Phrase-Level Recovery: Insert/delete tokens to allow parsing to continue (e.g., missing ; → insert ;).

• Error Productions: Augment grammar with productions for common errors (e.g., missing_semicolon).

• Global Correction: Find minimal corrections (edit distance) – computationally expensive, rarely used.

X. Additional & Special Topics

1. Bootstrapping

• Concept: Using a compiler to compile itself (or a more advanced version).

• Process:

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

  2. Use C1 to compile compiler C2 (written in L1, a subset of target language).

  3. Now C2 can compile compilers written in L1.

  4. Cross-compilation: Compiler runs on machine M1 but generates code for M2.

2. Regular Expressions for Specific Patterns

• Odd number of a and odd number of b: (b(ab)*a)* | (a(ba)*b)*

• Even length strings over {a,b}: ((a+b)(a+b))*

3. Operator Precedence Parsing

• Principle: Define precedence relations between terminals (<·, =·, ·>). Handle only operator grammars (no two adjacent non-terminals in RHS).

• Parsing Table: M[a, b] gives relation between a (on stack) and b (input).

• Example: For E → E+E | E*E | id, relations: id <· +, + ·> id, * > +, etc.

• Disadvantage: Limited to operator grammars; less powerful than LR.

4. Flow Graph Analysis (Implicit)

• Dominators: Node d dominates n if every path from entry to n goes through d.

• Natural Loops: Defined by a back edge (n → m where m dominates n). Loop body = nodes that can reach n without passing m.

Summary of High-Frequency Exam Topics:

1. Regex & FA: Design regex for constrained languages.

2. Lexical Errors: Identify and give examples.

3. Parsing Tables: SLR & CLR(1) construction (step-by-step).

4. DAG Construction: For expressions with common subexpressions.

5. Optimization: Constant folding, CSE, loop optimization with examples.

6. Symbol Tables: Data structures comparison.

7. Activation Records: Structure with example.

8. Storage Allocation: Stack vs. Heap comparison.

9. Backpatching: For boolean/control flow.

10. Intermediate Code: Quadruples, Triples, Indirect Triples for expressions.

11. FIRST/FOLLOW: Computation steps.

12. S vs L-attributed: Differences with examples.

13. Error Handling: Types & recovery strategies.

Final Tip: Always draw diagrams for parse trees, DAGs, flow graphs, activation records. For table construction, show items, states, and final table. For optimization, show before/after code.