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

UNIT 3: COMPILER DESIGN

I. INTRODUCTION & COMPILER STRUCTURE

A compiler is a translator that converts a program written in a source language (high-level) to an equivalent program in a target language (machine code/assembly).

Phases of a Compiler

The compilation process is divided into two main parts:

1. Analysis (Front End): Understands the source program.

   • Lexical Analysis (Scanning): Reads input characters, groups them into lexemes, and produces a stream of tokens.

   • Syntax Analysis (Parsing): Organizes tokens into a hierarchical structure (parse tree/abstract syntax tree) based on grammar rules.

   • Semantic Analysis: Checks for semantic consistency (e.g., type checking) and annotates the parse tree with attributes.

2. Synthesis (Back End): Generates the target program.

   • Intermediate Code Generation: Produces an intermediate representation (e.g., Three-Address Code) that is easy to generate and translate.

   • Code Optimization: Transforms the intermediate code for efficiency (speed, size) without changing meaning.

   • Code Generation: Maps the optimized intermediate code to the target machine language, allocating registers and memory.

3. Supporting Phases:

   • Symbol Table Management: Stores information about identifiers (name, type, scope, address).

   • Error Handling: Detects and reports errors at various phases, attempting recovery.

[!TIP] Exam Focus: Be prepared to draw the standard 6-phase diagram and state the output of a sample statement (e.g., id1 = id2 + id3 * 50) at each phase.

Compiler vs. Interpreter

Cross Compiler

A compiler that runs on one machine (host) but generates code for a different machine (target). Essential for embedded systems development.

Pre-processing and Input Buffering

• Pre-processor: Handles macro expansion, file inclusion, and conditional compilation before the main compilation begins.

• Input Buffering: Used by the lexical analyzer to read source characters efficiently. A common technique is using two buffers (primary and secondary) with a sentinel character to detect end-of-file and minimize I/O overhead.

Frontend vs. Backend Compiler Model

• Frontend: Machine-independent phases (Lexical, Syntax, Semantic Analysis, Intermediate Code Gen). Generates an intermediate representation (IR).

• Backend: Machine-dependent phases (Optimization, Code Generation). Takes IR as input.

• Advantages: Portability (same frontend for multiple targets), Modularity, Reusability of optimization modules.

• Disadvantages: Overhead of IR generation and maintenance, potential loss of source-level information.

II. LEXICAL ANALYSIS (SCANNING)

Role & Specification of Tokens

• Role: Reads character stream → groups into lexemes → identifies token type (e.g., keyword, identifier, operator, literal). Removes whitespace/comments.

• Specification: Tokens are described by regular expressions (patterns). E.g., identifier = letter (letter | digit)*.

Lexical Errors

Errors that cannot be recognized by the scanner (e.g., illegal character, unterminated comment). Often handled by panic mode (discard characters until a valid delimiter is found).

Recognition of Identifiers & Keywords

• Keywords (e.g., if, while) are reserved words. They have fixed patterns and are matched before the general identifier pattern.

• Identifiers match a general pattern (e.g., [a-zA-Z_][a-zA-Z0-9_]*). The scanner returns a token id and the lexeme (string) to the symbol table manager.

LEX Tool (LEX/YACC)

• LEX is a lexical analyzer generator.

• Input file has three sections: definitions, rules (pattern action), and user code.

• It generates a C program (lex.yy.c) that implements the scanner using DFA (from regex).

Finite State Machine (FSM)

• A deterministic finite automaton (DFA) is constructed from the union of all token regex patterns.

• The scanner simulates the DFA on the input string to recognize tokens.

• Applications: Token recognition, pattern matching.

• Limitations: Cannot count (e.g., balanced parentheses) or remember unbounded history → not suitable for nested structures (requires a pushdown automaton/parser).

[!TIP] Common Pitfall: Remember that a lexeme is the actual character sequence, while a token is the category (type) assigned to it.

III. SYNTAX ANALYSIS (PARSING)

Parser Types & Classification

Grammar Analysis & Transformation

• Context-Free Grammar (CFG): G = (V, T, P, S) where V = non-terminals, T = terminals, P = productions, S = start symbol.

• Ambiguity: A grammar is ambiguous if a string has >1 parse tree or >1 leftmost/rightmost derivation. Must be resolved for unambiguous parsing.

• Left Recursion:

  • Immediate: A -> Aα (direct). Causes infinite loop in top-down parsers.

  • Indirect: A -> Bα, B -> Aβ.

  • Elimination (Immediate): A -> Aα | β becomes A -> βA', A' -> αA' | ε.

• Left Factoring: Eliminates common prefixes to enable predictive parsing. A -> αβ1 | αβ2 becomes A -> αA', A' -> β1 | β2.

First & Follow Sets Computation

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

  • If X -> ε, then ε ∈ FIRST(X).

  • For X -> Y1 Y2 ... Yk, add FIRST(Yi) for i=1..k until ε is not in FIRST(Yi). If all Yi derive ε, add ε.

• FOLLOW(X): Set of terminals that can appear immediately to the right of X in some sentential form. If X is at the end, add $ (end-marker).

  • For A -> αXβ, add FIRST(β) - {ε} to FOLLOW(X).

  • If β =>* ε (or X is at end), add FOLLOW(A) to FOLLOW(X).

[!TIP] High Frequency: Computing FIRST/FOLLOW is a prerequisite for constructing LL(1) and SLR parsing tables.

Bottom-Up Parsing & LR Parsers

LR Parsing Principle: Uses a stack for grammar symbols and an input buffer. Action based on parsing table [state, symbol] → shift, reduce, accept, error.

Construction of Parsing Tables (Algorithm Overview):

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

2. Generate LR(0) Items: [A -> α・β] (・ marks parse position).

3. Build Canonical Collection: States are sets of items. Closure and Goto functions.

4. Construct Action/Goto Table:

   • Shift: On terminal a from state i to state j (via Goto).

   • Reduce: On item [A -> α・] in state i, for each a ∈ FOLLOW(A), set ACTION[i, a] = reduce A->α.

   • Accept: On [S' -> S・].

   • Goto: On non-terminal A from state i to j.

Differences among SLR, LALR, and LR Parsers:

[!TIP] Exam Crucial: You must be able to construct SLR and LALR parsing tables for a given grammar. The key steps are: (1) Augment grammar, (2) Find LR(0) items, (3) Build canonical collection, (4) For SLR: use global FOLLOW for reductions. For LALR: merge states with same LR(0) core, union lookaheads, then use merged FOLLOW for reductions.

IV. SYNTAX-DIRECTED TRANSLATION (SDT) & SEMANTIC ANALYSIS

Attributes & Annotated Parse Trees

• Attribute: An abstract value associated with a grammar symbol (e.g., type, value, address).

• Synthesized Attribute: Value computed from children in the parse tree. Flows upwards.

  • Example: E.value in E -> E1 + T where E.value = E1.value + T.value.

• Inherited Attribute: Value computed from parent/siblings. Flows downwards or sideways.

  • Example: S.in (incoming type environment) in S -> if (E) S1 else S2.

• Dependency Graph: Directed graph showing dependencies among attribute instances in a parse tree. A cycle indicates circular definition (error).

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

• S-attributed Definition: Only synthesized attributes. Evaluated in a bottom-up order (post-order traversal). Easy with LR parsers.

• L-attributed Definition: Attributes are either synthesized or inherited where inherited attributes depend only on:

  1. Parent's attributes.

  2. Siblings to the left.

  • Can be evaluated in a single left-to-right traversal (suitable for top-down parsers).

[!TIP] Key Difference: Inherited attributes get values from context (parent/left siblings), synthesized from children. L-attributed is a restricted form allowing top-down evaluation.

Type Checking & Type Systems

• Role of Type Checker: Ensures semantic correctness of operations (e.g., no bool + int), verifies function calls (number/types of arguments), and enforces type compatibility in assignments.

• Type Expressions: Built from base types (int, real, char) using type constructors (array, record, pointer, function).

  • Example: array[1..10] of record {x: int, y: real}.

• Equivalence of Type Expressions:

  • Name Equivalence: Two types are equivalent if they have the same name (or declaration). Strict.

  • Structural Equivalence: Two types are equivalent if their type expressions are identical (after expanding aliases). More flexible.

• Type Conversion:

  • Implicit (Coercion): Automatically performed by compiler (e.g., int to real in 5 + 3.2). May lose precision.

  • Explicit (Cast): Programmer-specified conversion (e.g., (int) x).

• Polymorphic Functions & Overloading:

  • Polymorphic: Function works with multiple types (e.g., length(list) for any list type). Often requires type variables.

  • Overloading: Same function name for different parameter type lists (e.g., print(int), print(real)). Resolved at compile-time (overload resolution).

Intermediate Code Generation Techniques

Three-Address Code (TAC): Statements with at most three operands (usually two sources, one destination). x = y op z.

[!TIP] Why Quadruples? They have explicit result fields, making common subexpression elimination and copy propagation simpler during optimization.

Syntax-Directed Translation Schemes (SDTs): Embed semantic actions (code snippets) within productions. For L-attributed schemes, actions can be placed anywhere; for S-attributed, only at the right end.

SDT for Infix to Postfix (Example):

E -> E1 + T { print('+'); }

  | T

T -> T1 * F { print('*'); }

  | F

F -> ( E ) 

  | id { print(id.name); }

Generation of TAC for Code Segments:

• Conditionals (if, if-else): Use backpatching for jump addresses.

• Loops (while): Structure: L1: <cond>, if false goto L2, <body>, goto L1, L2:.

• Switch: Generate TAC for each case label, use a jump table or sequence of compares.

V. INTERMEDIATE CODE & OPTIMIZATION

Basic Blocks & Flow Graphs

• Basic Block: A sequence of consecutive statements with:

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

  2. Single exit (last statement is the only one that can transfer control outside).

• Leader Statements: First statement of a basic block. A statement is a leader if:

  1. It is the first statement.

  2. It follows a conditional/unconditional jump.

  3. It is the target of a jump.

• Construction: Identify leaders → partition statements into blocks starting at each leader.

• Flow Graph: Nodes = basic blocks. Edges = possible control flow transfers ( jumps between blocks).

Directed Acyclic Graph (DAG)

• Definition: A directed graph with no cycles. Nodes represent values (variables, constants, temporaries). Edges represent operations.

• Construction from Basic Block:

  1. For each statement x = y op z, create a node N labeled op with edges from nodes for y and z.

  2. If a node for y op z already exists (same operator, same children), reuse it (common subexpression).

  3. Attach x as an attribute to the node N (for copy propagation).

  4. Delete any statement that assigns to a variable whose value is already available at a node.

• Applications:

  • Common Subexpression Elimination (CSE): Reuse existing node instead of creating new.

  • Copy Propagation: Replace uses of a variable with its defining expression.

  • Dead Code Elimination: Remove nodes with no live outputs.

  • Constant Folding: Evaluate const op const at compile time.

  • Register Allocation: Nodes represent values that can share a register if their lives do not overlap.

[!TIP] Algorithm to Construct DAG: Process statements in order. Maintain a symbol table mapping variable names to current DAG nodes. For x = y op z: look up nodes for y, z; find/create node N for op; update symbol table entry for x to point to N.

Code Optimization

Principle Sources: (1) Useless code (unreachable, dead), (2) Repeated computation (CSE), (3) Inefficient constructs (e.g., x*2 -> x+x).

Local Optimizations (on a Basic Block):

• Common Subexpression Elimination (CSE): Eliminate recomputation of same expression.

• Copy Propagation: Replace x = y with uses of x by y.

• Dead Code Elimination: Remove assignments to variables whose values are never used.

• Constant Folding & Propagation: Evaluate constant expressions at compile time; propagate constants.

• Peephole Optimization: Examine a small sliding window of instructions (peephole) for:

  • Redundant loads/stores.

  • Unreachable code.

  • Algebraic simplifications (x*1 -> x).

  • Sequence changes (MOV R1, R2; ADD R1, R3 -> ADD R2, R3).

Global Optimizations (across Basic Blocks):

• Loop Optimizations (HIGH FREQUENCY):

  • Moving Loop-Invariant Code: Identify computations that yield same result in every iteration and move them outside the loop.

    • Condition: All operands are loop-invariant (defined outside loop or constant within loop).

  • Induction Variables: Variables where value changes by a constant amount each iteration (e.g., i = i + 1). Can be eliminated or replaced by a single variable and a strength-reduced expression.

• Reduction in Strength: Replace expensive operation (*) with cheaper one (+), e.g., x*8 -> x<<3.

Three Areas of Code Optimization:

1. Machine Independent: Applied to IR (TAC, DAG). E.g., CSE, constant propagation, dead code elimination.

2. Machine Dependent: Require target architecture knowledge. E.g., register allocation, instruction selection, peephole on final code.

3. Language Dependent: Exploit specific language semantics (e.g., array bounds check elimination in Java if index proven in range).

VI. RUNTIME ENVIRONMENT & CODE GENERATION

Storage Allocation Strategies

Activation Record (AR) Model / Format

Layout for a procedure call (typical):

[!TIP] Exam Focus: Be able to draw the AR layout and explain each field. Understand the difference between dynamic link (runtime call chain) and static link (lexical nesting chain).

Symbol Table

• Purpose: Store attribute information for every identifier (name, type, scope, address/location, size).

• Data Structures:

  • Linear List (Unordered/Ordered): Simple, slow search.

  • Hash Table: Most common. Fast average access, handles large tables.

  • Binary Search Tree: Ordered, moderate speed.

  • Self-Organizing List: Move recently used items to front (good if locality).

Register Allocation & Assignment

• Goal: Assign as many live variables as possible to CPU registers (fast) instead of memory (slow).

• Register Allocation Graph (Interference Graph):

  • Nodes = temporary variables (or variables with fixed live ranges).

  • Edge between Ti and Tj if their live ranges overlap (they are simultaneously live). They cannot share a register.

• Graph Coloring: Problem reduces to coloring the graph with k colors (registers) such that adjacent nodes have different colors.

  • Simplification: Remove node with degree < k, push to stack.

  • Spill: If all nodes have degree >= k, spill one (assign to memory) to reduce graph.

  • Select/Assign: Pop nodes from stack, assign colors/registers.

Backpatching

• Concept: Used to generate jump instructions where the target address is unknown during initial code generation (e.g., in if, while, goto).

• Mechanism: Instead of emitting the actual jump, emit a placeholder and record the address of the jump instruction in a list.

• When target becomes known (e.g., after generating code for then part), backpatch the list by filling in the actual address at all recorded locations.

• Example for if (B) S1:

  1. Generate code for B, leaving Boolean result on top of stack.

  2. Emit if false goto -- (placeholder). Record address L1 of this instruction in a list B.false.

  3. Generate code for S1.

  4. Backpatch(B.false, nextInstrAddr).

[!TIP] Backpatching Lists: Each Boolean expression node has two lists: true (jumps if condition true) and false (jumps if false). For B1 && B2: B1.true is backpatched to start of B2; B2.false becomes B1 && B2.false; B1.false becomes B1 && B2.false. For B1 || B2: B1.false is backpatched to start of B2.

VII. ERROR HANDLING

Types of Compiler Errors

• Lexical Phase Errors: Invalid characters, malformed numbers/strings.

• Syntactic Phase Errors: Missing ;, mismatched {}, unexpected token (detected by parser).

• Semantic Errors: Type mismatch, undeclared variable, incompatible operand types, arity mismatch in function call.

Function of Error Handling Phase

• Detect errors accurately.

• Report them clearly to the user (message, location).

• Recover from the error to continue compilation (find more errors, not just stop at first).

• Minimize impact on correct parts of the program.

Error Recovery Strategies

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

• Phrase-Level Recovery: Perform local correction (insert/delete/replace token) to allow parsing to continue. Requires knowledge of common errors.

• Error Productions: Add special productions to the grammar for common errors (e.g., missing semicolon). Parser reduces by this production and reports error.

• Global Correction: Use algorithms (e.g., Levenshtein distance) to find minimal changes to make program valid. Expensive, rarely used in practice.

[!TIP] Common Error Examples:

• Lexical: 123.45.67 (malformed float).

• Syntactic: if (x > 0) y = 1 (missing braces for single statement? depends on language).

• Semantic: int x = "hello"; (type mismatch).