UNIT 5: Compiler Design (Based on Past Exam Questions)

1. Compiler Phases and Overview

A compiler is a program that translates source code (high-level language) into target code (machine/assembly language). The process is divided into distinct, sequential phases.

List of Compiler Phases:

1. Lexical Analysis (Scanning)

2. Syntax Analysis (Parsing)

3. Semantic Analysis

4. Intermediate Code Generation

5. Code Optimization

6. Code Generation

7. Symbol Table Management (贯穿 all phases)

8. Error Handling (贯穿 all phases)

Role of Each Phase:

[!TIP] Exam Focus: Be prepared to list phases in order and state the key output/input of each. Questions often link phases (e.g., "What does syntax analysis receive from lexical analysis?").

2. Lexical Analysis

Importance of Separation from Syntax Analysis:

1. Simplicity: Separates low-level character processing from high-level syntax rules.

2. Efficiency: Lexical analyzer can be optimized separately (e.g., using finite automata).

3. Portability: Machine-dependent aspects (like character encoding) are isolated.

4. Implementation: Allows use of specialized tools (like LEX).

Finite Automata (FA) for Token Recognition:

• Regular Expressions (pattern for a token class) are converted to a Non-deterministic FA (NFA).

• NFA is converted to a Deterministic FA (DFA).

• DFA is implemented as a program (transition table) that scans input characters and recognizes token boundaries.

• Example: Identifier pattern [a-zA-Z][a-zA-Z0-9]* → DFA with states for start letter, subsequent alphanumeric chars.

LEX Tool:

• Structure: A LEX program (.l file) has three sections:

  
  %{
  
  /* C declarations (global vars, functions) */
  
  %}
  
  /* Regular expressions (definitions) */
  
  %%
  
  /* Rules: Pattern { Action (C code) } */
  
  %%
  
  /* User code (main, auxiliary functions) */
  
  

• Example for id and arithmetic operators:

  
  %{
  
  #include "y.tab.h" /* Token definitions from parser */
  
  %}
  
  digit   [0-9]
  
  letter  [a-zA-Z]
  
  %%
  
  {letter}({letter}|{digit})*   { yylval = strdup(yytext); return ID; }
  
  "+"                          { return PLUS; }
  
  "-"                          { return MINUS; }
  
  "*"                          { return MUL; }
  
  "/"                          { return DIV; }
  
  "="                          { return ASSIGN; }
  
  [ \t\n]                     ; /* Skip whitespace */
  
  .                            { return yytext[0]; } /* Catch-all */
  
  %%
  
  int yywrap() { return 1; }
  
  

  • yylval passes token value (e.g., string for id) to parser.

  • yytext holds matched lexeme.

LEX Compiler Overview:

lex source.l → generates lex.yy.c (C program with yylex() function) → compile with GCC → a.out (scanner executable). The scanner reads stdin, uses DFA to find longest matching pattern, executes associated action.

[!TIP] Common Pitfall: LEX uses maximal munch (longest match). If == and = are both patterns, == is recognized as one token, not two =.

3. Syntax Analysis (Parsing)

Parsing Techniques:

Operator Precedence Parsing:

• A simple shift-reduce parser for expressions.

• Based on precedence relations (<·, =·, ·>) between terminals.

• No need for grammar to be in a specific form (unlike LR).

• Limitation: Cannot handle non-operator tokens or ambiguous grammars well. Only for operator grammars (no two adjacent non-terminals on RHS).

• Example: For E -> E+E | E*E | (E) | id, precedence: id <· +, + ·> *, * <· id, etc.

LR Parsers:

• SLR(1): Uses FOLLOW sets for reduce actions. May have conflicts if a production's FOLLOW set intersects with a shift action's lookahead.

• LALR(1): Merges LR(1) states with identical core (items without lookahead). More precise than SLR, fewer conflicts. Used in YACC/BISON.

• CLR(1) / LR(1): Uses full LR(1) items (production + dot position + lookahead). No unnecessary reductions. Most powerful, largest tables.

• Comparison: SLR vs LALR:

  | Feature | SLR(1) | LALR(1) | | :--- | :--- | :--- | | Lookahead | FOLLOW(A) for reduction of A -> α. | Precise lookahead from merged states. | | Power | Weakest (may reject valid LR(1) grammars). | Stronger (accepts all SLR(1) + more). | | Table Size | Smallest. | Larger than SLR, smaller than full LR(1). | | Conflicts | More likely. | Fewer conflicts than SLR. |

CLR(1) Parsing Table Construction (Example Grammar):

Given: S -> L = R | R, L -> *R | id, R -> L

1. Augment Grammar: Add S' -> S.

2. Compute LR(1) Items: For each production A -> α·Bβ, a, find all productions B -> γ and compute FIRST(βa) for lookahead b.

3. Build Canonical Collection of LR(1) Items: Use GOTO on states.

4. Construct Table:

   • ACTION[state, terminal]:

     • If item [A -> α·aβ, b] → shift on a.

     • If item [A -> α·, a] (and A != S') → reduce A -> α.

     • If item [S' -> S·, $] → accept.

   • GOTO[state, non-terminal]: State after shifting A.

Parse Tree Construction & Ambiguity Elimination:

• Ambiguous Grammar: Allows multiple parse trees for same string (e.g., E -> E+E | E*E | id for a+b*c).

• Elimination: Use precedence and associativity rules to rewrite grammar.

  • Example: E -> E+T | T, T -> T*F | F, F -> (E) | id.

  • Now a+b*c has unique tree: E(E(a)+T(T(b)*F(c))).

Context-Free Grammars (CFG):

• Capabilities: Describe nested structures (matching parentheses, if-then-else), recursion.

• Limitations: Cannot express context-sensitive constraints (e.g., variable must be declared before use, type matching). Need semantic analysis for this.

FIRST and FOLLOW Sets:

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

  • Rules: If X -> aα, a ∈ FIRST(X). If X -> ε, ε ∈ FIRST(X). If X -> Yα, FIRST(Y) - {ε} ⊆ FIRST(X); if ε ∈ FIRST(Y), also add FIRST(α).

• FOLLOW(A): Set of terminals that can appear immediately to the right of A in some sentential form. $ (EOF) is in FOLLOW(S).

  • Rules: If S -> αAβ, then FIRST(β) - {ε} ⊆ FOLLOW(A). If S -> αA or S -> αAβ where ε ∈ FIRST(β), then FOLLOW(S) ⊆ FOLLOW(A).

• Computation Steps: Iteratively apply rules until no new symbols added.

[!TIP] Exam Trap: For FOLLOW(A), you add FIRST(β) only if β is present after A. If A is at end (S -> αA), add FOLLOW(S).

4. Syntax-Directed Translation

Attribute Grammars:

• S-attributed: All attributes are synthesized. Evaluated in bottom-up (post-order) traversal.

  • Example: E -> E1 + T { E.val = E1.val + T.val }

• L-attributed: Attributes can be synthesized or inherited, but inherited attributes from left siblings only. Can be evaluated in top-down (pre-order) traversal.

  • Example: D -> T L where L inherits type from T.

Bottom-up Evaluation of S-Attributes:

• When reducing A -> α in a parse, compute A's synthesized attributes from attributes of symbols in α.

• Example Grammar:

  
  E -> E1 + T   { E.val = E1.val + T.val }
  
  E -> T        { E.val = T.val }
  
  T -> int      { T.val = int.lexval }
  
  

• For input int + int:

  1. Reduce int -> T: T.val = int.lexval (say 5).

  2. Reduce int -> T: T.val = 2.

  3. Reduce E -> T: E.val = T.val = 5.

  4. Shift +.

  5. Reduce E -> E1 + T: E.val = E1.val + T.val = 5 + 2 = 7.

Converting L-attributed Grammar to Translation Scheme:

1. For each production A -> X1 X2 ... Xn, place semantic actions between symbols where inherited attributes are needed.

2. Inherited attribute of Xi from left siblings is computed by an action before Xi.

3. Inherited attribute from A is computed by an action at the leftmost position.

4. Synthesized attributes are computed by an action at the rightmost position.

• Example: D -> T L with L.in = T.type.

  • Scheme: D -> T { L.in = T.type } L

Syntax-Directed Translation for Case Statements:

• Grammar:

  
  stmt -> case expr of case_list end
  
  case_list -> case_list case | case
  
  case -> const ':' stmt
  
  

• Translation: Generate jump tables or if-else chains.

• Backpatching: For each case, generate conditional jump to stmt if expr == const. Use backpatching lists to fill addresses after all cases are known.

5. Intermediate Code Generation

Forms of Intermediate Code:

Generation for Arithmetic Expressions:

• Expression: d = (a-b) + (a-c) + (a-c)

• Quadruples:

  
  (-, a, b, t1)
  
  (-, a, c, t2)
  
  (+, t1, t2, t3)
  
  (-, a, c, t4)   // Common subexpr not yet eliminated
  
  (+, t3, t4, t5)
  
  (=, t5, -, d)
  
  

• Triples:

  
  (-, a, b)
  
  (-, a, c)
  
  (+, 1, 2)
  
  (-, a, c)      // Duplicate triple
  
  (+, 3, 4)
  
  (=, 5, d)
  
  

• Indirect Triple:

  
  Triple[1] = (-, a, b)
  
  Triple[2] = (-, a, c)
  
  Triple[3] = (+, 1, 2)
  
  Triple[4] = (-, a, c)  // Same as 2
  
  Triple[5] = (+, 3, 4)
  
  Triple[6] = (=, 5, d)
  
  Indirect[] = {1,2,3,4,5,6}
  
  

Backpatching for Boolean Expressions:

• Used for conditional statements (if, while) and boolean expressions that generate jumps.

• Concept: Generate code with unfilled jumps ((if_false, a, -)). Maintain a list of quadruple indices needing the same target address.

• Example: if (a < b) stmt1 else stmt2

  1. a < b → (<, a, b, -) → generate if_false jump, add its index to list L1.

  2. Code for stmt1.

  3. Generate unconditional goto to stmt2, index j1.

  4. backpatch(L1, nextInstr) → fills all if_false jumps to point to stmt2.

  5. Code for stmt2.

[!TIP] Key: makelist(i) creates list {i}. merge(L1, L2) concatenates lists. backpatch(L, addr) fills all jumps in L with addr.

6. Symbol Table Management

Purpose:

• Store information about identifiers (name, type, scope, address, line number).

• Support insertion (on declaration), lookup (on use), and scope management.

Operations:

• insert(name, attributes)

• lookup(name) → returns entry or NULL.

• delete(name) or delete_scope(scope_level).

Data Structures:

[!TIP] Most Common: Hash table with buckets (chaining) is standard for its speed. For nested scopes, use a stack of hash tables.

7. Storage Allocation

Static vs Dynamic Allocation:

Heap Storage Allocation Strategy:

• Manages unbounded memory requests at runtime.

• Strategies:

  1. First-fit: Allocate first block large enough.

  2. Best-fit: Allocate smallest block that fits (minimizes waste).

  3. Worst-fit: Allocate largest block (leaves large leftover).

• Fragmentation:

  • External: Free memory exists but not contiguous.

  • Internal: Allocated block larger than requested (wasted inside).

• Garbage Collection: Reclaims unreachable heap objects (e.g., mark-sweep).

Activation Record (AR) / Stack Frame:

Structure for a procedure/function call:

|---------------------------|
| Actual Parameters         |  (caller pushes)

|---------------------------|
| Return Address            |
|---------------------------|
| Control Link (Dynamic)    |  (pointer to caller's AR)

|---------------------------|
| Access Link (Static)      |  (pointer to non-local scope)

|---------------------------|
| Local Variables           |
|---------------------------|
| Temporary Variables       |
|---------------------------| <-- SP (Stack Pointer)

• Management: CALL pushes AR, sets new SP. RETURN pops AR, restores SP.

8. Code Optimization

Basic Blocks and Flow Graphs:

• Basic Block: Sequence of statements with single entry (first stmt) and single exit (last stmt). No jumps inside except at end.

• Construction: Identify leaders (first stmt, target of jump, after jump). Statements from leader to next leader-1 form a block.

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

Optimization of Basic Blocks:

1. Common Subexpression Elimination (CSE): Recompute value only once.

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

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

3. Constant Folding: Evaluate constant expressions at compile time.

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

4. Algebraic Simplifications: x * 1 → x, x + 0 → x.

Loop Optimization Techniques:

1. Code Motion: Move invariant computations out of loop.

   • while (i < n) { x = y * z; ... } → t = y * z; while (...) { x = t; ... }

2. Induction Variable Elimination: Replace multiple induction vars with one.

   • i = 0; while (i < n) { j = i * 4; ... i = i+1; } → j = 0; incr = 4; while (...) { ... j = j + incr; }

3. Strength Reduction: Replace expensive op with cheaper one.

   • x * 8 → x << 3 (multiplication → shift).

   • j = i * 8 → j = i << 3.

Variable Propagation:

• Replace uses of a variable with its known constant value.

• Example: a = 5; b = a + 2; → b = 5 + 2 → b = 7 (after constant folding).

Reducible vs Non-Reducible Flow Graphs:

• Reducible Flow Graph: Can be reduced to a single node by repeatedly contracting edges (removing loops, merging nodes). All structured programs (with if, while, for without goto) produce reducible graphs.

• Non-Reducible: Contains irreducible loops (multiple entry points, e.g., from goto). Harder for data-flow analysis.

• Importance: Most optimizations (like reaching definitions) assume reducible graphs.

Dependency Graphs:

• Directed graph where nodes = statements or expressions, edges = data/control dependencies.

• Data Dependency: S2 uses result of S1 → edge S1 → S2.

• Control Dependency: S2 executes only if condition in S1 is true/false.

• Use: Detect parallelism, schedule instructions, identify optimization opportunities (e.g., if no dependency, reorder).

[!TIP] Loop Optimization: Always look for invariant code first (code motion), then induction variables, then strength reduction.

9. Additional Topics

Bootstrapping in Compiler Construction:

• Problem: How to compile a compiler written in language X when no X compiler exists?

• Solution: Bootstrap – compile in stages.

  1. Write compiler C1 for X in a lower-level language L (e.g., assembly, or another existing language).

  2. Use L compiler to compile C1 → produces X compiler C2 (written in X).

  3. Now C2 can compile X programs directly. Can also recompile C2 with itself (C3) to ensure purity.

• Example: First C compiler written in assembly. Once cc1 exists, it can compile future C compilers written in C.

[!TIP] Analogy: Like "pulling yourself up by your bootstraps" – using an initial simple version to build a better version of itself.