Group B — Medium / Descriptive Questions (5 Marks Each)

Phases of a Compiler

A compiler translates source code from a high-level language into machine code through several distinct phases. It is conceptually divided into the Analysis Phase (Front-end) and Synthesis Phase (Back-end).

• Lexical Analysis: Scans the source code character by character to group them into meaningful sequences called tokens.
• Syntax Analysis: Groups tokens into a hierarchical structure called a Parse Tree to check grammatical correctness according to Context-Free Grammar rules.
• Semantic Analysis: Checks the parse tree for semantic consistency with language rules (e.g., type checking, variable declaration checks).
• Intermediate Code Generation (ICG): Generates an explicit, low-level, machine-independent representation (e.g., Three-Address Code).
• Code Optimization: Improves the intermediate code to make it faster and consume less memory (e.g., dead code elimination, constant folding).
• Target Code Generation: Translates the optimized intermediate code into relocatable machine code or assembly language for the target architecture, handling register allocation.

Thompson's Construction: (a|b)*a

Thompson's Construction is an algorithm to build a Non-Deterministic Finite Automaton (NFA) from a Regular Expression. It works recursively by building basic NFAs for single characters and combining them using rules for union |, concatenation ., and Kleene star *.

Step 1: Construct NFA for (a | b)

Step 2: Construct NFA for (a | b)* (Kleene Star)

Add a new start state and a new final state. Add ε-transitions to loop back and to skip the machine.

Step 3: Construct Final NFA for (a | b)*a (Concatenation)

Concatenate the previous NFA with an NFA for 'a'. The old final state (7) merges with the start state of 'a'.

Subset Construction Method

The Subset Construction (or Powerset Construction) algorithm converts an NFA into an equivalent Deterministic Finite Automaton (DFA) by simulating all possible active states of the NFA simultaneously.

Concept: A single state in the new DFA represents a set of states in the NFA. We use the \(\epsilon\)-closure operation to find all states reachable without consuming input.

1. Initialize: Create the start state of the DFA by finding the \(\epsilon\)-closure of the NFA's start state. Let this be DFA state \(A\).
2. Iterate: For every existing DFA state (subset of NFA states) and for every possible input symbol (e.g., 'a' or 'b'):
   • Find the set of NFA states reachable by transitioning on the symbol from the current subset.
   • Take the \(\epsilon\)-closure of that resulting set.
   • If this new subset hasn't been seen before, it becomes a new DFA state.
   • Add a transition from the current DFA state to the new DFA state.
3. Final States: Any DFA state (subset) that contains at least one final state of the original NFA is marked as a final state in the DFA.

For the regex (a|b)*abb, the resulting DFA typically has 5 states representing the progress of matching the suffix abb.

Lexeme, Token, and Pattern

The Lexical Analyzer reads raw characters and groups them. Understanding the difference between these three terms is fundamental to lexical analysis.

Code Example: while (count <= 100)

• Lexeme while matches the pattern for the keyword token.
• Lexeme count matches the pattern for the id (identifier) token.
• Lexeme <= matches the pattern for the relop (relational operator) token.

Role of the Symbol Table

A Symbol Table is a critical data structure created and maintained by compilers to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc.

It is accessed and updated across all phases of the compiler:

1. Lexical Analysis: When an identifier is encountered, the lexer checks if it's already in the table. If not, it creates a new entry and passes a pointer to this entry to the parser.
2. Syntax Analysis: The parser adds structural information to the symbol table, such as the scope of variables and function parameters.
3. Semantic Analysis: This phase relies heavily on the symbol table for Type Checking. It verifies that variables are declared before use, checks that types in expressions match, and ensures function calls have the correct number/type of arguments by looking up their signatures in the table.
4. Intermediate Code Generation: Uses the symbol table to allocate temporary variables and determine the memory size required for different data types.
5. Target Code Generation & Optimization: Uses the symbol table to determine the exact memory addresses or register assignments for variables during runtime.

Lexical Error Recovery Strategies

A lexical error occurs when the Lexical Analyzer reads a sequence of characters that does not match the pattern of any valid token in the language (e.g., encountering an illegal character like @ in standard C).

Instead of halting compilation immediately, the lexer attempts error recovery to find more errors in the same pass.

1. Panic Mode Recovery: The simplest and most common strategy. The lexer deletes successive characters from the remaining input until a well-formed token can be identified.
   Example: Input 23@45. The lexer reads 23 (number), encounters @ (error), deletes @, and resumes to find 45 (number).
2. Character Deletion: Delete the extraneous character.
3. Character Insertion: Insert a missing character that might complete a token (very difficult to implement reliably).
4. Character Substitution: Replace an incorrect character with a correct one.
5. Transposition: Swap two adjacent characters (e.g., reading fi instead of if, though usually handled by the syntax analyzer).

Left Recursion Elimination

A grammar is Left Recursive if it contains a non-terminal \(A\) that derives a string starting with itself: \(A \rightarrow A\alpha\). Top-Down parsers (like LL(1) and Recursive Descent) will enter an infinite loop trying to parse such grammars.

Algorithm (Direct Left Recursion)

If a grammar has productions of the form:
\(A \rightarrow A\alpha_1 \mid A\alpha_2 \dots \mid \beta_1 \mid \beta_2 \dots\)
(Where \(\alpha\) are strings that do not derive \(\epsilon\), and \(\beta\) are strings that do not start with \(A\)).

We replace them with two new sets of productions using a new non-terminal \(A'\):

• \(A \rightarrow \beta_1 A' \mid \beta_2 A' \dots\)
• \(A' \rightarrow \alpha_1 A' \mid \alpha_2 A' \dots \mid \epsilon\)

Example

Original Grammar:
\(E \rightarrow E + T \mid T\)

Here, \(\alpha = + T\) and \(\beta = T\). Applying the algorithm:

Eliminated Grammar:
\(E \rightarrow T E'\)
\(E' \rightarrow + T E' \mid \epsilon\)

This transforms the left-recursive grammar into a right-recursive one, which is perfectly safe for Top-Down parsers.

Left Factoring

Left Factoring is a grammar transformation technique used to remove ambiguity for predictive top-down parsers. It is required when two or more productions of a non-terminal share a common prefix, making it impossible for the parser to decide which production to choose by looking at the next input token (Lookahead).

Algorithm

If we have productions of the form where \(\alpha\) is a non-empty common prefix:
\(A \rightarrow \alpha\beta_1 \mid \alpha\beta_2 \dots \mid \gamma\)

We factor out the common prefix \(\alpha\) and create a new non-terminal \(A'\) for the divergent suffixes:

• \(A \rightarrow \alpha A' \mid \gamma\)
• \(A' \rightarrow \beta_1 \mid \beta_2 \dots\)

Example

Original Grammar (Dangling-Else Problem):
\(S \rightarrow \textbf{if } E \textbf{ then } S \mid \textbf{if } E \textbf{ then } S \textbf{ else } S \mid a\)

Here, the common prefix \(\alpha\) is if E then S. \(\beta_1\) is \(\epsilon\), \(\beta_2\) is else S, and \(\gamma\) is a.

Factored Grammar:
\(S \rightarrow \textbf{if } E \textbf{ then } S \ S' \mid a\)
\(S' \rightarrow \textbf{else } S \mid \epsilon\)

Conditions for LL(1) Grammar

A Context-Free Grammar (CFG) is LL(1) (Left-to-right scan, Leftmost derivation, 1 token lookahead) if and only if its parsing table contains no multiply-defined entries. For a grammar to be LL(1), it must satisfy three strict conditions for any pair of productions \(A \rightarrow \alpha \mid \beta\):

1. Disjoint FIRST Sets: It must be impossible to derive strings starting with the same terminal from both \(\alpha\) and \(\beta\).
   Mathematically: \(\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset\).
   (This means the grammar must be Left-Factored).
2. No Left Recursion: The grammar must not contain direct or indirect left recursion, as this causes infinite loops in LL parsing.
3. Nullable Prefix Conflict (FIRST-FOLLOW Conflict): If one of the productions (say \(\beta\)) can derive the empty string (\(\epsilon\)), then \(\alpha\) cannot derive any string starting with a terminal that is in the FOLLOW set of \(A\).
   Mathematically: If \(\epsilon \in \text{FIRST}(\beta)\), then \(\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset\).

If a grammar passes these conditions, a predictive parser can always determine exactly which production to apply by looking at just the next input token.

LL(1) Parsing Table Construction

Grammar (after left-recursion elimination):
1. \(E \rightarrow T E'\)
2. \(E' \rightarrow + T E'\)
3. \(E' \rightarrow \epsilon\)
4. \(T \rightarrow F T'\)
5. \(T' \rightarrow * F T'\)
6. \(T' \rightarrow \epsilon\)
7. \(F \rightarrow ( E )\)
8. \(F \rightarrow id\)

FIRST and FOLLOW Sets:

LL(1) Parsing Table:

Because every cell contains at most one production, the grammar is definitively LL(1).

Top-Down vs Bottom-Up Parsing

Shift-Reduce Parsing Mechanism

Shift-Reduce parsing is a bottom-up parsing strategy that uses a Stack to hold grammar symbols and an Input Buffer holding the remaining string to be parsed.

The parser performs four primary actions:

1. Shift: The parser shifts the next input token from the input buffer onto the top of the stack.
2. Reduce: If the symbols on the top of the stack match the right-hand side (body) of a production rule (this match is called a handle), the parser pops them off the stack and pushes the left-hand side (head) non-terminal onto the stack.
3. Accept: If the stack contains only the Start Symbol and the input buffer is empty (contains only the end marker $), parsing is successful.
4. Error: If neither shift nor reduce is valid, a syntax error is detected.

Conflicts: A Shift/Reduce conflict happens if the parser cannot decide whether to shift the next token or reduce the current handle. A Reduce/Reduce conflict happens if multiple production rules match the handle.

Comparison of LR Parsers

LR(0) Item Set Construction

An LR(0) item is a production rule with a dot (•) indicating how much of the right-hand side has been recognized by the parser.

Example for \(A \rightarrow XYZ\): Items are \(A \rightarrow \bullet XYZ\), \(A \rightarrow X \bullet YZ\), \(A \rightarrow XY \bullet Z\), and \(A \rightarrow XYZ \bullet\).

Closure Operation

If \(I\) is a set of items for a grammar, then \(\text{CLOSURE}(I)\) is constructed as follows:

1. Initially, every item in \(I\) is added to \(\text{CLOSURE}(I)\).
2. If an item \(A \rightarrow \alpha \bullet B \beta\) is in \(\text{CLOSURE}(I)\) (where the dot is just before a non-terminal \(B\)), then for every production \(B \rightarrow \gamma\) in the grammar, add the item \(B \rightarrow \bullet \gamma\) to \(\text{CLOSURE}(I)\).
3. Repeat step 2 until no more new items can be added.

This operation expands the state to include all possible productions that could be derived next.

Yacc File Structure

A Yacc (Yet Another Compiler Compiler) specification file is divided into three distinct sections separated by %%.

• Declarations: Contains C headers, token declarations (%token), and operator precedence/associativity (%left, %right).
• Rules: Context-free grammar rules in BNF format. Each rule can have semantic actions written in C inside curly braces {}. $$ refers to the LHS value, and $1, $2 refer to RHS symbols.
• User Code: Auxiliary C functions like main() and error handlers required to run the parser.

Lex File Structure

A Lex (or Flex) file specifies lexical analyzer rules. Like Yacc, it is divided into three sections separated by %%.

• Definitions: C code inside %{ ... %}, followed by macro definitions for regular expressions to make rules cleaner.
• Rules: A list of pattern { action } pairs. When the lexer matches the regex pattern, it executes the C code in the action block (usually returning a token).
• User Functions: Additional C routines (like yywrap).

SDD vs SDT

Synthesized vs Inherited Attributes

Attributes are values associated with grammar symbols (nodes in a parse tree) used to carry semantic information.

• Synthesized Attributes:
  • The value of a synthesized attribute at a node is computed solely from the attributes of its children.
  • Information flows bottom-up in the parse tree.
  • Evaluated easily using a bottom-up parser (LR parsers).
  • Example: In E → E1 + T, E.val = E1.val + T.val. The value of E synthesizes up from its children.
• Inherited Attributes:
  • The value of an inherited attribute at a node is computed from the attributes of its parent and/or its siblings.
  • Information flows top-down or laterally in the parse tree.
  • Useful for passing context (like variable types from a declaration down to the variable identifiers).
  • Example: In Decl → Type IdList, the type (e.g., int) is inherited by the nodes inside IdList.

S-Attributed vs L-Attributed SDDs

• S-Attributed SDD:
  • A Syntax Directed Definition that uses only Synthesized Attributes.
  • Attribute values can be evaluated by traversing the parse tree bottom-up.
  • Perfectly suited for implementation during Bottom-Up (LR) parsing. The semantic actions can simply run during the Reduce operation.
• L-Attributed SDD:
  • Allows both Synthesized and Inherited attributes, but with a strict restriction on Inherited attributes:
  • An inherited attribute at a node can only depend on attributes from its parent or its left siblings (never right siblings).
  • "L" stands for Left-to-Right. The attributes can be evaluated during a standard Depth-First, Left-to-Right traversal of the parse tree.
  • Easily implemented alongside Top-Down (LL) parsing.

Intermediate Code: Syntax Trees vs Postfix

Intermediate Code Generators convert the parse tree into simpler representations for optimization.

• Syntax Trees (Abstract Syntax Trees - AST):
  • A condensed version of a parse tree. Internal nodes represent operators (e.g., +, *), and leaf nodes represent operands (identifiers, constants).
  • It explicitly shows the hierarchical structure and operator precedence of expressions.
  • Example for a = b + c * d: Root is =. Left child is a, right child is +. The + has children b and *, where * has children c and d.
• Postfix Notation (Reverse Polish Notation):
  • A linearized string representation where operators immediately follow their operands.
  • Parentheses are not needed because evaluation order is strictly left-to-right using a stack.
  • Example for (a + b) * c: Postfix is a b + c *.
  • It is highly efficient for generating stack-machine code (like Java Bytecode).

Three-Address Code (3AC) Representations

Three-Address Code is a linearized representation of a syntax tree where each instruction has at most three addresses (two operands and one result). It is stored in data structures during compilation.

• Quadruples: A structure with four fields: (Operator, Operand 1, Operand 2, Result).
  • Example for a = b + c: (+, b, c, a)
  • Pros: Easy to move instructions around during optimization because the result name is explicitly stored.
  • Cons: Wastes memory storing temporary variable names.
• Triples: A structure with three fields: (Operator, Operand 1, Operand 2). The result of the operation is implicitly referred to by the index (position) of the triple itself.
  • Example: (0) (+, b, c). If another instruction needs this result, it references (0).
  • Pros: Saves memory by avoiding temporary variable storage.
  • Cons: Very difficult to optimize. Moving a triple changes its index, which breaks all other triples referencing it.
• Indirect Triples: Uses a separate array of pointers to index the standard Triples array.
  • Pros: Combines the memory efficiency of triples with the optimizability of quadruples. To move an instruction, the optimizer simply reorders the pointer array without touching the actual triples.

SDT for Boolean Expressions

Boolean expressions (like A < B or C > D) are primarily used to alter the flow of control (e.g., in if-else or while loops). Their SDT relies on generating conditional jump instructions.

Instead of computing a literal true or false value, we associate two inherited attributes with every boolean expression B:

• B.true: The instruction label to jump to if B evaluates to true.
• B.false: The instruction label to jump to if B evaluates to false.

Example SDD Rules for B → B1 or B2:

• B1.true = B.true (If B1 is true, the whole OR expression is true, jump to B's true label).
• B1.false = newlabel() (If B1 is false, we must evaluate B2. Jump to a new label where B2's code starts).
• B2.true = B.true
• B2.false = B.false (If B2 is also false, the whole expression is false).

Backpatching

Backpatching is a technique used during one-pass Intermediate Code Generation (ICG) for boolean expressions and control flow statements.

The Problem

When the compiler generates a conditional jump instruction (e.g., "If true, goto L1"), it often doesn't know the exact target address of L1 yet because the code for that section hasn't been parsed/generated.

The Solution

Instead of failing or requiring a second pass over the code, the compiler leaves the target address blank (or creates a placeholder). It then puts the index of this incomplete instruction into a list.

• makelist(i): Creates a new list containing only the instruction index i.
• merge(p1, p2): Combines two lists of instruction indices that all need to jump to the exact same target.
• backpatch(p, i): Once the target address i finally becomes known, this function visits every instruction listed in p and fills in the blank target address with i.

Activation Record (Stack Frame)

When a function (subroutine) is called, the OS/Compiler pushes a block of memory called an Activation Record onto the Run-Time Stack to manage the function's execution state.

Structure (from top to bottom of stack):

1. Actual Parameters: The arguments passed to the function by the caller.
2. Return Values: Space reserved for the function to write its result back to the caller.
3. Control Link (Dynamic Link): A pointer to the Activation Record of the caller function. Used to pop the stack when returning.
4. Access Link (Static Link): A pointer used to access non-local variables defined in lexically enclosing scopes (used in languages with nested procedures).
5. Saved Machine Status: The caller's CPU registers, specifically the Return Address (Program Counter), so execution can resume properly.
6. Local Data: Memory for local variables declared inside the function.
7. Temporaries: Scratchpad memory used by the compiler during complex expression evaluation.

Heap Memory Management

The Heap is a region of memory used for dynamic allocation of data whose size or lifetime cannot be determined at compile-time (e.g., objects created with new or malloc()).

Dynamic Allocation Strategies

The memory manager maintains a linked list of free blocks in the heap. When a program requests memory, it searches this list:

• First-Fit: Allocates the first free block that is large enough. Fast, but causes memory fragmentation.
• Best-Fit: Searches the entire list and allocates the smallest free block that is large enough. Minimizes wasted space inside the block but creates tiny, unusable fragments (external fragmentation) and is slower.
• Next-Fit: Like First-Fit, but starts searching from where the last allocation occurred, rather than the beginning of the list.

When objects are explicitly freed (e.g., free() or delete), the manager returns the block to the free list and attempts to coalesce adjacent free blocks into larger ones to prevent fragmentation.

Garbage Collection Algorithms

Garbage Collection automatically reclaims heap memory that is no longer reachable by the program.

Identifying Leaders and Basic Blocks

A Basic Block is a straight-line sequence of code with exactly one entry point and one exit point. Identifying them is the first step in constructing a Control Flow Graph (CFG) for optimization.

Algorithm to Identify Leaders

A Leader is the first instruction of a basic block. The rules to find leaders in a sequence of Three-Address Code are:

1. The very first instruction in the code sequence is a leader.
2. Any instruction that is the target of a conditional or unconditional jump (goto) is a leader.
3. Any instruction that immediately follows a conditional or unconditional jump is a leader.

Constructing Basic Blocks

Once all leaders are identified, a Basic Block consists of the leader instruction and all subsequent instructions up to, but not including, the next leader.

Directed Acyclic Graph (DAG) for Basic Blocks

A DAG is a data structure used to perform Local Code Optimization within a single basic block. It visually represents the data dependencies and data flow of expressions.

Construction Rules

1. Leaves: Represent initial values of variables or constants entering the block. (e.g., initial value of a).
2. Internal Nodes: Represent operators (+, *, -). The children of the node represent the operands.
3. Node Labels: An internal node is labeled with the operator. Additionally, the node is "tagged" with the names of all variables that currently hold the value computed by that node.

Optimizations achieved via DAG

• Common Subexpression Elimination: If an expression like a + b is computed twice, the DAG builder won't create a new node. It will just add a tag to the existing + node, eliminating the redundant calculation.
• Dead Code Elimination: If a root node (a computed value) is never used subsequently, it can be deleted.

Local Code Optimization Techniques

Local optimizations are performed within a single Basic Block (no control flow analysis required).

• Constant Folding: The compiler evaluates constant expressions at compile-time rather than runtime.
  Before: x = 2 * 3.14
  After: x = 6.28
• Constant Propagation: If a variable is assigned a constant value, subsequent reads of that variable are replaced by the constant itself.
  Before: pi = 3.14; area = pi * r * r;
  After: area = 3.14 * r * r;
• Copy Propagation: If a variable is assigned the value of another variable, use the original variable in subsequent uses.
  Before: x = y; z = x + 1;
  After: z = y + 1;
• Dead Code Elimination: Removing instructions whose results are never used or instructions that are completely unreachable.

Loop Optimization Techniques

Since programs spend the vast majority of their time executing loops, optimizing loop structures provides the highest performance gains.

• Loop Invariant Code Motion (Hoisting): Moving an expression that yields the same result on every iteration outside the loop so it is only computed once.
  Before: for(i=0; i<10; i++) { x = y + z; a[i] = x; }
  After: x = y + z; for(i=0; i<10; i++) { a[i] = x; }
• Strength Reduction: Replacing an expensive mathematical operation with a cheaper equivalent operation. Frequently used for loop induction variables.
  Example: Replacing multiplication (i * 4) inside a loop with successive addition (t = t + 4).
• Loop Unrolling: Replicating the body of the loop multiple times and reducing the loop counter checks. This reduces the branch penalty overhead and increases instruction-level parallelism for modern pipelined CPUs.

Peephole Optimization Techniques

Peephole optimization is a late-stage, machine-dependent optimization. The compiler examines a small, sliding window (the "peephole") of target instructions and replaces them with a shorter or faster equivalent sequence.

1. Redundant Instruction Elimination

Removing instructions that do nothing or load values that are already in the correct register.

Before: MOV R1, a
MOV a, R1
After: MOV R1, a

2. Flow of Control Optimization (Jump to Jump)

Eliminating unnecessary intermediate jumps.

Before: JMP L1
...
L1: JMP L2
After: JMP L2
...
L1: JMP L2

3. Algebraic Simplification

Removing mathematically useless operations.

Before: ADD R1, 0 or MUL R2, 1
After: (Deleted completely)

4. Use of Machine Idioms

Replacing standard instructions with specialized, faster hardware instructions.

Before: ADD R1, 1
After: INC R1 (Increment instruction is faster and uses less space).

Issues in the Code Generation Phase

The target code generator must output highly efficient machine code while preserving the exact semantics of the program. The primary challenges are:

• Instruction Selection: Choosing the best machine instruction to execute an intermediate code operation. For example, replacing a = b + 1 with a fast INC b instead of a generic ADD b, 1. This depends heavily on the target CPU architecture (CISC vs RISC).
• Register Allocation and Assignment: Registers are the fastest memory in the CPU, but they are limited in number. The compiler must decide which variables should be kept in registers (Allocation) and specifically which register to use for which variable (Assignment) to minimize slow memory access (loads/stores).
• Evaluation Order: Changing the order in which instructions are executed can drastically reduce the number of registers needed to hold intermediate results, but the compiler must ensure this doesn't violate data dependencies.
• Target Machine Characteristics: The compiler must handle architectural quirks, such as addressing modes, memory alignment restrictions, and pipeline delays.

Chaitin's Graph Coloring for Register Allocation

Register allocation can be modeled as a mathematical graph coloring problem, proposed by Gregory Chaitin.

1. Liveness Analysis: Determine the "live range" of every variable (the time from when it is defined to when it is last used).
2. Build Interference Graph: Create an undirected graph where:
   • Each node represents a variable.
   • An edge connects two nodes if their live ranges overlap (they "interfere" because they are alive at the same time and cannot share a register).
3. Graph Coloring: Attempt to color the graph using \(K\) colors, where \(K\) is the number of available CPU registers, such that no two adjacent nodes share the same color.
4. Spilling: If the graph cannot be colored with \(K\) colors, the compiler must select a variable to "spill" to main memory (usually the one least frequently accessed). This node is removed from the graph, and coloring is retried.

Syntax Error Recovery Methods

When a parser encounters a syntax error (a token that violates the CFG rules), it attempts recovery to continue parsing and find further errors.

Static Scope vs Dynamic Scope

Scope rules determine how free variables in a function are resolved (bound to their declarations).

• Static Scope (Lexical Scope):
  • The scope is determined by the physical layout of the source code at compile-time.
  • If a variable is not found in the local scope, the compiler looks in the lexically enclosing block (the block of code that literally surrounds it).
  • Used by almost all modern languages (C, Java, Python).
  • Advantage: Easy for programmers to read and reason about.
• Dynamic Scope:
  • The scope is determined by the sequence of function calls at run-time.
  • If a variable is not found locally, the runtime looks in the caller's scope, then the caller's caller, tracing back up the call stack.
  • Used by early LISP, Bash, Perl (with local).
  • Advantage: Useful for temporarily overriding global configurations.
  • Disadvantage: Highly unpredictable, as a function's behavior changes depending on who called it.

Hash Table Symbol Table Organization

A Hash Table is the most common data structure for symbol tables because it provides extremely fast \(O(1)\) average-case time for insertions and lookups.

Scope Chaining Implementation

In languages with nested scopes (like C++ or Java blocks), the same identifier (e.g., x) can be declared multiple times in different scopes. The symbol table must resolve this correctly.

• Individual Hash Tables: Create a new hash table for every new scope. Link each table to its parent scope's table. To look up a variable, search the local table; if not found, traverse the link to the parent table.
• Single Hash Table with Chaining: Use one giant hash table for all scopes. Each bucket contains a linked list of entries. When a new scope defines x, it pushes the new declaration to the front of the linked list for bucket hash("x"). When the scope exits, the compiler deletes the front element, exposing the older declaration from the outer scope.

Type Checking and Conversions

Type Checking (performed during semantic analysis) ensures that operands in expressions and function calls are of compatible types according to the language rules.

• Implicit Conversion (Coercion): The compiler automatically converts a type to prevent an error, usually widening the type to prevent data loss.
  Example: In float x = 5;, the integer 5 is implicitly coerced into a float 5.0 before assignment.
• Explicit Conversion (Casting): The programmer forces the compiler to treat a variable as a different type, often involving a narrowing conversion that might lose data.
  Example: int y = (int) 3.14; (Forces conversion, truncating the fractional part to 3).

In the AST, type conversions are explicitly represented as unary operator nodes (e.g., int_to_float) generated by Semantic Actions in the SDT.

Static Single Assignment (SSA)

Static Single Assignment (SSA) form is an intermediate representation where every variable is assigned a value exactly once. If a variable is updated multiple times in the original code, SSA creates new versions (e.g., x1, x2, x3).

Original Code:
x = 1; x = x + 2;

SSA Code:
x_1 = 1; x_2 = x_1 + 2;

Advantages of SSA

1. Simplifies Data Flow Analysis: Because each variable has exactly one definition point, the "Reaching Definitions" problem becomes trivial.
2. Improves Optimization Algorithms: SSA makes optimizations like Constant Propagation, Dead Code Elimination, and Value Numbering significantly faster and more effective because use-def chains are direct and unambiguous.
3. Phi (\(\Phi\)) Functions: When control flow merges (e.g., after an if-else), SSA uses \(\Phi\) functions to select the correct variable version based on which path was taken. (e.g., x_3 = Φ(x_1, x_2)).

Data Flow Analysis Concepts

Data Flow Analysis collects information about the flow of data along execution paths in a CFG to enable global optimizations.

• Reaching Definitions: A definition of a variable \(d\) (e.g., x = 5) reaches a point \(p\) in the program if there exists a path from \(d\) to \(p\) such that \(x\) is not redefined (killed) anywhere along that path.
  Application: Used for Constant Propagation and loop optimizations.
• Live Variable Analysis: A variable \(x\) is live at point \(p\) if its current value will be read (used) along some path starting at \(p\) before it is overwritten. If it will never be read again, it is dead.
  Application: Crucial for Register Allocation. If a variable is dead, its register can be immediately reassigned to another variable. Used for Dead Code Elimination.

Retargetable Compilers (GCC / LLVM)

A Retargetable Compiler is designed to support multiple source programming languages and multiple target machine architectures without rewriting the entire compiler.

Architecture

It achieves this via a strict modular architecture relying on a universal Intermediate Representation (IR):

1. Front-End (Language-Specific): There is a separate front-end for C, C++, Rust, etc. They all parse their specific languages and translate them into the exact same universal IR.
2. Middle-End (Optimizer): The optimizer only reads and transforms the universal IR. It is completely independent of both the source language and the target hardware.
3. Back-End (Machine-Specific): There is a separate back-end for x86, ARM, MIPS, etc. Each back-end takes the universal IR and translates it into specific machine code.

Advantage: To support a new CPU architecture, developers only need to write a new Back-End (connecting IR to the new CPU), automatically granting support for all existing front-end languages!