Ans: A lexeme is the actual sequence of characters in the source program that matches the pattern for a token; it is the concrete text the scanner consumed. In int count; the lexemes are int, count and ; — here count is the lexeme matching the identifier pattern, for which the lexical analyser emits the token \( \langle id,\ ptr \rangle \).

Ans: A token is the pair \( \langle \text{token-name},\ \text{attribute-value} \rangle \) produced by the lexical analyser, where the token-name is an abstract symbol that the parser treats as a terminal and the (optional) attribute points to further information such as a symbol-table entry. For the lexeme count the token is \( \langle id,\ ptr \rangle \); tokens like ; or while need no attribute.

Ans: A pattern is the rule — normally a regular expression — that describes the form all lexemes of a given token may take. For the token id the pattern is \( letter\,(letter \mid digit)^{*} \); count is one lexeme matching that pattern, and \( \langle id,\ ptr \rangle \) is the token produced. So the pattern is the description, the lexeme is the matched text, and the token is the parser's symbol.

Ans: A cross compiler is a compiler that runs on one machine (the host) but generates target code for a different machine, i.e. host \( \ne \) target. It is essential for building software for embedded systems or a new architecture that cannot yet host a compiler — e.g. gcc executing on an x86 workstation and emitting ARM object code.

Ans: Bootstrapping is the technique of writing a compiler for a language in that same language: a small compiler for a subset \( S_0 \) is first written in an existing language (or machine code), and that compiler is then used to compile a fuller compiler written in \( S_0 \), the process repeating until the full language is supported. It is described using T-diagrams and is how compilers for C, Pascal and Go were built.

Ans: A symbol table is the compiler's data structure that records every identifier of the source program together with its attributes — type, scope/nesting level, storage class, size, and memory offset. It is created and filled during lexical and syntax analysis and consulted by semantic analysis, code generation and error reporting; it is usually a hash table supporting fast insert and lookup.

Ans: A compiler is split into an analysis part (front end) — lexical, syntax and semantic analysis plus intermediate-code generation, which breaks the source into pieces, builds the intermediate representation and symbol table and reports errors — and a synthesis part (back end) — code optimisation and target-code generation, which builds the target program from that intermediate representation. The split is what allows one front end to serve many machines.

Ans: A grammar is left recursive if some non-terminal \( A \) admits a derivation \( A \Rightarrow^{+} A\alpha \); the immediate case is \( A \to A\alpha \mid \beta \). It makes a top-down (recursive-descent / LL) parser recurse for ever without consuming input, so it must be eliminated by rewriting as \( A \to \beta A' \), \( A' \to \alpha A' \mid \epsilon \). Bottom-up LR parsers, in contrast, handle left recursion happily.

Ans: Left factoring is the grammar transformation that postpones a parsing decision when two or more alternatives share a common prefix: \( A \to \alpha\beta_1 \mid \alpha\beta_2 \) is rewritten as \( A \to \alpha A' \), \( A' \to \beta_1 \mid \beta_2 \). It removes the non-determinism of choice so that one lookahead token suffices for LL(1) — whereas removing left recursion cures infinite recursion; the two transformations fix different defects and both may be needed.

Ans: A grammar is ambiguous if it produces more than one parse tree — equivalently more than one leftmost (or rightmost) derivation — for some sentence of its language. For \( E \to E+E \mid E*E \mid id \), the string id+id*id has two distinct parse trees. An ambiguous grammar is neither LL(1) nor LR(k) for any \( k \), and is disambiguated by precedence/associativity rules or by rewriting.

Ans: A parse tree (concrete syntax tree) is a tree depicting a derivation: its root is the start symbol, each interior node is a non-terminal whose children are the symbols of the right side of the production applied, and the leaves read left to right give the input string (the yield). It records every grammar symbol, including punctuation and single-child chains, unlike a syntax tree.

Ans: An abstract syntax tree is a condensed parse tree in which operators (or language constructs) label the interior nodes and their operands are the children, while symbols needed only for parsing — parentheses, commas, chains of single productions — are dropped. For a = b + c the AST is = with children a and the subtree +(b, c); a DAG goes one step further by sharing identical subtrees.

Ans: A shift-reduce conflict occurs when, in some LR state with a given lookahead, the parsing table allows both shifting the next input symbol and reducing by a completed production, so the action is not unique. The standard example is the dangling-else grammar \( S \to \textbf{if } E \textbf{ then } S \mid \textbf{if } E \textbf{ then } S \textbf{ else } S \) on lookahead else; Yacc resolves such conflicts in favour of shift.

Ans: A reduce-reduce conflict occurs when two or more different productions are simultaneously complete in an LR state and both are legal reductions on the same lookahead, so the parser cannot tell which production to reduce by. Unlike a shift-reduce conflict it almost always signals a genuinely badly designed or ambiguous grammar; LALR(1) can introduce reduce-reduce conflicts by merging CLR(1) states with the same core.

Ans: LL(1) parsing is table-driven predictive top-down parsing: the first L means the input is scanned Left to right, the second L means a Leftmost derivation is produced, and the 1 means one lookahead token is used, with no backtracking. A grammar is LL(1) iff for every pair \( A \to \alpha \mid \beta \), \( FIRST(\alpha) \cap FIRST(\beta) = \emptyset \) and, if \( \beta \Rightarrow^{*} \epsilon \), \( FIRST(\alpha) \cap FOLLOW(A) = \emptyset \) — so it must be free of left recursion and left factored. Because it must commit to a production before seeing the right side, every LL(1) grammar is LR(1) but not conversely.

Ans: For a grammar symbol string \( \alpha \), \( FIRST(\alpha) \) is the set of terminals that can begin some string derived from \( \alpha \), and it also contains \( \epsilon \) if \( \alpha \Rightarrow^{*} \epsilon \). A predictive parser uses it to choose a production: for \( A \to \alpha \), the entry \( M[A,\ a] \) is filled for every \( a \in FIRST(\alpha) \) — so \( FIRST \) looks at what a production can start with, unlike \( FOLLOW \).

Ans: For a non-terminal \( A \), \( FOLLOW(A) \) is the set of terminals that can appear immediately to the right of \( A \) in some sentential form, i.e. all \( a \) with \( S \Rightarrow^{*} \alpha A a \beta \); the endmarker \( \$ \) is always in \( FOLLOW(S) \) for the start symbol \( S \). It is what decides when to apply an \( \epsilon \)-production: if \( A \to \alpha \) and \( \epsilon \in FIRST(\alpha) \), the entry \( M[A,\ b] \) is filled for every \( b \in FOLLOW(A) \).

Ans: \( \$ \) is the endmarker, an artificial symbol appended to the right end of the input to mark end-of-file; it is also pushed at the bottom of the parser stack initially. It is used as a lookahead column in the LL(1)/LR parsing table and always belongs to \( FOLLOW(S) \) for the start symbol \( S \); the parser accepts when the input has reduced to \( S \) with \( \$ \) as lookahead.

Ans: An \( \epsilon \)-production is a production of the form \( A \to \epsilon \), which derives the empty string and makes \( A \) nullable. It lets a non-terminal be matched by no input at all; in LL(1) table construction, when \( \epsilon \in FIRST(\alpha) \) for \( A \to \alpha \), the entry \( M[A, b] \) is filled for every \( b \in FOLLOW(A) \) (including \( \$ \)).

Ans: A handle of a right-sentential form \( \gamma \) is a substring \( \beta \) together with a production \( A \to \beta \) such that replacing \( \beta \) by \( A \) yields the previous right-sentential form of a rightmost derivation, i.e. \( S \Rightarrow_{rm}^{*} \alpha A w \Rightarrow_{rm} \alpha\beta w \) with \( w \) a string of terminals. Bottom-up parsing is exactly repeated handle pruning, and the handle always appears on top of the stack, which is why a stack suffices.

Ans: Shift is the LR action that pushes the next input symbol (together with the new state number from the ACTION table) onto the parser stack and advances the input pointer. It is chosen when the symbols on the stack do not yet form a complete handle, so more input is needed before a reduction can be made.

Ans: Reduce is the LR action taken when the right side \( \beta \) of a production \( A \to \beta \) — the handle — sits on top of the stack: the parser pops \( 2|\beta| \) entries (\( |\beta| \) symbols with their states), pushes \( A \), and moves to state \( GOTO[s, A] \) where \( s \) is the exposed state. Each reduction is one step of the rightmost derivation traced in reverse.

Ans: Accept is the action that announces a successful parse and halts the parser. In an LR parser built for the augmented grammar it is taken in the state containing the item \( S' \to S\ \cdot \) when the lookahead is \( \$ \) — that is, the whole input has been reduced to the start symbol with nothing left to read.

Ans: Yacc (Yet Another Compiler-Compiler) is the UNIX parser generator: from a .y specification — declarations, translation rules (a context-free grammar with embedded C semantic actions), and support routines, separated by %% — it produces y.tab.c containing the driver yyparse(). The parser it builds is LALR(1), and it calls yylex(), normally generated by Lex, for tokens.

Ans: Lex (GNU version Flex) is a lexical-analyser generator: from a .l specification of regular-expression patterns with C actions it produces lex.yy.c containing yylex(), a DFA obtained internally by Thompson's construction followed by subset construction. Ties are resolved by the longest-match rule and, for equal lengths, by the rule listed first.

Ans: A synthesized attribute of a node \( N \) is one whose value is computed only from the attributes of \( N \)'s children (and of \( N \) itself), so information flows up the parse tree — e.g. \( E \to E_1 + T\ \{\ E.val := E_1.val + T.val\ \} \). Terminals can carry only synthesized attributes, supplied by the lexical analyser, and such attributes can always be evaluated in a bottom-up pass.

Ans: An inherited attribute of a node \( N \) is one whose value is computed from attributes of \( N \)'s parent and/or its siblings, so information flows down and across the tree — e.g. \( D \to T\ L\ \{\ L.type := T.type\ \} \), which passes a declared type to a list of identifiers. It is evaluated in a depth-first, left-to-right traversal rather than purely bottom-up.

Ans: An S-attributed syntax-directed definition is one that uses only synthesized attributes. Every semantic action can therefore be placed at the right end of its production and evaluated bottom-up as the parser reduces, which is why S-attributed definitions can be implemented directly on an LR parser in a single pass with no explicit tree.

Ans: An L-attributed syntax-directed definition allows synthesized attributes plus inherited attributes restricted so that, in a production \( A \to X_1 X_2 \ldots X_n \), an inherited attribute of \( X_j \) depends only on inherited attributes of \( A \) and on attributes of \( X_1, \ldots, X_{j-1} \) — i.e. only on symbols to its left. Such definitions are evaluable in one depth-first left-to-right pass, so they suit predictive/LL translation; every S-attributed SDD is L-attributed, but not conversely.

Ans: Three-address code is a linearised intermediate representation in which every instruction has at most one operator on the right-hand side and at most three addresses, in the general form \( x := y\ op\ z \). Nested expressions are broken up using compiler-generated temporaries: \( a := b + c * d \) becomes \( t_1 := c * d;\ t_2 := b + t_1;\ a := t_2 \).

Ans: A quadruple represents one three-address instruction as a record of four fields — op, arg1, arg2, result; e.g. \( t_1 := b * c \) is (*, b, c, t1). Because the result temporary is named explicitly, instructions may be moved or reordered freely during optimisation, at the cost of storing all those temporary names.

Ans: A triple represents an instruction with only three fields — op, arg1, arg2 — the result is not named; instead the instruction is referred to by its position (index) in the triple array. This saves the space of temporary names, but since operands are encoded as triple positions, moving or reordering an instruction invalidates those references, making optimisation awkward.

Ans: An indirect triple representation keeps the triples in one array plus a separate list of pointers to them giving the execution order. Optimisation reorders or deletes entries in the pointer list only, leaving the triples and their indices untouched — thus retaining the space economy of triples while regaining the reorderability of quadruples.

Ans: Backpatching is the technique that lets jump code be generated in a single pass when a jump's target address is not yet known: the instruction is emitted with the target left blank and its index is kept on a list built by \( makelist() \) and \( merge() \); when the label's address becomes known, \( backpatch(list,\ addr) \) fills that address into every instruction on the list. It is used for boolean expressions and control flow (if, while, short-circuit &&/||).

Ans: An activation record (stack frame) is the block of memory pushed on the control stack for one activation of a procedure. It typically holds, from top down: the returned value, the actual parameters, an optional control link (to the caller's record) and access/static link (for non-local data), saved machine status including the return address and registers, local data, and temporaries.

Ans: A display is an array \( d \) in which \( d[i] \) points to the most recent activation record of the procedure at nesting depth \( i \). It gives constant-time access to non-local variables — the variable is found at a fixed offset in \( d[i] \) — whereas the static-link chain requires walking \( n_{use} - n_{decl} \) links; the cost is saving and restoring display entries on call and return.

Ans: A basic block is a maximal sequence of consecutive three-address instructions with a single entry (its first instruction, the leader) and a single exit (its last instruction): control can enter only at the beginning and, apart from the last instruction, no instruction is a jump or a jump target. Hence if the first instruction executes, all of them execute in order.

Ans: A control flow graph (flow graph) is a directed graph whose nodes are the basic blocks of a procedure, with an edge \( B_1 \to B_2 \) whenever control may pass from the last instruction of \( B_1 \) to the first of \( B_2 \) — either by a jump to \( B_2 \)'s leader or by falling through. Distinguished ENTRY and EXIT nodes are added; the flow graph is the substrate for global data-flow analysis and loop detection.

Ans: A leader is the first instruction of a basic block. The leaders are found by three rules: (i) the first instruction of the intermediate code is a leader; (ii) any instruction that is the target of a conditional or unconditional jump is a leader; (iii) any instruction immediately following a jump is a leader. Each basic block then consists of a leader and all instructions up to, but not including, the next leader.

Ans: A DAG is a directed acyclic graph built for a basic block in which leaves are the initial values of identifiers/constants, interior nodes are operators, and every node carries the identifiers whose value it holds. Identical subexpressions are represented by a single shared node rather than duplicated as in a syntax tree, which directly exposes common subexpressions, dead code and reordering opportunities for local optimisation.

Ans: Common subexpression elimination replaces a recomputation of an expression \( E \) by a reference to its previously computed value, provided \( E \) was already evaluated on every path to this point and none of its operands has been modified since (i.e. \( E \) is available). Thus \( t_1 := b*c; \ldots; t_2 := b*c \) becomes \( t_2 := t_1 \); it is done locally with a DAG/value numbering and globally with available-expressions data-flow analysis.

Ans: Dead code elimination removes instructions whose computed value is never subsequently used — the assigned variable is dead at that point — as well as code that is unreachable. For instance \( x := y + z \) is deleted if \( x \) is never live afterwards, and the body of if (false) { ... } is unreachable. Liveness is established by live-variable (backward) data-flow analysis.

Ans: Constant folding is the compile-time evaluation of expressions whose operands are all known constants, replacing the expression by its computed value — \( x := 3 * 4 + 2 \) becomes \( x := 14 \). It saves run-time work and code space, and is usually enabled and re-triggered by constant propagation.

Ans: Copy propagation replaces later uses of \( x \) by \( y \) after a copy statement \( x := y \), provided that copy is the only definition of \( x \) reaching that use and neither \( x \) nor \( y \) is redefined in between. It does not by itself make the code faster; its value is that it renders \( x \) dead, so dead-code elimination can then delete the copy statement altogether.

Ans: Loop invariant code motion hoists a computation whose operands do not change anywhere inside the loop out of the loop body and into its pre-header, so it is evaluated once instead of once per iteration. The move is legal only if the instruction's block dominates all loop exits (or the variable is dead on exit) and the target is not assigned elsewhere in the loop.

Ans: Strength reduction replaces an expensive operation with an equivalent cheaper one — classically a multiplication by a repeated addition on an induction variable, so that \( t := i * 4 \) inside a loop becomes \( t := t + 4 \) per iteration. Machine-level instances include \( x * 2 \to x + x \) or \( x \ll 1 \), and \( x / 2 \to x \gg 1 \).

Ans: Peephole optimisation is a simple, local improvement technique that slides a small window — the peephole — of a few consecutive target or intermediate instructions and replaces the sequence in it by a shorter or faster equivalent, repeating passes until no more improvements occur. Typical transformations are removing redundant load/store pairs and unreachable code, flow-of-control optimisation (jump to a jump), algebraic simplification (\( x := x + 0 \)), strength reduction and use of machine idioms.

Ans: Register allocation is the phase that decides which program values are held in the machine's limited set of registers at each point in the program, while register assignment chooses the specific physical register for each. The goal is to minimise memory loads and stores; it is normally solved as graph colouring of the interference graph, and the general problem is NP-complete.

Ans: A register interference graph is an undirected graph with one node per live range (variable/temporary) and an edge between two nodes whose live ranges overlap, meaning both are simultaneously live and therefore cannot share a register. Finding a legal allocation is then \( k \)-colouring this graph, where \( k \) is the number of available registers; nodes that cannot be coloured are spilled to memory.

Ans: Spilling is what a register allocator does when registers run short: the value in a register is stored to a location in the activation record and reloaded just before its next use, freeing that register in between. In graph-colouring allocation, a node that cannot be given one of the \( k \) colours is chosen for spilling by a cost heuristic (spill cost / degree), and the graph is rebuilt and recoloured.

Ans: Static Single Assignment form is an intermediate representation in which every variable is assigned exactly once: each assignment creates a new subscripted name (\( x_1, x_2, \ldots \)), and at control-flow join points a \( \phi \)-function such as \( x_3 := \phi(x_1, x_2) \) selects the value that arrived along the executed path. Because every use has a unique definition, def-use information is explicit, which greatly simplifies constant propagation, dead-code elimination and register allocation.

Ans: In a flow graph, a node \( d \) dominates node \( n \) (written \( d\ dom\ n \)) if every path from the ENTRY node to \( n \) passes through \( d \); every node dominates itself, and the closest strict dominator of \( n \) is its immediate dominator \( idom(n) \). Dominators identify natural loops: a back edge \( n \to d \) is one whose head \( d \) dominates its tail \( n \).

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!

Canonical LR(1) Parsing Table and Trace

Part (a): Constructing CLR(1) Parsing Table

Given Grammar:

1. S' → S
2. S → AA
3. A → aA
4. A → b

Step 1: Canonical LR(1) Item Sets

• I0:
  S' → • S, [$]
  S → • AA, [$]
  A → • aA, [a/b] (Since FIRST(A$) = {a, b})
  A → • b, [a/b]
• I1 (Goto I0, S): S' → S •, [$]
• I2 (Goto I0, A):
  S → A • A, [$]
  A → • aA, [$]
  A → • b, [$]
• I3 (Goto I0, a):
  A → a • A, [a/b]
  A → • aA, [a/b]
  A → • b, [a/b]
• I4 (Goto I0, b): A → b •, [a/b]
• I5 (Goto I2, A): S → AA •, [$]
• I6 (Goto I2, a):
  A → a • A, [$]
  A → • aA, [$]
  A → • b, [$]
• I7 (Goto I2, b): A → b •, [$]
• I8 (Goto I3, A): A → aA •, [a/b]
• I9 (Goto I6, A): A → aA •, [$]

Note: Goto(I3, a) loops to I3. Goto(I3, b) loops to I4. Goto(I6, a) loops to I6. Goto(I6, b) loops to I7.

Step 2: CLR(1) Parsing Table

Part (b): Parse Trace for 'aabb$'

Three-Address Code & Control Flow Graphs

Part (a): Generating 3AC

Statement: while (a < b) do if (c < d) then x = y + z; else x = y - z;

Quadruples Representation:

Part (b): Basic Blocks and CFG

• B1: (0) to (1). Evaluates while condition. Exits to B2 or END.
• B2: (2) to (3). Evaluates if condition. Exits to B3 or B4.
• B3: (4) to (5). Executes then branch. Jumps back to B1.
• B4: (6) to (8). Executes else branch. Jumps back to B1.

FIRST/FOLLOW Sets & LL(1) Table

Part (a): Compute FIRST and FOLLOW

Grammar:

1. E → T E'
2. E' → + T E' | ε
3. T → F T'
4. T' → * F T' | ε
5. F → ( E ) | id

FIRST Sets:

• FIRST(F) = { (, id }
• FIRST(T') = { *, ε }
• FIRST(T) = FIRST(F) = { (, id }
• FIRST(E') = { +, ε }
• FIRST(E) = FIRST(T) = { (, id }

FOLLOW Sets:

• FOLLOW(E) = { $, ) } (Start symbol gets $, and ')' follows E in F → (E) ).
• FOLLOW(E') = FOLLOW(E) = { $, ) }
• FOLLOW(T) = FIRST(E') - {ε} ∪ FOLLOW(E') = { +, $, ) }
• FOLLOW(T') = FOLLOW(T) = { +, $, ) }
• FOLLOW(F) = FIRST(T') - {ε} ∪ FOLLOW(T') = { *, +, $, ) }

Part (b): Construct LL(1) Parsing Table

Trace for id + id * id$:

DAG for Basic Blocks & Optimization

Part (a): Constructing the DAG

Original Code:

DAG Construction:

Part (b): Derive Optimized 3AC

By reading the DAG, we eliminate the redundant calculation of 4 * i (Common Subexpression Elimination) and remove redundant variable assignments (Copy Propagation / Dead Code Elimination).

Optimized 3AC:

Chaitin's Graph Coloring for Register Allocation

Part (a): Explanation of the Algorithm

Chaitin's algorithm formulates register allocation as a graph coloring problem. If the CPU has \(K\) physical registers, we attempt to color an Interference Graph using \(K\) colors.

• Node: Represents a variable in the program.
• Edge: An edge connects two nodes if their live ranges overlap (they cannot share the same register).
• Simplification Phase: Repeatedly find a node with degree \(< K\) (fewer than \(K\) edges). Remove it from the graph and push it onto a stack. If all nodes have degree \(\ge K\), a node must be spilled (saved to memory).
• Coloring Phase: Pop nodes from the stack one by one, adding them back to the graph and assigning them a color (register) that is not used by any of their currently active neighbors.

Part (b): Construct Interference Graph

Suppose variables a, b, c, d have lifetimes such that: a interferes with b, c, d. b interferes with a, c. c interferes with a, b, d. d interferes with a, c.

• K = 3 Registers (R1, R2, R3).
• Assign a = R1.
• b neighbors a. Assign b = R2.
• c neighbors a, b. Assign c = R3.
• d neighbors a, c. Can we reuse R2? Yes, because d does not interfere with b. Assign d = R2.
• Coloring successful! No spills needed.

Part (c): Register Spilling Mechanism

If the graph cannot be colored with \(K\) colors, the compiler selects a variable to "spill" to main memory. It generates a STORE instruction after every definition of the variable, and a LOAD instruction before every use. This splits the variable's long live range into several tiny, independent live ranges, significantly reducing the degree of the node in the interference graph, making it easier to color on the next iteration.

SDT for Type Checking & Conversions

Part (a): Type Checking Principles

During Semantic Analysis, the compiler traverses the AST to ensure operators receive operands of compatible types. If types mismatch but are compatible (e.g., int + float), the compiler applies Implicit Type Conversion (Coercion). It inserts a new AST node (like intToFloat) to convert the int operand into a float before the addition occurs.

Part (b): SDD Rules for Arithmetic Type Conversion

Assume we have an expression grammar E → E1 + E2, and our basic types are int and float.

if (E1.type == int and E2.type == int) {
    E.type = int;
    E.node = new Node('+', E1.node, E2.node);
} 
else if (E1.type == float and E2.type == float) {
    E.type = float;
    E.node = new Node('+', E1.node, E2.node);
} 
else if (E1.type == int and E2.type == float) {
    E.type = float;
    // Coerce E1 to float
    Node* t1 = new Node('intToFloat', E1.node);
    E.node = new Node('+', t1, E2.node);
} 
else if (E1.type == float and E2.type == int) {
    E.type = float;
    // Coerce E2 to float
    Node* t2 = new Node('intToFloat', E2.node);
    E.node = new Node('+', E1.node, t2);
} 
else {
    error("Type mismatch");
}

E.type = lookup(id.entry, type);
E.node = new Leaf(id.entry);

Lex/Flex Tool and Program

Part (a): Lex File Structure

A Lex specification file (.l extension) generates a C program (lex.yy.c) that acts as a lexical analyzer. It has three sections:

1. Declarations: %{ ... %} C includes, global variables. Macro definitions for regex patterns.
2. Rules (%%): Pairs of [Regular Expression] { C Code Action }. When the lexer matches the regex against the input stream, it executes the corresponding C code block.
3. User Subroutines (%%): C functions like main() to drive the lexer and yywrap() to handle EOF.

Part (b): Complete Lex Program

A Lex program to count keywords, identifiers, integers, floats, and lines.

Yacc/Bison and Calculator Program

Part (a): Yacc Structure and Precedence

Yacc reads a .y file containing a Context-Free Grammar and generates an LALR(1) parser in C (y.tab.c). To resolve shift-reduce conflicts naturally found in expression grammars, Yacc uses precedence declarations:

• %left '+' '-': Left associative, lower precedence.
• %left '*' '/': Left associative, higher precedence. (Listed lower in the file means higher precedence).

Part (b): Complete Yacc Specification for a Calculator

Lex File (calc.l) - Feeds tokens to Yacc

Yacc File (calc.y)

ICG for 2D Array References

Part (a): Memory Layout Orders

Physical memory is a 1-dimensional array of bytes. A 2D array A[M][N] (where M = rows, N = columns) must be linearized.

• Row-Major Order: Used by C/C++. Elements of the first row are stored contiguously in memory, followed by the second row, etc.
• Column-Major Order: Used by Fortran/MATLAB. Elements of the first column are stored contiguously, followed by the second column, etc.

Part (b): Address Calculation & 3AC

Given: Array A[M][N]. Let w be the size of one element in bytes (e.g., 4 bytes for an int). Let Base be the starting memory address of A[0][0].

Address Formula (Row-Major):
\(\text{Address}(A[i][j]) = \text{Base} + ((i \times N) + j) \times w\)

Generating 3AC for x = A[i][j]:

Assume the array has N = 10 columns and element size w = 4 bytes. We must generate low-level intermediate code that explicitly computes the memory offset.

Next-Use Information & Register Descriptors

Part (a): Next-Use Calculation

Next-use information tells the code generator exactly when the value of a variable will be used next in the basic block. This is critical for Register Allocation. If a variable in a register has no "next use" (it is dead), the register can be immediately reused for another variable without saving it to memory.

Register Descriptor: Tracks which variables are currently held in each physical register.

Address Descriptor: Tracks the current memory locations where the valid value of a variable resides (could be in a register, in RAM, or both).

Part (b): Trace Register Descriptors

Code Segment: x = (a - b) + (a - c) + (a - b)

Convert to 3AC first:

Trace Table (Assume 2 Registers R0, R1):

Global Data Flow Analysis: Reaching Definitions

Part (a): Global Data Flow Analysis

Global Data Flow Analysis determines how values and properties of variables propagate across the Control Flow Graph (CFG), beyond the boundaries of a single basic block. It uses an iterative algorithm to solve a system of data-flow equations until a fixed point (convergence) is reached.

Part (b): Reaching Definitions Equations

A definition \(d\) of a variable \(x\) reaches a point \(p\) if there is a path from \(d\) to \(p\) such that \(x\) is not killed (overwritten) along the path.

• GEN[B]: The set of definitions generated within block B that reach the end of B without being killed locally.
• KILL[B]: The set of all definitions in the entire program that define the same variables defined in B.

Iterative Equations (Forward Flow):

1. \(\text{IN}[B] = \bigcup_{P \in \text{predecessors}(B)} \text{OUT}[P]\)
(A definition reaches the start of B if it reaches the end of any of B's predecessors).

2. \(\text{OUT}[B] = \text{GEN}[B] \cup (\text{IN}[B] - \text{KILL}[B])\)
(A definition reaches the end of B if it was generated in B, OR if it entered B and was not killed in B).

Solving Iteratively:

1. Initialize \(\text{OUT}[B] = \emptyset\) for all blocks.
2. Loop through all blocks, calculating \(\text{IN}\) then \(\text{OUT}\).
3. Repeat the loop until no \(\text{OUT}\) set changes for any block (Convergence).

Live Variables & Available Expressions

Part (a): Concepts

• Available Expressions: An expression x + y is available at point \(p\) if every path from the start node to \(p\) evaluates x + y, and neither x nor y is modified between the last evaluation and \(p\). Used for Global Common Subexpression Elimination.
• Live Variable Analysis: A variable \(x\) is live at point \(p\) if its value at \(p\) could be read along some path before \(x\) is redefined. Used for Dead Code Elimination and Register Allocation.

Part (b): Backward Data Flow Equations for Live Variables

Because liveness depends on future uses of a variable, information flows backward through the CFG.

• USE[B]: Variables whose values are read in B prior to being overwritten in B.
• DEF[B]: Variables that are definitely overwritten in B.

Iterative Equations (Backward Flow):

1. \(\text{OUT}[B] = \bigcup_{S \in \text{successors}(B)} \text{IN}[S]\)
(A variable is live at the end of B if it is live at the start of any of B's successors).

2. \(\text{IN}[B] = \text{USE}[B] \cup (\text{OUT}[B] - \text{DEF}[B])\)
(A variable is live at the start of B if it is used in B, OR if it is live at the end of B and not redefined in B).

Symbol Tables for Object-Oriented Scopes

Part (a): Organization

Object-Oriented Languages (like Java/C++) introduce complex nested scopes: Global → Namespace → Class → Method → Local Block. The symbol table must support inheritance (resolving variables in a parent class) and shadowing (local variables hiding class fields).

The compiler creates a hierarchical tree of symbol tables. Each table represents a scope and contains a pointer to its enclosing (parent) scope's table.

Part (b): Scope Tree Structure and Lookup

Symbol Lookup Mechanism:

If x is referenced inside the if-block:

1. Search the if-block table. Not found.
2. Follow pointer to method1() table. Not found.
3. Follow pointer to Class A table. Found int x. Return type and address.
4. If not found in Class A, and Class A extends BaseClass, the pointer traces up to BaseClass before checking Global.

Runtime Storage Allocation

Part (a): Storage Regions

For procedural languages, OS memory given to a program is divided into:

• Code/Text Segment: Read-only, executable machine instructions.
• Static/Global Data: Global variables and static variables allocated exactly once at compile-time.
• Heap: Dynamically allocated memory (e.g., malloc()). Grows upwards.
• Stack: Memory for function calls and local variables. Grows downwards.

Part (b): Activation Record Creation Trace

When caller() invokes callee(int x):

1. Caller pushes the actual parameter x onto the stack.
2. Caller saves its own machine status (specifically the Return Address PC) onto the stack.
3. Caller executes the jump instruction to callee's code.
4. Callee pushes the old Frame Pointer (Control Link) onto the stack to save the caller's stack frame base.
5. Callee updates the Frame Pointer to the current Stack Pointer (establishing its own Activation Record base).
6. Callee decrements the Stack Pointer to allocate space for its own local variables and temporaries.
7. When returning, the process reverses: the stack pointer is restored to the control link, and execution jumps back to the saved return address.

Garbage Collection (Generational)

Part (a): Standard Algorithms Overview

• Mark-and-Sweep: Marks live objects, sweeps dead ones. Causes fragmentation.
• Copying Collector: Copies live objects to a new memory space. No fragmentation, but wastes 50% RAM.
• Reference Counting: Each object tracks how many pointers point to it. If count reaches 0, it is immediately freed. Cannot detect cyclical references (A points to B, B points to A).

Part (b): Generational Garbage Collection

The Generational Hypothesis: "Most objects die young." (e.g., local variables in functions). Objects that survive a long time (e.g., global caches) will likely continue to survive.

Mechanism:

1. The heap is divided into generations: Young Generation (Nursery) and Old Generation (Tenured).
2. All new objects are allocated in the Young Gen.
3. Because most objects die young, the GC runs a Minor GC frequently on the Young Gen using a fast Copying Collector. It reclaims massive amounts of memory quickly.
4. Objects that survive multiple Minor GCs are "promoted" to the Old Gen.
5. The Old Gen fills up very slowly. A Major GC (usually Mark-and-Sweep) runs infrequently on the Old Gen.

Advantage: Drastically reduces GC pause times because the collector doesn't have to scan the entire heap every time memory runs low.

Error Detection and Recovery

Part (a): Errors Across Phases

• Lexical Errors: Unrecognized characters (@), unterminated strings.
• Syntax Errors: Missing semicolons, unbalanced parentheses, invalid statements.
• Semantic Errors: Type mismatches, undeclared variables, parameter count mismatches.
• Logical Errors: Not caught by the compiler (e.g., infinite loops).

Part (b): Panic Mode vs Phrase-Level in Parsers

Panic Mode in LL(1) / LR(1):

• When an unexpected token arrives, the parser is stuck.
• It enters panic mode, popping states off the stack and discarding input tokens until it finds a "synchronization token" (e.g., } or ;).
• Once synchronized, parsing resumes from a known safe state.

Phrase-Level Recovery:

• The parser detects the error and attempts a local patch.
• If the input is x = y * ;, the parser might artificially insert an identifier token (making it x = y * id;) or delete the *, issue an error message, and continue.
• This prevents massive chunks of code from being skipped, but requires carefully designed error productions in the grammar (e.g., adding a grammar rule Stmt → error ; to catch malformed statements).

Peephole Optimization (x86 Assembly)

Part (a): Pattern Matching

The compiler scans the generated target assembly code using a small sliding window (2-4 instructions). If the window matches a known inefficient pattern, it is replaced with an optimized sequence.

Part (b): Applying Transformations to 8086 Code

Unoptimized Snippet:

Peephole Applied:

Loop Optimizations

Part (a): Concepts

• Loop Unrolling: Duplicating the loop body to reduce the number of iterations and the overhead of evaluating the loop condition/jump.
• Loop Jamming (Fusion): Merging two adjacent loops that iterate over the same range into a single loop to reduce loop overhead.
• Software Pipelining: Reorganizing loops such that different iterations of the loop are overlapped. E.g., loading data for iteration i+1 while computing data for iteration i.

Part (b): Matrix Multiplication Unrolling

Original Loop:

Unrolled Loop (Factor of 4):

Advantages: Eliminates branch instructions entirely. Modern Superscalar CPUs can execute all 4 multiplication instructions simultaneously (Instruction-Level Parallelism) because there are no data dependencies between them.

LLVM Compiler Architecture

Part (a): LLVM Architecture

LLVM is a modern, modular compiler framework used by Clang (C/C++), Rust, and Swift.

• Front-End: Parses the source language and generates LLVM Intermediate Representation (LLVM IR). Clang is the front-end for C/C++.
• LLVM IR: The core of the system. It is a strictly typed, RISC-like, Static Single Assignment (SSA) language. It acts as the universal language for the optimizer.
• Optimizer (Middle-End): A collection of modular Passes that read LLVM IR, optimize it, and emit optimized LLVM IR.
• Back-End: Reads the optimized LLVM IR and translates it into specific machine code (x86, ARM) via Instruction Selection and Register Allocation.

Part (b): LLVM Pass Manager

The Pass Manager controls the execution of optimization passes.

• Analysis Passes: Compute information about the IR without modifying it (e.g., Call Graph analysis, Dominator Tree analysis).
• Transform Passes: Mutate the IR to optimize it (e.g., mem2reg promotes memory allocations to SSA registers, loop-unroll unrolls loops).
• The Pass Manager schedules these passes, ensuring that if a Transform pass invalidates the Dominator Tree, the Analysis pass is automatically re-run before the next pass that requires it.

Complete Trace Through All 6 Compiler Phases

Part (a) & (b): Tracing a = b + c * 60

1. Lexical Analysis: Converts character stream to tokens.

2. Syntax Analysis: Generates Parse Tree (or AST) enforcing precedence.

3. Semantic Analysis: Type checking. Assuming a, b, c are floats.

4. Intermediate Code Generation: Generates 3AC.

5. Code Optimization: Applies Constant Folding at compile time.

6. Target Code Generation: Generates assembly (assuming x86-like FPU).

SLR(1) Parsing Table Construction

Part (a): Construct SLR(1) Table

Grammar:

1. S' → S
2. S → L = R
3. S → R
4. L → * R
5. L → id
6. R → L

FOLLOW Sets:

• FOLLOW(S) = { $ }
• FOLLOW(L) = { =, $ }
• FOLLOW(R) = { =, $ }

LR(0) Item Sets (DFA):

• I0: S' → •S, S → •L=R, S → •R, L → •*R, L → •id, R → •L
• I1 (Goto I0, S): S' → S•
• I2 (Goto I0, L): S → L•=R, R → L•
• I3 (Goto I0, R): S → R•
• I4 (Goto I0, *): L → *•R, R → •L, L → •*R, L → •id
• I5 (Goto I0, id): L → id•
• I6 (Goto I2, =): S → L=•R, R → •L, L → •*R, L → •id
• I7 (Goto I4, R): L → *R•
• I8 (Goto I4, L): R → L•
• I9 (Goto I6, R): S → L=R•

(Goto(I4, *) = I4, Goto(I4, id) = I5, Goto(I6, *) = I4, Goto(I6, id) = I5, Goto(I6, L) = I8)

Part (b): Checking for Conflicts

An SLR(1) table uses FOLLOW sets to place Reduce actions. Look at State I2:

• S → L•=R dictates a Shift action on the symbol = (Goto I6).
• R → L• dictates a Reduce action by rule 6. According to SLR(1) rules, this reduction is placed in the columns for FOLLOW(R).
• Since FOLLOW(R) contains = and $, we must place Reduce 6 in the column for =.

Conflict: In State I2, under column =, we have both a Shift action and a Reduce action. Therefore, the SLR(1) table has a Shift-Reduce (S-R) conflict, and this grammar is NOT SLR(1).

LR Item Sets: SLR vs LALR vs CLR

Part (a): Generation Methods

• SLR(1): Builds the DFA using basic LR(0) items (no lookahead). It blindly places Reduce actions using global FOLLOW() sets. It is small but prone to conflicts.
• CLR(1): Builds the DFA using LR(1) items (Item + Lookahead). Lookaheads are precisely tracked through transitions. It places Reduce actions only in the columns specified by the item's lookahead. It is powerful but produces massive state machines because it creates distinct states for identical items that have different lookaheads.
• LALR(1): Starts by generating the massive CLR(1) DFA. It then scans the states and merges states that have the exact same "Core" (the LR(0) part of the item) but different lookaheads. The resulting DFA has the exact same number of states as SLR(1), but retains precise lookahead information.

Part (b): Merging CLR to LALR

Suppose CLR generates two states:

State 10: A → X • Y, [a]
State 15: A → X • Y, [b]

Because the core A → X • Y is identical, LALR merges them into a single state:

Merged State 10_15: A → X • Y, [a/b]

Conflict Resolution: Merging LR(1) states to form LALR(1) states can never introduce a new Shift-Reduce conflict. If a shift-reduce conflict appears in the merged state, it must have already existed in the original CLR(1) states. However, merging can occasionally introduce new Reduce-Reduce conflicts.

Backpatching in Control Flow

Part (a): Explanation

Backpatching is used in one-pass compilers. When parsing a boolean expression with short-circuit evaluation, the compiler generates jump instructions but doesn't know the destination addresses yet. It leaves them blank and adds their instruction indexes to a truelist or falselist. When the destination code is finally generated, a backpatch() function fills in the blanks.

Part (b): Backpatched 3AC for if (a < b or c < d) and e < f then x = 1;

Assuming instructions start at index 100.

Memory Management for OOP (C++/Java)

Part (a): General Memory Management

In OOP, objects are typically allocated dynamically on the Heap using new. Memory is reclaimed either manually (delete in C++) or automatically via Garbage Collection (Java). Local object references are stored on the Stack within activation records.

Part (b): Object Layout and Virtual Method Tables (VTable)

Object Layout in Memory: An object in memory consists of:

1. A hidden pointer to the class's Virtual Method Table (vptr).
2. The object's instance variables (fields). Fields inherited from parent classes are placed first in the layout to ensure binary compatibility.

Dynamic Dispatch via VTable:

To support Polymorphism (Method Overriding), the compiler creates one VTable per class (not per object). The VTable is an array of function pointers pointing to the most derived implementation of virtual methods.

When a virtual method is called (e.g., obj->draw()):

1. The CPU follows obj's hidden vptr to find the class's VTable.
2. It looks up the index for draw() (e.g., index 2) in the VTable.
3. It jumps to the function address stored at that index.

Code Generation for Target Architectures

Part (a): RISC vs CISC

Part (b): Instruction Selection via Tree-Rewriting

The compiler represents the Intermediate Code as a forest of trees. The Target Architecture's instruction set is represented as a set of tree templates (patterns).

Instruction selection is treated as a Tree Pattern Matching problem. The compiler "tiles" the IR tree with target instruction templates. If a template matches a subtree, the compiler replaces the subtree with the corresponding assembly instruction. Dynamic programming (like the Sethi-Ullman algorithm) is used to find the optimal tiling that minimizes execution cost.

Dominator Trees and Natural Loops

Part (a): Concepts

• Dominator: Node A dominates Node B if every path from the CFG entry node to B must pass through A.
• Dominator Tree: A tree representing dominance. The parent of a node is its immediate dominator (the closest dominator).
• Natural Loop: A loop in the CFG that has a single entry point (the header) and at least one back-edge that returns to the header.

Part (b): Algorithm to Identify Natural Loops

1. Compute Dominators: For all nodes in the CFG.
2. Find Back-Edges: A CFG edge from node T (Tail) to node H (Header) is a back-edge IF AND ONLY IF H dominates T.
3. Construct Loop Body: For every back-edge T → H, the natural loop consists of H, T, and all nodes that can reach T without passing through H.
4. Insert Pre-Header: The compiler injects a new block (the pre-header) immediately before the loop header. This provides a safe place to move invariant code (Loop Hoisting) out of the loop.

Value Numbering

Part (a): LVN vs GVN

Value Numbering tracks the mathematical values computed by a program rather than the variable names themselves.

• Local Value Numbering (LVN): Operates within a single Basic Block. Assigns unique integer IDs to distinct values. Used for localized Common Subexpression Elimination and Constant Folding.
• Global Value Numbering (GVN): Extends this logic across the entire CFG using SSA form. Much more powerful, allowing the compiler to prove that variables in entirely different blocks hold the same underlying value.

Part (b): Applying LVN

Code:

LVN Trace:

1. a = x + y: Give x value 1, y value 2. Expression + (1,2) gets value 3. a maps to 3.
2. b = x + y: Expression + (1,2) already exists and has value 3! Map b to 3. (Optimize: b = a).
3. a = 17: Give 17 value 4. Update a to map to 4.
4. c = x + y: Expression + (1,2) still exists as value 3. Map c to 3. (Optimize: c = b because a was overwritten!).

Interprocedural Optimization and Inlining

Part (a): Interprocedural Optimization (IPO)

Standard optimizations operate within a single function boundary. IPO analyzes the entire program (or multiple files via Link-Time Optimization) to optimize across function calls. Techniques include Dead Function Elimination and Constant Propagation across arguments.

Inline Expansion: The most aggressive IPO technique. The compiler replaces a function call with the actual body of the called function.

Part (b): Tradeoffs of Function Inlining

Target Machine Architecture & Code Generation

Part (a): Target Machine Model

A standard target machine model assumes a byte-addressable memory, \(n\) general-purpose registers (\(R_0\) to \(R_{n-1}\)), and standard instructions (LOAD, STORE, ADD, SUB, MULT, BRANCH). Instruction costs usually correlate with memory access (Register-to-Register = 1 cost, Memory-to-Register = 2 cost).

Part (b): Generating Assembly using 2 Registers

Statement: x = a + b * c

Assuming we have registers R0 and R1. To minimize memory accesses, we should evaluate the most deeply nested subtree first (the multiplication).

Static Program Analysis

Part (a): Tools and Linters

Static analysis examines source code without executing it. Modern compilers (like Clang) use static analysis infrastructure to issue warnings (e.g., "variable used uninitialized", "memory leak"). Linters (like ESLint or SonarQube) are standalone static analysis tools enforcing style and catching common bugs.

Part (b): Abstract Interpretation and Model Checking

• Abstract Interpretation: Mathematically models the execution of a program across all possible inputs. Instead of tracking exact values (e.g., x = 5), it tracks abstract properties (e.g., "x is a positive integer"). It guarantees the absence of certain bugs (e.g., proving no array out-of-bounds errors can ever occur).
• Model Checking: Explores the state space of a program to verify properties, typically for concurrent systems. It creates a state-machine of the program and checks if "bad states" (like deadlocks or race conditions) are reachable. If a bad state is found, it provides a counter-example trace to reproduce the bug.