Compiler Design (CS-603) - Unit 2 Short Notes

UNIT 2: COMPILER DESIGN - SHORT NOTES

I. COMPILER STRUCTURE & OVERVIEW

Phases of a Compiler

A compiler transforms source code into target code through a sequence of analysis (frontend) and synthesis (backend) phases.

Supporting Phases:

• Symbol Table Manager: Stores identifier info (type, scope, address).

• Error Handler: Detects & reports errors at each phase.

• Pre-processor & Input Buffering: Handles macros, file inclusion, and efficient character reading.

DiagramSEARCH: "compiler phases diagram six phases"

Compiler vs. Interpreter

Frontend vs. Backend Compiler Model

Cross Compiler

A compiler running on machine A that generates code for machine B (where A ≠ B). Used in embedded systems development.

Pre-processing & Input Buffering

• Pre-processing: Macro expansion, file inclusion (#include), conditional compilation (#ifdef).

• Input Buffering: Reads source characters in blocks (e.g., 2-buffer scheme with sentinel # to avoid boundary checks). Reduces I/O overhead.

II. LEXICAL ANALYSIS

Role & Token Specification

• Role: First phase. Reads source characters, groups them into lexemes, and produces a stream of tokens (token-name, attribute-pointer).

• Token Specification: Defined by regular expressions (e.g., id = letter(letter|digit)*, num = digit+).

Lexical Errors

Invalid characters, unterminated comments/strings, invalid numeric constants. Often handled by error token and recovery (e.g., skip to next whitespace).

Recognition of Identifiers & Keywords

1. Lexer matches longest possible lexeme.

2. If lexeme matches a keyword pattern (e.g., if, while), returns keyword token.

3. If lexeme matches id pattern, checks symbol table:

   • If present → returns existing entry.

   • If new → inserts into symbol table, returns pointer.

Finite State Machines (FSM)

• Definition: Abstract machine (states, transitions) recognizing regular languages.

• Applications: Token recognition (each token = FSM), pattern matching.

• Limitations: Cannot count (e.g., a^n b^n), cannot handle nested/recursive structures (needs PDA).

LEX Tool

• Purpose: Lexical analyzer generator.

• Input: Specification file with patterns (regex) and actions (C code).

• Output: lex.yy.c → a yylex() function that returns tokens.

• Usage: lex prog.l → gcc lex.yy.c -ll → a.out.

Regular Expressions for Tokens

• digit = [0-9]

• letter = [a-zA-Z]

• id = letter(letter|digit)*

• num = digit+(.digit+)?(E[+-]?digit+)?

• comment = "/*"(.|\n)*"*/"

III. SYNTAX ANALYSIS (PARSING)

Parser Types & Comparison

LL(1) Parsing

• LL(1) Grammar: For any two productions A → α | β:

  1. FIRST(α) ∩ FIRST(β) = ∅

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

• Predictive Parsing Table: M[A, a] contains production A → α if:

  • a ∈ FIRST(α), or

  • ε ∈ FIRST(α) and a ∈ FOLLOW(A).

• Recursive Descent Parser: A set of recursive procedures, one per non-terminal. Without backtracking requires LL(1) grammar.

• Left Factoring: Factor common prefixes.

  • A → αβ1 | αβ2 becomes A → αA', A' → β1 | β2.

• Left Recursion Elimination:

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

  • Indirect: Reorder productions or introduce new non-terminals.

LR Parsing

• LR Parsers: Use shift-reduce parsing. Most powerful (handle all deterministic CFGs).

• LR(0) Items: Productions with a dot • showing progress: A → α•β.

• SLR Parsing:

  1. Build canonical collection of LR(0) items.

  2. Construct ACTION and GOTO tables.

  3. Use FOLLOW sets to resolve conflicts on reduce actions for A → α•.

• LALR Parsing: States with identical cores (items without lookahead) are merged. More powerful than SLR, less than canonical LR(1).

• Comparison:

  | Parser | States (approx.) | Power | Conflict Resolution | | :--- | :--- | :--- | :--- | | SLR(1) | Smallest | Weakest | Uses FOLLOW(A) | | LALR(1) | Medium | Medium | Merges cores, uses lookahead | | LR(1) | Largest | Most powerful | Full lookahead per item |

Grammar Analysis

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

  • FIRST(a) = {a}

  • FIRST(αβ) = FIRST(α) ∪ (FIRST(β) if ε∈FIRST(α))

  • FIRST(A) for non-terminal: FIRST(α) for all A→α.

• FOLLOW(A): Set of terminals that can appear immediately after A in some sentential form.

  • $ ∈ FOLLOW(S)

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

  • If A → αB or A → αBβ with ε∈FIRST(β), then FOLLOW(A) ⊆ FOLLOW(B).

• Ambiguity in CFG: A grammar is ambiguous if a string has >1 parse tree or >1 leftmost/rightmost derivation. Example: E → E + E | E * E | id for id+id*id.

• Closure Properties of CFLs: CFLs are closed under union, concatenation, Kleene star, substitution, reversal. NOT closed under intersection, complement.

IV. SYNTAX-DIRECTED TRANSLATION & SEMANTIC ANALYSIS

Syntax-Directed Definitions (SDD) & Translations (SDT)

• SDD: CFG + semantic rules (actions) on productions. Evaluates attributes.

• SDT: SDD with semantic actions embedded in productions.

• Synthesized Attributes: Value computed from children's attributes. Flows up the parse tree.

  • Example: E.value = E1.value + T.value in E → E1 + T.

• Inherited Attributes: Value computed from parent/siblings. Flows down or across the tree.

  • Example: S.in = true in S → if (E) S1 else S2 to propagate condition.

• S-attributed SDT: All attributes are synthesized. Evaluated in bottom-up order (e.g., LR parsing).

• L-attributed SDT: Inherited attributes defined by:

  1. Parent's inherited attributes.

  2. Siblings' synthesized attributes to the left.

  • Can be evaluated in top-down (LL) or bottom-up order.

• Annotated Parse Tree: Parse tree with attribute values at each node.

• Dependency Graph: Directed graph of attribute dependencies. Cycle = circular definition (error).

Type Checking & Type Systems

• Role of Type Checker: Ensures operator-operand type compatibility, enforces type rules, infers types.

• Type Expressions: Built from basic types using type constructors (array, pointer, function).

  • int, float, array(3, int), ptr(int), func(int)→float.

• Type Equivalence:

  • Name equivalence: Two types are same if declared with same name (e.g., typedef).

  • Structural equivalence: Types are same if their structures are identical (e.g., array(10, int) vs array(5, array(2, int))).

• Type Conversion:

  • Implicit (coercion): Automatic by compiler (e.g., int → float in float f = 5).

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

Intermediate Representations (IR)

• Three-Address Code (TAC): x = y op z (at most 3 addresses per instruction).

  • Quadruples: (op, arg1, arg2, result). Easy to optimize (arguments immutable).

  • Triples: (op, arg1, arg2). Result referenced by position. No temporary names, but harder to optimize (shared references).

  • Indirect Triples: Quadruples stored in an array; triples point to array indices. Allows easy reordering.

• Why Quadruples Preferred in Optimizing Compilers?

  \boxed{\text{Quadruples allow easy access to operands and results, facilitating optimizations like constant propagation and common subexpression elimination without modifying original structure.}}

• TAC Generation:

  • Expressions: Use translation rules (e.g., E → E1 + T generates t = E1.code || T.code || gen(E.val = t1 + t2)).

  • Control Flow:

    • if E then S1 else S2: E.true, E.false labels.

    • while E do S: begin: E.code, S.code, goto begin.

V. INTERMEDIATE CODE & BASIC BLOCKS

Flow Graph Construction

• Definition: Directed graph where nodes = basic blocks, edges = possible control flow.

• Construction:

  1. Partition TAC into basic blocks.

  2. Leader statements (first statement, target of jump, after jump) start new blocks.

  3. Add edges: fall-through from block i to i+1; jump edges from goto/if statements.

Basic Blocks

• Characteristics:

  • Single entry (first statement executed once).

  • Single exit (last statement controls exit).

  • Linear sequence (no jumps inside except at end).

• Partitioning Algorithm:

  1. Mark first statement as leader.

  2. Statement following a goto/if is leader.

  3. Statement immediately after leader is leader.

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

Directed Acyclic Graph (DAG)

• Definition: Directed graph with no cycles. Nodes = identifiers/constants, edges = computations.

• Construction Algorithm for Basic Block:

  1. For each statement x = y op z:

     • If y or z not yet in DAG → create leaf node.

     • If node for y op z exists → reuse it.

     • Create node for x (or reuse if already exists).

  2. Nodes with no children are common subexpressions.

• Applications:

  • Common Subexpression Elimination: Reuse existing node.

  • Dead Code Elimination: Nodes not used later (no path to output).

  • Code Generation: Order nodes for efficient evaluation (e.g., register allocation).

VI. CODE OPTIMIZATION

Principle Sources

Optimization Techniques

1. Common Subexpression Elimination (CSE): Recompute value only once. Use DAG to identify.

2. Copy Propagation: Replace x = y with uses of x by y (may enable CSE).

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

4. Loop-Invariant Code Motion: Move computations that produce same value in each iteration outside the loop.

   • Example: t = a * b inside loop where a,b unchanged → move before loop.

5. Peephole Optimization: Local, window-based (2-4 instructions) improvements:

   • Redundant load/store elimination.

   • Algebraic simplifications (x*1 → x).

   • Sequence replacement (MOV R1,R2; ADD R1,R3 → ADD R2,R3).

Loop Optimization (Detailed)

• Loop Invariant Code Motion:

  1. Identify invariant expressions (all definitions of variables used in expression are outside loop).

  2. Move to pre-header (new block before loop).

  3. Ensure safety (no side effects, no exceptions).

• Induction Variable Elimination: Replace variables that change linearly (i = i + 1) with loop index.

Local vs. Global Transformations

Three Areas of Optimization

1. Machine-Independent: IR-level (TAC). CSE, DAG, loop transformations.

2. Machine-Dependent: Target-specific. Register allocation, instruction selection, peephole.

3. Architecture-Specific: Exploits special hardware (e.g., vector instructions, cache lines).

VII. CODE GENERATION

Backpatching

• Concept: Maintain lists of unfilled jumps (for boolean expressions, if, while). Fill addresses when target known.

• Boolean Expressions: Generate code with true-list and false-list.

  • E → E1 or E2: E1.true and E2.true → E.true; E1.false + E2.false → E.false.

  • Backpatch E1.false to start of E2.code.

• Control Statements:

  • if E then S1: E.true → S1.code; E.false → next.

  • while E do S: begin: E.code; S.code; goto begin; backpatch E.true to S, E.false to after.

Register Allocation & Assignment

• Strategies:

  1. Register Descriptor: Tracks which variables are in which registers.

  2. Address Descriptor: Tracks where each variable can be found (register/memory).

• Allocation: Assign variables to registers (ideally keep frequently used in registers).

• Example: Use graph coloring:

  1. Build interference graph (nodes = variables, edge = live together).

  2. Color graph with k colors (registers).

  3. Spill if >k colors (store excess to memory).

Code Generation for Expressions & Statements

• Expressions: Generate TAC, then map to machine instructions (e.g., x = y + z → LOAD y, R1; ADD z, R1; STORE R1, x).

• Statements: Use backpatching for jumps, manage control flow.

VIII. STORAGE ALLOCATION & SYMBOL TABLE

Storage Allocation Strategies

Activation Record (AR) Model

Components (typical):

1. Return address (where to go after return).

2. Control link (dynamic link: pointer to caller's AR).

3. Access link (static link: for non-local vars in nested scopes).

4. Saved machine state (registers).

5. Parameters (passed by caller).

6. Local variables.

7. Temporaries.

DiagramCANVAS: Activation record stack with fields: return addr, control link, access link, saved regs, params, locals, temporaries

Symbol Table

• Purpose: Store identifier info (name, type, scope, address, line number).

• Data Structures:

  • Linear List: Simple, slow search (O(n)).

  • Hash Table: Fast (O(1) avg), handles collisions.

  • Binary Search Tree: Ordered, O(log n) search.

• Operations: insert(name, info), lookup(name), delete(name).

Polymorphic Functions & Overloading

• Polymorphic: Function works with multiple types (e.g., print(int), print(float)).

• Overloading: Same name, different parameter types.

  • Resolved at compile-time (static binding) by type checking and signature matching.

  • Example: sqrt(double), sqrt(complex).

IX. ERROR HANDLING & AUXILIARY TOPICS

Error Handling Phase

• Strategy: ** panic mode** (skip to synchronizing token), error productions, local correction (insert/delete token).

Dynamic Storage Allocation

• Heap Management: malloc(size), free(ptr).

• Issues: Fragmentation (external/internal), garbage collection (automatic reclamation).

Input Buffering (Sentinel Method)

• Two buffers (lexemeBegin, forward pointers).

• Sentinel (#) placed at end of each buffer to avoid boundary checks.

• When forward reaches sentinel, refill half-empty buffer.

EXAM TIPS & COMMON PITFALLS

[!TIP] Parsing Tables (SLR/LALR)

• SLR: Use FOLLOW(A) for reductions → may have spurious conflicts.

• LALR: Merge states with same core → fewer conflicts than SLR, same as LR(1) for common grammars.

• Always compute canonical collection first. State i has item [A → α•Bβ, a] → goto(i, B) includes [A → αB•β, a].

[!TIP] FIRST/FOLLOW Sets

• FIRST(ε) = {ε}.

• For FOLLOW(A), include $ if A is start symbol.

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

[!TIP] DAG Construction

• Process statements in order.

• Reuse node if y op z already exists (same operator, same operands).

• Final node for each variable = last assignment in block.

[!TIP] Backpatching

• Maintain lists (linked lists of pending jumps).

• makelist(i) returns list with i.

• merge(p1, p2) concatenates lists.

• backpatch(list, addr) fills all addr in list.

[!TIP] Activation Record

• Static link (access link) for non-local variables in nested procedures.

• Dynamic link (control link) to restore caller's AR.

• Parameters usually placed above return address (in caller's AR).

[!TIP] Storage Allocation

• Stack: Fast (pointer adjustment), supports recursion, but no explicit deallocation.

• Heap: Flexible, but fragmentation and overhead.

[!TIP] Common Mistakes

• Confusing synthesized (up) vs inherited (down/across) attributes.

• Forgetting to eliminate left recursion for top-down parsers.

• Miscomputing FIRST for nullable productions.

• Not partitioning TAC correctly into basic blocks (leaders).

• Assuming DAG nodes are only for expressions—they represent values of variables.