Cheatsheet Compiler Design - RRB JE for Computer Science Engineering -

1. Compiler Phases

1.1 Overview

2. Lexical Analysis

2.1 Key Concepts

2.2 Regular Expressions

2.3 Finite Automata

• RE → NFA: Thompson's Construction
• NFA → DFA: Subset Construction (Powerset Construction)
• DFA Minimization: State reduction using equivalence classes
• Number of states in minimized DFA ≤ Number of states in DFA

3. Syntax Analysis (Parsing)

3.1 Context-Free Grammars

3.2 Derivations

3.3 Parse Trees vs. Syntax Trees

• Parse Tree: Shows complete derivation with all grammar symbols
• Abstract Syntax Tree (AST): Condensed representation, operators as internal nodes

3.4 Top-Down Parsing

3.4.1 Recursive Descent Parsing

• Each non-terminal has a procedure
• May require backtracking
• Predictive parsing: No backtracking with lookahead

3.4.2 FIRST and FOLLOW Sets

3.4.3 LL(1) Parsing

• Left-to-right scan, Leftmost derivation, 1 lookahead symbol
• Uses parsing table M[N, T]
• Table entry M[A, a] = {A → α} if a ∈ FIRST(α) or (ε ∈ FIRST(α) and a ∈ FOLLOW(A))
• No entry with multiple productions → Grammar is LL(1)
• LL(1) conditions: No ambiguity, no left recursion, left-factored

3.5 Bottom-Up Parsing

3.5.1 Shift-Reduce Parsing

• Handle: Substring matching RHS of production in rightmost derivation
• Viable Prefix: Prefix of right-sentential form not extending past handle

3.5.2 LR Parsing

• Left-to-right scan, Rightmost derivation in reverse
• LR(0), SLR(1), LALR(1), CLR(1) (Canonical LR)
• Power hierarchy: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1) (= LR(1)).

3.5.3 LR(0) Items

• Item: Production with dot (•) in RHS indicating position
• A → •XYZ, A → X•YZ, A → XY•Z, A → XYZ•
• Augmented Grammar: Add S' → S to original grammar

3.5.4 SLR(1) Parsing

• Construct canonical LR(0) collection of items
• Reduce by A → α if [A → α•] in state and lookahead ∈ FOLLOW(A)
• Conflicts: shift-reduce, reduce-reduce

3.5.5 CLR(1) vs LALR(1)

• LALR(1) may introduce shift-reduce or reduce-reduce conflicts not present in CLR(1).
• LALR(1) may introduce reduce-reduce conflicts not in CLR(1)

3.5.6 Operator Precedence Parsing

• Uses precedence relations: ⋖ (yields precedence), ≐ (equal precedence), ⋗ (takes precedence)
• Applicable only to operator grammars (no ε-productions and no two adjacent non-terminals)

4. Syntax-Directed Translation

4.1 Definitions

4.2 Attribute Grammar Types

• All S-attributed grammars are L-attributed
• L-attributed can be evaluated during LL parsing

5. Intermediate Code Generation

5.1 Intermediate Representations

5.2 Three-Address Code Instructions

• Assignment: x = y op z, x = op y, x = y
• Copy: x = y
• Unconditional jump: goto L
• Conditional jump: if x relop y goto L
• Procedure call: call p, n; return y
• Indexed assignment: x = y[i], x[i] = y
• Address operations: x = &y, x = *y, *x = y

5.3 Translation of Expressions

• Postfix notation: No parentheses needed, operands before operators
• Infix to Postfix: Use operator stack with precedence rules
• DAG (Directed Acyclic Graph): Identifies common subexpressions

5.4 Boolean Expressions

• Numerical representation: true = 1, false = 0
• Short-circuit evaluation: Conditional jumps, more efficient
• Backpatching: Fill in addresses of jumps during one-pass compilation

5.5 Control Flow Translation

• If-then-else: Generate labels for true, false, and next
• While loop: Test at beginning, jump back to test
• For loop: Initialization, test, increment, body
• Switch-case: Jump table or sequence of conditional jumps

6. Code Optimization

6.1 Types of Optimization

6.2 Basic Block

• Sequence of consecutive statements with single entry and single exit
• Leaders: First statement, target of jump, statement after jump
• Control Flow Graph (CFG): Nodes are basic blocks, edges are control flow

6.3 Local Optimizations

6.4 Global Optimizations

6.4.1 Data Flow Analysis

6.4.2 Reaching Definitions

• Forward analysis, union over all paths
• gen[B]: Definitions generated in B
• kill[B]: Definitions killed in B
• out[B] = gen[B] ∪ (in[B] - kill[B])
• in[B] = ∪ out[P] for all predecessors P

6.4.3 Live Variable Analysis

• Backward analysis, union over all paths
• use[B]: Variables used before definition in B
• def[B]: Variables defined in B
• in[B] = use[B] ∪ (out[B] - def[B])
• out[B] = ∪ in[S] for all successors S

6.4.4 Available Expressions

• Forward analysis, intersection over all paths
• e_gen[B]: Expressions computed in B
• e_kill[B]: Expressions killed in B
• out[B] = e_gen[B] ∪ (in[B] - e_kill[B])
• in[B] = ∩ out[P] for all predecessors P

6.5 Loop Optimizations

• Dominator: Node d dominates n if every path to n goes through d
• Natural Loop: Single entry (header), back edge from node to dominating header

7. Runtime Environments

7.1 Storage Organization

7.2 Activation Records

• Components: Return address, arguments, local variables, saved registers, control link, access link
• Frame pointer (FP): Points to fixed location in activation record
• Stack pointer (SP): Points to top of stack

7.3 Parameter Passing

7.4 Access Links

• Static scope: Access link points to activation record of lexically enclosing procedure
• Nesting depth: Level of nesting in program structure
• Follow access links to find non-local variables

7.5 Heap Management

7.6 Garbage Collection

8. Code Generation

8.1 Issues in Code Generation

• Instruction selection: Choose appropriate machine instructions
• Register allocation: Assign variables to registers
• Instruction ordering: Optimize instruction sequence

8.2 Register Allocation

8.2.1 Register Descriptors

• Track which variables are in which registers
• Address descriptors: Track locations of variable values

8.2.2 Graph Coloring

• Interference graph: Nodes are variables, edges connect simultaneously live variables
• k-colorable if chromatic number ≤ k (k = number of registers)
• Spilling: Store variable in memory when insufficient registers

8.3 Instruction Selection

• Tile IR with machine instruction patterns
• Tree pattern matching for expression evaluation
• Consider cost of different instruction sequences

8.4 Peephole Optimization

9. Error Handling

9.1 Error Types

9.2 Error Recovery Strategies

10. Important Formulas and Facts

10.1 Time Complexity

• Lexical analysis: O(n) where n = input length
• LL(1) parsing: O(n)
• LR parsing: O(n)
• NFA to DFA conversion: O(2ⁿ) worst case where n = NFA states
• DFA minimization: O(n log n) using Hopcroft's algorithm

10.2 Grammar Properties

• Every regular language has a CFG
• Not all CFLs are regular
• Ambiguous grammar cannot be LL(1) or LR(k)
• Left-recursive grammar cannot be LL(1)
• Every LL(1) grammar is unambiguous
• Every LR(1) grammar is unambiguous

10.3 Parsing Power

• LL(1) ⊂ LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)
• Number of LR(0) states ≤ Number of CLR(1) states
• Number of SLR(1) states = Number of LR(0) states
• Number of LALR(1) states = Number of SLR(1) states

10.4 Optimization

• Basic block optimization: Always safe, preserves semantics
• Loop optimization: High impact on performance
• Data flow equations: Iterated until fixed point reached
• Optimizations must preserve program semantics