UNIT 4: Compiler Design - High-Impact Short Notes

Based on RGPV CS-603 Past Paper Analysis

I. Introduction and Compiler Structure

Phases of a Compiler (with block diagram):

1. Lexical Analysis: Scans source, produces tokens.

2. Syntax Analysis: Parses tokens into parse tree using CFG.

3. Semantic Analysis: Checks type consistency, annotates parse tree.

4. Intermediate Code Generation: Produces machine-independent IR (e.g., TAC).

5. Optimization: Improves IR for efficiency.

6. Code Generation: Maps IR to target machine code.

7. Symbol Table Management:贯穿 all phases.

8. Error Handling:贯穿 all phases.

Block Diagram Flow:

Source Program → Lexical Analyzer → Syntax Analyzer → Semantic Analyzer → Intermediate Code → Optimizer → Code Generator → Target Code

(Symbol Table & Error Handler interact with all phases)

Compiler vs Interpreter:

Frontend-Backend Model:

• Frontend: Language-dependent (lexical, syntax, semantic analysis). Output: IR (e.g., TAC).

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

• Advantages: Modularity, retargetability (same frontend for multiple machines), reusability.

• Disadvantages: Interface complexity, potential inefficiency from abstraction.

Pre-processing and Input Buffering:

• Pre-processing: Macro expansion, file inclusion, conditional compilation (e.g., #include, #define in C).

• Input Buffering: Double buffering (two buffers) to reduce I/O overhead; allows lookahead for token recognition.

Cross-compiler: Compiler running on machine A generates code for machine B (different ISA/OS).
Example: Compiling Android apps on x86 host for ARM target.

II. Lexical Analysis

Role: Read source characters, group into tokens, remove whitespace/comments, handle lexical errors, populate symbol table for identifiers.

Token Specification (using regex):

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

• Keyword: if, while, etc. (fixed strings)

• Constant: [0-9]+ (integer), [0-9]*\.[0-9]+ (float)

• Operator: +, -, *, /, =, etc.

• Punctuation: ;, ,, (, )

Regular Expressions for Tokens:

• Integer: [0-9]+

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

• Whitespace: [ \t\n]+ (skipped)

• Comment: //.* or /*.**/

Finite Automata (DFA/NFA):

• DFA: Single next state per input; efficient for implementation.

• NFA: Multiple next states possible; can have ε-transitions.

• Limitations: Cannot count or match nested structures (e.g., balanced parentheses) → need CFG.

LEX Tool:

• Specification sections:

  1. Definitions: regex macros (e.g., DIGIT [0-9]).

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

  3. User Code: C functions (e.g., main()).

• Generates lexical analyzer in C.

Error Handling in Lexical Analysis:

• Panic mode: Skip characters until valid delimiter (e.g., ;, }).

• Recovery: Insert missing character, delete extraneous character, replace with correct one.

• Lexical phase errors: Invalid characters, unterminated comments, malformed numbers.

III. Syntax Analysis (Parsing)

Parser Role: Check syntax using CFG, produce parse tree/abstract syntax tree.

Top-down vs Bottom-up Parsing:

Context-Free Grammars (CFG):

• Productions: A → α (A non-terminal, α string of terminals/non-terminals).

• Derivations:

  • Leftmost: Replace leftmost non-terminal first.

  • Rightmost: Replace rightmost non-terminal first.

• Parse Tree: Graphical representation of derivation.

• Ambiguity: String has >1 parse tree (e.g., if-else dangling else).

  Example: S → if S then S | if S then S else S | a → if a then if a then a else a ambiguous.

Left Recursion & Elimination:

• Immediate left recursion: A → Aα | β → eliminate:

  
  A → βA'
  
  A' → αA' | ε
  
  

• Indirect left recursion: Reorder non-terminals to eliminate.

Left Factoring:

• When multiple productions share common prefix: A → αβ1 | αβ2 →

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

Top-down Parsing:

• Recursive Descent with Backtracking: Try productions sequentially; may be exponential.

• Predictive Parsing (LL(1)): Use parsing table (no backtracking).

  • Properties:

    1. For A → α | β, FIRST(α) ∩ FIRST(β) = ∅.

    2. If ε ∈ FIRST(α), then FIRST(α) ∩ FOLLOW(A) = ∅.

  • Parsing Table Construction:

    • For A → α, for each a ∈ FIRST(α), set M[A,a] = A→α.

    • If ε ∈ FIRST(α), for each b ∈ FOLLOW(A), set M[A,b] = A→α.

    • Else error.

Bottom-up Parsing (LR Parsing):

• LR(k): Left-to-right scan, Rightmost derivation (reverse), k lookahead.

• LR(0) Items: Production with dot · (e.g., S → L · = R).

• States: Sets of items (closure + goto).

• Parsing Tables: ACTION (shift/reduce/accept/error) and GOTO (non-terminal transitions).

Comparison of SLR, LALR, LR:

[!TIP]

• SLR may have spurious conflicts because FOLLOW(A) may contain terminals not in FIRST(α).

• LALR merges states with same core (LR(0) items), losing some lookahead precision.

• LR(1) has largest tables but no false conflicts.

First & Follow Sets:

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

  • If X → ε, include ε.

• FOLLOW(A): Set of terminals that appear immediately after A in some sentential form. Include $ for start symbol.

• Computation: Standard algorithms (see textbooks).

Error Detection & Recovery:

• Syntactic errors: Missing/extra tokens, mismatched parentheses.

• Recovery:

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

  • Phrase level: Insert/delete/replace tokens to continue parsing.

  • Error productions: Add productions for common errors.

IV. Semantic Analysis

Role: Check semantic consistency (type, scope), enrich AST with types, attributes, generate intermediate code via SDT.

Attribute Grammars:

• Attributes: Values associated with grammar symbols.

• Synthesized: Computed from children (bottom-up). Example: E.value = E1.value + T.value.

• Inherited: Computed from parent/siblings (top-down). Example: array index type from parent.

• Differences:

S-attributed Definitions: Only synthesized attributes. Evaluated in bottom-up order (e.g., LR parsing).
L-attributed Definitions: Inherited attributes from left siblings and parent only. Allows top-down evaluation (e.g., LL parsing).
Example:

S → L = R   { L.place = newtemp(); R.place = L.place; }

L → * R     { L.place = R.place; }

L → id      { L.place = id.place; }

Here L.place is inherited from parent S and left sibling? Actually in S → L = R, L.place is set by S? Wait, better example:

A → B C D

B.inh = A.inh   // inherited from parent

C.inh = B.synth // from left sibling

L-attributed: C.inh from left sibling B.synth allowed.

Dependency Graph & Annotated Parse Tree:

• Dependency graph: Nodes = attribute instances; edges = dependency (if attribute X.a depends on Y.b).

• Annotated parse tree: Parse tree with attribute values filled after evaluation.

• Evaluation order: Topological sort of dependency graph (must be acyclic for well-defined grammar).

Type Checking:

• Type expressions: Basic types (int, float), arrays ([10]int), functions ((int)→float), products ((int, float)).

• Type equivalence:

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

  • Structural equivalence: Same structure (e.g., [10]int ≡ [10]int).

• Type conversion:

  • Implicit (coercion): int → float in assignment.

  • Explicit (cast): (float) i.

• Polymorphic functions: Operate on multiple types (e.g., length(list<T>)).

• Overloading: Same name, different parameter types (e.g., print(int), print(string)).

V. Intermediate Code Generation

Three-Address Code (TAC):

• Form: x = y op z (or x = op y, goto L, if x relop y goto L).

• Forms:

  | Quadruples | Triples | Indirect Triples | |----------------------|----------------------|---------------------------| | (op, arg1, arg2, result) | (op, arg1, arg2) | List of pointers to triples | | Explicit temporaries | No result field; refer by position | Allows easy rearrangement | | Preferred in optimizing compilers (easy renaming, optimization) | Harder to optimize | Used with DAG |

TAC Generation Examples:

• Expression a = b + c * d:

  
  t1 = c * d
  
  a = b + t1
  
  

• Control Structures:

  • if (B) S1 else S2:

    
    B.true = ?, B.false = ?
    
    code for B
    
    if B.false goto L2
    
    code for S1
    
    goto L1
    
    L2: code for S2
    
    L1:
    
    

  • while (B) S:

    
    L1: code for B
    
    if B.false goto L2
    
    code for S
    
    goto L1
    
    L2:
    
    

Directed Acyclic Graph (DAG):

• Nodes: Operations (internal), variables/constants (leaves).

• Construction Algorithm (for basic block):

  1. Initialize empty DAG.

  2. For each statement x = y op z in order:

     • Get/create node for y, z.

     • If node n with same op and children exists, use n; else create new node.

     • Associate x with that node (may have multiple names).

• Applications:

  • Common subexpression elimination (shared nodes).

  • Dead code elimination (unreferenced nodes).

  • Efficient code generation (evaluate leaves once, propagate values).

• Example: For a = b + c; d = b + c; → single + node with two parents a and d.

Backpatching:

• Purpose: Fill addresses of jump instructions for boolean expressions and flow-of-control statements.

• Mechanism: Maintain lists of unfilled jumps (instruction indices).

• Boolean Expressions:

  • B → B1 or B2:

    • B1.false merged with B2.false → B.false.

    • B.true = B1.true (after B1 code, backpatch B1.false to B2 code).

  • B → not B1: swap true/false lists.

• Flow-of-control Statements:

  • if B then S1 else S2:

    • Generate B with true_list, false_list.

    • Backpatch true_list to S1 start.

    • Backpatch false_list to S2 start.

    • S.next = merge(S1.next, S2.next).

  • while B do S:

    
    L1: code for B
    
    if B.false goto L2
    
    code for S
    
    goto L1
    
    L2:
    
    

    • B.true backpatched to S start; B.false to after loop.

Flow Graphs & Basic Blocks:

• Basic Block: Sequence of statements with:

  1. Single entry (first statement executed only from start).

  2. Single exit (last statement only way to exit).

  3. Straight-line code (no jumps inside except at end).

• Construction:

  1. Identify leaders: First statement, target of jump, statement after jump.

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

• Flow Graph: Nodes = basic blocks; edges = possible control transfers (jumps).

• Characteristics: Used for optimization (data flow analysis), register allocation.

VI. Code Optimization

Goals & Types:

• Goals: Improve execution speed, reduce memory, power efficiency.

• Types:

  • Machine-independent: On IR (TAC, DAG) – constant folding, CSE.

  • Machine-dependent: On target code – peephole, register allocation.

• Local vs Global:

  • Local: Within a basic block (e.g., CSE, constant propagation).

  • Global: Across blocks (e.g., dead code elimination, loop optimization).

• Loop Optimization: Most impactful (loops execute repeatedly).

Optimization Techniques (with examples):

Use of DAG in Optimization:

• Construct DAG for basic block → eliminate CSE automatically (shared nodes).

• Generate code from DAG in reverse postorder (evaluate leaves first).

• Example: For a=b+c; d=b+c; e=a*d; → DAG has one + node for b+c, shared by a and d.

Data Flow Analysis (Brief):

• Computes information at program points (e.g., reaching definitions, live variables).

• Equations: IN[n] = ∪ OUT[p] for predecessors p; OUT[n] = gen[n] ∪ (IN[n] - kill[n]).

• Used for global optimizations (constant propagation, dead code).

VII. Code Generation

Issues:

1. Instruction selection: Choose target instructions for IR.

2. Register allocation: Assign variables to limited registers.

3. Evaluation order: Minimize registers, avoid hazards.

Register Allocation & Assignment:

• Graph Coloring Algorithm:

  1. Build interference graph: nodes = variables, edge if two variables live simultaneously.

  2. Color graph with k colors (registers).

  3. If not k-colorable, spill variable (store in memory) and retry.

• Linear Scan Algorithm:

  1. Sort variables by live range start.

  2. Allocate registers linearly, freeing when live range ends.

  3. Spill when no register free.

  • Faster but less optimal than graph coloring.

Code Generation from TAC/DAG:

• Expressions: Generate load/store, arithmetic instructions. Use registers for temporaries.

• Control Structures: Use backpatching to fill jump addresses.

• Example: For if (a<b) x=y; else x=z;

  
  if a < b goto L1
  
  x = z
  
  goto L2
  
  L1: x = y
  
  L2:
  
  

Instruction Selection Strategies:

• Tree rewriting: Match IR tree to machine instruction patterns.

• Pattern matching: Use templates for common sequences.

VIII. Runtime Environment

Storage Organization:

Activation Record (AR):

• Model/Format (typical for stack allocation):

  
  [Actual parameters]   // from caller
  
  [Return address]      // where to continue after return
  
  [Control link]        // pointer to caller's AR (dynamic chain)
  
  [Access link]         // pointer to enclosing AR (for nested scopes)
  
  [Saved registers]     // if needed
  
  [Local variables]     // including temporaries
  
  [Temporaries]         // intermediate values
  
  

• Procedure Call/Return:

  • Call: Push AR, set control/access links, jump.

  • Return: Restore registers, pop AR, jump to return address.

Symbol Table Management:

• Organization:

  • Linear list: Simple, slow lookup (O(n)).

  • Hash table: Fast average lookup (O(1)), handles collisions.

  • Tree structures (BST, B-tree): Ordered, efficient range queries.

• Operations:

  • insert(name, attributes)

  • lookup(name) → attribute entry

  • delete(name) (for scopes)

• Scope Handling: Nested scopes → use access links (static chain) or display (array of AR pointers).

IX. Additional & Peripheral Topics

Properties of Optimizing Compilers:

1. Preserve semantics: Output program must be equivalent.

2. Improve performance: Most cases faster/smaller.

3. Efficient compilation: Not too slow.

4. Modular: Separate analysis and transformation.

Tools for Code-Improving Transformations:

• DAG: For local optimization (CSE).

• Data flow equations: For global analysis (reaching definitions, live variables).

• Static Single Assignment (SSA): Simplify data flow analysis.

• Machine descriptions: For instruction selection (e.g., codegen in lcc).

Closure Properties of CFG:

• CFLs closed under: Union, Concatenation, Kleene star.

• Not closed under: Intersection, Complement (except with additional constraints).

Theory of Computation (Peripheral):

• Recursive languages closed under complement (unlike CFLs).

• Automata equivalence: DFA ≡ NFA (in language recognition power).

Key Formulas & Algorithms

First & Follow (Algorithm Sketch):

1. FIRST(X):

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

   • If X → ε, add ε.

   • If X → Y1...Yk, add FIRST(Y1) (excluding ε); if all Yi derive ε, add ε.

2. FOLLOW(A):

   • If S start symbol, add $ to FOLLOW(S).

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

   • If β ⇒* ε, add FOLLOW(B) to FOLLOW(A).

DAG Construction Algorithm:

for each statement x = y op z in order:

    node_y = get_node(y)  // create if not exists

    node_z = get_node(z)

    if node n with op and children (node_y, node_z) exists:

        x_node = n

    else:

        x_node = new node(op, node_y, node_z)

    associate x with x_node

Backpatching for if B then S1 else S2:

B.code with true_list, false_list

backpatch(B.true_list, S1.instr)

backpatch(B.false_list, S2.instr)

S.next = merge(S1.next, S2.next)

Loop Invariant Code Motion:

• Identify statements in loop where all definitions are loop-invariant (no definition changes within loop).

• Move such statements before loop (ensure no side effects, and moved code executed only once).

[!EXAM TIPS]

• DAG vs TAC: DAG eliminates CSE automatically; TAC is linear.

• SLR vs LALR: SLR uses FOLLOW for reductions → may have conflicts; LALR uses precise lookahead → fewer conflicts.

• S vs L-attributed: L-attributed allows inherited from left siblings → more flexible for top-down.

• Backpatching: Always maintain lists; patch after generating code for substatements.

• Register Allocation: Graph coloring optimal but expensive; linear scan faster for JITs.

• Activation Record: Access link for non-local variables in nested procedures; control link for dynamic chain.

• Type Checking: Structural equivalence more flexible than name equivalence.

• Constant Folding vs Propagation: Folding evaluates expressions; propagation replaces variables with constants.

• Peephole: Look for redundant loads/stores, jumps to jumps, algebraic simplifications.

• LEX: Patterns are regex; actions are C code; yytext holds matched string.