Peephole optimization scans the generated (often target) code through a small sliding window ("peephole") of a few consecutive instructions and replaces recognized inefficient patterns with shorter or faster equivalents. It is applied repeatedly since one replacement can expose the next.

1. Redundant load/store elimination - a store immediately followed by a load of the same value from the same location is unnecessary.

2. Algebraic simplification - identity operations that don't change the value are removed.

3. Strength reduction - cheap machine instructions replace expensive ones for the same effect.

4. Unreachable code / jump-to-jump elimination - code after an unconditional jump/return (never reached) is deleted, and a jump to another jump is collapsed to jump straight to the final target.

Because it works on a small local window, peephole optimization is cheap to run yet consistently removes redundancy left behind by naive syntax-directed code generation.

The code generator turns intermediate representation into target machine code while trying to produce fast, compact code; several interacting issues make this a genuinely hard combinatorial problem:

• Instruction selection - choosing which machine instruction(s) implement a given IR operation; the same computation can often be done several ways (e.g. multiply-by-power-of-2 as a shift), and CISC-style machines add complexity through instructions that combine several IR operations (e.g. an addressing mode that does load+add).
• Register allocation and assignment - deciding which values are kept in the limited set of physical registers (allocation) and which specific register each gets (assignment); poor decisions force values to be spilled to memory, adding load/store overhead.
• Evaluation order - the order in which independent computations are scheduled affects the number of registers needed simultaneously and can affect pipeline/instruction-level parallelism on the target.
• Choice of addressing modes and memory management - exploiting indexed, indirect, or auto-increment addressing modes can shorten code, but requires matching IR access patterns to what the target supports.
• Target machine characteristics - instruction set, pipeline behavior, and cost/timing of each instruction all constrain what a "good" translation looks like, so the generator must be tailored to (or parameterized by) the target architecture.

These issues are interdependent - e.g. instruction selection affects how many registers are needed - which is why practical code generators (or separate optimization passes) address them together rather than in complete isolation.

Chaitin's algorithm allocates a fixed number k of physical registers to program values via graph coloring: build an interference graph whose nodes are live ranges (variables/temporaries) and whose edges connect any two live ranges simultaneously live at some point (so they cannot share a register); then find a k-coloring of this graph, where a color represents a register.

Algorithm outline:

1. Build the interference graph from live-range analysis.
2. Simplify - repeatedly remove any node with degree less than k (it is trivially colorable later) and push it onto a stack.
3. Spill decision - if every remaining node has degree >= k, optimistically pick a node as a potential spill candidate (using a cost heuristic - low use/def frequency, high degree), remove it, and continue simplifying.
4. Select - pop nodes off the stack one by one, assigning each a register color different from its already-colored neighbors; a node marked as a potential spill may still get a color if one happens to be free.
5. Actual spill code - only if select genuinely fails to find a free color is the value spilled to memory, and the process (build/simplify/select) is repeated on the rewritten program.

When the parser encounters a token that cannot be legally derived at that point, an error-recovery strategy lets compilation continue (to catch further errors in one pass) instead of stopping at the first mistake. Two common strategies:

Compilers frequently combine both: phrase-level fixes for well-known common mistakes, falling back to panic mode synchronization for anything unrecognized, so error messages stay precise while parsing always terminates.

Scope rules determine which declaration a variable reference is bound to. The two disciplines differ in when that binding is decided.

A compiler's symbol table stores each identifier's attributes (type, scope, offset, etc.) and must support fast insert and lookup as well as correct scoping. A common efficient organization is a hash table with scope chaining: identifier names are hashed into buckets, and entries for identifiers declared in nested scopes are chained so that inner-scope declarations shadow outer ones.

On entering a new scope, a fresh scope marker/level is pushed; declarations insert new entries at the head of their name's chain, tagged with the current scope level. A lookup follows the hash bucket's chain and returns the first (innermost, most recently declared) matching entry, correctly implementing shadowing. On leaving a scope, all entries tagged with that scope level are removed (or a scope-boundary marker is popped), restoring visibility of the outer declarations - giving average O(1) insert/lookup with correct nested-scope resolution.

Type checking verifies that operations are applied to operands of compatible types, using the static or inferred types recorded in each expression's syntax tree/symbol table entries. When operand types don't match an operator's exact required types but are still compatible, a type conversion (coercion) is inserted.

During semantic analysis the compiler applies coercion rules bottom-up on the expression tree: if an operator expects type T and the actual operand has a type coercible to T, a conversion node is inserted around that operand before code generation, so the emitted code always operates on matching types.

Static Single Assignment (SSA) is an intermediate representation property in which every variable in the program is assigned a value exactly once (textually) - each new assignment to a source variable creates a fresh SSA name (e.g. x becomes x1, x2, x3...). Where control-flow paths carrying different definitions of the same original variable merge, a special phi (Φ) function is inserted at the join point to select the correct incoming value based on which predecessor block control arrived from.

Because every use in SSA has exactly one reaching definition, def-use chains become explicit and trivial to compute, which greatly simplifies several optimizations:

• Constant propagation - a use trivially inherits the single definition's value if it is constant.
• Dead code elimination - a definition with no uses can be deleted immediately, without a separate liveness pass.
• Value numbering / common sub-expression elimination - identical SSA expressions are guaranteed to compute identical values, so redundancy detection is direct.

This is why most modern optimizing compilers (LLVM, GCC's GIMPLE-SSA) build SSA as their central optimization IR before eventually converting back out of SSA for code generation.

Data flow analysis computes, for each program point, facts that hold on every possible execution path reaching (or leaving) that point, by solving equations over the control-flow graph. Two classic instances:

Reaching Definitions (a forward problem) - a definition d of variable v "reaches" a point p if there is some path from d to p along which v is not redefined. Used for constant propagation and to build def-use chains.

Live Variables Analysis (a backward problem) - a variable v is live at point p if there exists a path from p to some use of v along which v is not redefined first. Used for register allocation (a dead variable's register can be reused) and dead-code elimination.

Both are solved by iterating over the flow graph until the IN/OUT sets reach a fixed point - reaching definitions propagates information forward from entry, live variables propagates it backward from exit.

A retargetable compiler can generate code for a new target machine by replacing only its back end, without rewriting the front end or optimizer. This is achieved by funneling all source languages through a single, machine-independent intermediate representation (IR), keeping every machine-specific detail (instruction patterns, register classes, calling conventions) isolated behind a well-defined backend interface.

In both designs, retargetability comes from the same principle: a common, machine-independent representation and optimizer sit in the middle, and only a well-isolated backend module needs to change to support a new instruction set architecture.

Part (a): Canonical LR(1) construction. Augmented grammar and productions numbered:

LR(1) items carry a lookahead. Applying closure/goto (closure rule: for item [A→α.Bβ, a], add [B→.γ, b] for every b in FIRST(βa)) produces 10 canonical states:

goto(I3,a)=I3 and goto(I6,a)=I6 (self loops). The CLR(1) ACTION/GOTO table (r1: S→AA, r2: A→aA, r3: A→b):

No cell has more than one action — the grammar is CLR(1) with no shift-reduce or reduce-reduce conflicts.

Part (b): Trace of "aabb$".

The two reduced A's are "aab" and "b", concatenating to "aabb" = the input string, confirming the trace is correct.

Part (a): TAC and three-address representations. Three-address code for the statement (with statement numbers as labels):

Quadruples name a temporary explicitly in the result field, so operands can be reordered freely at optimization time. Triples instead refer to another triple's result by its position/index (i), so moving a triple invalidates every reference to it; Indirect Triples fix this by adding a separate list of pointers into the triple table representing execution order — code motion during optimization then only reorders the pointer list, leaving the triple table itself untouched.

Part (b): Control Flow Graph and Basic Blocks. Applying the leader rules (first statement; targets of any goto/conditional goto; statement immediately after a goto/conditional goto) to the 10 TAC statements gives leaders {1,3,5,8}, hence 4 basic blocks:

Part (a): FIRST and FOLLOW sets.

Part (b): LL(1) table and trace of "id + id * id $".

Part (a): DAG construction. Scanning the basic block, t1=4*i and t3=4*i compute the identical expression (same operator, same operand values, no intervening redefinition of i) so they collapse onto one shared DAG node with two labels:

Part (b): Optimized 3AC derived from the DAG. Reading the DAG in a valid topological (bottom-up) order and emitting one instruction per distinct node, using each node's surviving live label directly, eliminates the recomputation of t3 and the redundant copies via t6/t7:

This reduces the block from 9 three-address statements to 6, removing exactly the two dead temporaries (t3, and the extra copies via t6/t7) that the DAG's shared-node structure exposed.

Part (a): Chaitin's algorithm. (1) Build an interference graph: one node per live range/variable, an edge between two nodes if they are simultaneously live at some program point. (2) Simplify: repeatedly remove (push onto a stack) any node with degree < k (k = number of available registers) since it is trivially colorable once its neighbors are colored. (3) If stuck (all remaining nodes have degree ≥k), optimistically pick a spill candidate (lowest spill-cost/degree ratio), mark it and push it anyway. (4) Select: pop the stack, assigning each node a register/color different from its already-colored neighbors; if a marked spill candidate genuinely cannot get a color, generate spill code (store after definition, reload before each use) and rebuild the graph.

Part (b): Worked interference graph, k=3 registers. Consider: a=10; b=20; c=a+b; d=a-b; e=c+d; print(e). Live ranges: a:[I1-I4], b:[I2-I4], c:[I3-I5], d:[I4-I5], e:[I5-I6]. By the standard convention a variable does not interfere with the destination of the statement that consumes it as its very last use, giving interference edges (a,b), (a,c), (b,c), (c,d); d and e end up isolated from a/b and c/d respectively beyond the one edge shown.

Simplify order (remove lowest-degree first): e (deg 0), d (deg 1), a (deg 2), b (deg 1), c (deg 0) — pushed in that order onto the stack. Select (pop in reverse): c→R1 (no colored neighbor); b→R2 (avoids c=R1); a→R3 (avoids b=R2, c=R1); d→R2 (avoids c=R1 only); e→R1 (no neighbors).

Since the graph's largest clique has size 3 = k, all 5 variables are colored with exactly 3 registers and no spill is required.

Part (c): Register spilling. If simplify gets stuck (every remaining node has degree ≥ k) a node is optimistically marked as a potential spill and pushed anyway; during select, if it truly cannot be given a free color, the variable is spilled: it is kept in memory, a store is emitted immediately after its definition and a fresh load is emitted immediately before each use, splitting its live range into many short ranges that are individually easy to color, at the cost of extra memory traffic.

Part (a): Syntax-Directed Translation (SDT) for type checking attaches semantic type attributes to grammar symbols and computes them with rules tied to each production. Every expression non-terminal carries a synthesized attribute type which is computed bottom-up from the types of its children. A type checker uses two building blocks: (1) a table of basic type compatibility (e.g. int op int -> int, real op real -> real) and (2) a set of coercion (implicit conversion) rules that say which types may be automatically widened to a common type when the operand types differ. In most languages, only widening conversions (int -> real, char -> int) are performed implicitly; a narrowing conversion (real -> int) requires an explicit cast because it can lose information. When the type checker finds E1 op E2 with different types, instead of rejecting the program it inserts a unary conversion operator such as inttoreal around the narrower operand's AST node, producing a new synthesized type for the whole expression. This is exactly how languages like C and Java silently promote int to double in mixed arithmetic. Type checking and conversion insertion therefore happen together, in the same pass, as the parse tree (or an equivalent syntax-directed evaluation during LR parsing) is built or walked.

Part (b): The SDD below defines type and node (the AST pointer) synthesized attributes for arithmetic expressions, inserting explicit conversion nodes wherever the operand types differ.

Here coerce(Ei) denotes wrapping Ei.node in an inttoreal unary AST node only if Ei.type = int, otherwise returning Ei.node unchanged. Each conversion node is later translated by the code generator into an explicit CVTI2R (integer-to-real) machine instruction, so the widening that was implicit at the source level becomes explicit in the intermediate/target code.

Part (a): A Lex/Flex source file (conventionally .l) is divided into three sections separated by the delimiter %%:

• Definitions section: everything before the first %%. C declarations, global variables and header includes are written inside %{ ... %} markers and are copied verbatim into the generated lex.yy.c. Below that, regular-expression name definitions (e.g. DIGIT [0-9]) may be given so later rules can reuse them as {DIGIT}.
• Rules section: between the first and second %%. Each line is a pair pattern  action where pattern is a regular expression and action is a fragment of C executed whenever the longest input text matching that pattern is found (maximal-munch / longest-match rule; ties broken by rule order). The matched text is available in the global char *yytext and its length in int yyleng.
• User code section: everything after the second %%, copied verbatim - normally contains main() (which calls yylex()) and any helper functions such as a manual yywrap().

Flex compiles the rules into a single DFA-driven scanning loop; when run it repeatedly calls the internal matcher, and for every token recognized it executes the associated action and then resumes scanning, until end of input (yywrap() returning 1) is reached.

Part (b): A complete Lex program that scans C source and counts keywords, identifiers, integer constants, floating-point constants, and source lines:

Compiled with flex scanner.l && gcc lex.yy.c -lfl -o scanner. The order of rules matters: {FLOAT} is placed before {INT} so a token like 3.14 is not first partially matched as the integer 3.

Part (a): A Yacc/Bison specification (.y) has the same three-section layout as Lex: a declarations section (before the first %%) declares terminal tokens with %token, non-terminal result types with %type, and, crucially, precedence and associativity with lines such as %left '+' '-' followed by %left '*' '/' - operators declared on a later line bind tighter, and the keyword (%left, %right, %nonassoc) fixes how a chain of same-precedence operators associates. This lets an otherwise ambiguous grammar such as E : E '+' E | E '*' E be resolved automatically by the LALR table generator without needing to rewrite the grammar into unambiguous non-terminals for every precedence level. The grammar rules section (between the two %%) lists each production together with a semantic action in braces, where $$ denotes the value (attribute) of the left-hand non-terminal and $1, $2, ... denote the values of the right-hand symbols in order; Yacc builds a push-down automaton with a state/action table (shift, reduce, accept, error) from these rules, resolving shift-reduce conflicts using the declared precedence of the token about to be shifted versus the precedence of the rule about to be reduced. The final C code section supplies yylex() (usually generated by a companion Lex file), main(), and yyerror().

Part (b): A complete Yacc specification for an infix arithmetic calculator:

Companion lexer (calc.l) that supplies NUMBER tokens:

Built with yacc -d calc.y && lex calc.l && gcc y.tab.c lex.yy.c -o calc. The %left/%right declarations make *,/ bind tighter than +,-, and %prec UMINUS gives unary minus the highest precedence, correctly parsing expressions like 2+3*4 and -2*(3+4).

Part (a): Address calculation for A[i][j]. For an array with row bounds [low1..high1], column bounds [low2..high2], n2 = number of columns = high2-low2+1, and element width w:

• Row-major order (rows stored contiguously, used by C/C++/Java): addr(A[i][j]) = base + ((i-low1)*n2 + (j-low2)) * w. Row-major visits an entire row before moving to the next, so the rightmost index j varies fastest.
• Column-major order (used by FORTRAN): with n1 = number of rows, addr(A[i][j]) = base + ((j-low2)*n1 + (i-low1)) * w. Here the leftmost index i varies fastest.

Part (b): 3AC for x = A[i][j] (row-major, 0-based indices, so low1=low2=0). A compile-time constant c = base - (low1*n2+low2)*w is precomputed so no subtraction is needed at run time:

This is exactly the standard "address descriptor" pattern used by real compilers: the multiply by n2 and the final scale by w are the only run-time arithmetic operations, with the bounds-dependent constant folded away at compile time.

Part (a): Next-use / register descriptor algorithm. Scanning a basic block backward, for statement i: x = y op z: (1) attach to statement i the current liveness/next-use info of x, y, z (as known from statements below i); (2) in the symbol table, set x to "not live, no next-use" (it is about to be (re)defined going forward); (3) set y and z to "live, next-use = i". Forward code generation then uses getReg(): prefer an already-empty register; else reuse a register whose current value is dead (no next use and not live-out); else spill the value with the least-urgent next use to memory.

Part (b): Trace for x = (a-b) + (a-c) + (a-b). TAC: t1=a-b; t2=a-c; t3=t1+t2; t4=a-b; x=t3+t4.

Using 2 registers R0,R1 (a,b,c stay in memory, never needing a permanent register since operations can read a memory operand directly):

Because next-use correctly showed t1 and t2 die at statement 3, R0 was safely reused for t3 instead of spilling — the whole expression is evaluated with only 2 registers and zero spills.

Part (a): Global data flow analysis computes, for every basic block in a program's control flow graph (CFG), facts that depend on paths through the whole procedure rather than on a single block in isolation (e.g. "which assignments to a variable might still be live/valid at this point"). Because a CFG can contain cycles (loops), these facts cannot be computed in one top-down or bottom-up sweep; instead they are expressed as data flow equations relating each block's input set to its predecessors'/successors' output sets, and solved iteratively: initialize all sets (commonly to the empty set), then repeatedly recompute every block's IN/OUT using the equations until no set changes between two consecutive passes - this is the fixed point, guaranteed to exist and to be reached in a bounded number of iterations because the sets only grow (for "may" analyses) or shrink (for "must" analyses) monotonically over a finite universe of facts (a lattice with finite height).

Part (b): For Reaching Definitions (a forward, "may"/union analysis) the equations are:

Illustrative CFG (4 blocks): B1 (entry): d1: a=1; then B2: d2: b=2; then B3: d3: a=3 which branches back to B2 (loop) or falls through to B4 (exit). Edges: B1->B2, B2->B3, B3->B2, B3->B4.

The result shows d1 (a=1) reaches B2 but is killed before reaching B4 (since d3 overwrites a on every path into B4), while d2 (b=2) and d3 (a=3) both reach the loop exit B4 - exactly the information a compiler needs to detect that the initial value of a is dead by the time the loop exits, enabling dead-code/constant-propagation optimizations.

Part (a): Live Variable Analysis determines, at each program point, the set of variables whose currently held value may still be used along some path before being overwritten - a variable is "live" going into a block if some path from there reads it before redefining it. This is a backward analysis (information flows from a block's successors back into it) and a "may" analysis (a variable is live if it is live along any one outgoing path, so information sets are unioned). Available Expressions Analysis determines, at each program point, the set of expressions (e.g. a+b) that have already been computed on every path reaching that point and whose operands have not been reassigned since - it is a forward analysis and a "must" analysis (an expression is available only if it is available along every incoming path, so sets are intersected).

Part (b): Data flow equations:

Applications: live variable sets drive register allocation - a variable's live range (the span between definition and last use) determines which temporaries can share a physical register via graph coloring, and a variable that is dead immediately after assignment identifies dead code that can be deleted. Available expressions drive global common subexpression elimination - if an expression is available at a point, a later re-evaluation of the exact same expression can be replaced by a reference to the previously computed temporary, and also support loop-invariant code motion, hoisting an available, loop-independent expression out of a loop into its preheader.

Part (a): In an object-oriented language, scopes nest not only through blocks but through the class hierarchy: the global/file scope contains class declarations, each class scope contains its own members (fields, methods, nested/inner classes) and also implicitly re-exposes the members inherited from its superclass, and each method scope nested inside a class contains parameters and local variables, and additionally can see the enclosing class's fields/methods without qualification. The symbol table is therefore organized as a tree of scopes (a "scope tree") mirroring this nesting: each scope has its own hash table of symbol->attribute-record entries, plus a pointer to its parent scope (lexically enclosing scope) and, for a class, an additional pointer to its superclass's scope (which is not lexically enclosing but must still be searched for inherited members).

Part (b):

Lookup of an identifier used inside Derived.g() proceeds: (1) search g()'s own local scope (parameters/locals); (2) if not found, search the enclosing class scope Derived (its own fields/methods); (3) if still not found, follow the superclass link to Base's scope and search it (repeating up the inheritance chain for multi-level inheritance); (4) finally search the enclosing lexical scope, Global. The first matching entry found, in this order, is bound to the reference; if a name exists in both a class and its superclass, the class's own entry shadows (hides) the inherited one, which is how method overriding and field shadowing are resolved at compile time.

Part (a): Runtime storage for a procedural language is split into three regions: (1) a static area for global variables and constants, whose addresses are fixed at compile time; (2) a stack, which holds one activation record (also called a stack frame) per currently active procedure call, pushed on call and popped on return - this works because procedure activations are naturally last-in-first-out for languages without coroutines/closures that outlive their creator; and (3) a heap, for dynamically allocated data whose lifetime is not tied to any single procedure call (via malloc/new). Stack-based allocation is what makes recursion possible: every recursive call gets its own fresh activation record with its own locals, even though the code is the same.

Part (b):

On a call, the caller pushes actual parameter values, then a control link (pointer to the caller's activation record, used to restore the caller's frame on return) and, for languages with nested procedures, an access link (pointer to the activation record of the lexically enclosing procedure, used to resolve non-local variable references); the caller also saves its own machine status (return address, register contents) before transferring control. The callee then allocates space for its local variables and temporaries on top of this. Return value handling: the callee writes its result into the reserved return-value slot (or a dedicated register, per the calling convention) before executing the return sequence, which pops the callee's frame, restores the saved machine status and jumps to the return address recorded via the control link, leaving the stack pointer back where the caller left it. Parameter passing may be by value (copy actual into the parameter slot), by reference (copy the address instead), or by value-result, all of which only change what is written into the "Actual Parameters" area, not the overall frame structure.

Part (a): Mark-and-Sweep runs in two phases: starting from a set of roots (globals, stack references), it recursively marks every reachable heap object, then sweeps the whole heap linearly, reclaiming any unmarked (unreachable) object back to a free list. It never moves objects, so pointers stay valid, but it leaves the heap fragmented and its sweep cost is proportional to heap size regardless of how much garbage exists. A Copying Collector divides the heap into two equal semispaces; it allocates only in the active (from-space) semispace and, when that fills, traces all reachable objects from the roots (Cheney's breadth-first algorithm using a work queue in the new space itself) and copies them compactly into the other (to-space) semispace, updating every pointer to the new location; the old semispace is then discarded wholesale. This automatically compacts memory and makes allocation a trivial pointer bump, at the cost of needing double the address space and copying live (not dead) objects. Reference Counting stores, in every object, a count of how many pointers reference it; incrementing on each new reference and decrementing (freeing at zero) on each reference removal, reclamation is immediate and spread out rather than a stop-the-world pause, but it cannot reclaim cyclic garbage (two objects referencing each other with no external reference) and imposes overhead on every pointer assignment.

Part (b): The generational hypothesis observes empirically that "most objects die young" - the large majority of allocated objects become garbage very shortly after creation (e.g. short-lived temporaries), while a small minority survive for a long time. A generational collector exploits this by splitting the heap into a small young/nursery generation and one or more older generations; new objects are always allocated in the nursery, which is collected frequently using a cheap copying collector (a "minor GC") because it is small and most of its contents are dead, so scanning it is fast; objects that survive several minor collections are promoted (tenured) into the old generation, which is collected only rarely with a more expensive full/major GC. This gives large performance gains because it concentrates collection effort where garbage actually accumulates and avoids repeatedly re-scanning long-lived, mostly stable old-generation data. The one correctness subtlety is inter-generational pointers (an old object referencing a young one); collectors track these with a write barrier that records such pointers in a remembered set, so a minor GC can treat the remembered set as additional roots without having to scan the entire old generation.

Part (a): Every compiler phase detects and reports its own class of errors. The lexical analyzer flags illegal characters or malformed tokens (e.g. an unterminated string literal) and typically recovers by deleting the bad character(s) and resuming scanning. The syntax analyzer (parser) flags token sequences that do not match any grammar production (e.g. a missing semicolon or unbalanced parenthesis); since it has the most structural context it does the bulk of recovery work (panic mode / phrase-level / error productions, discussed below). The semantic analyzer flags type mismatches, undeclared identifiers, and redeclaration errors, typically continuing analysis by assuming an error type or inserting the identifier into the symbol table so that a single mistake does not trigger a cascade of false-positive errors downstream. The intermediate-code/optimizer and code-generator phases rarely see genuine source errors (a well-formed AST that passed semantic checks should always be generatable) but still validate invariants (e.g. detecting overflow of fixed-size constant folds) and report internal-compiler-errors if an invariant is violated. In all phases, good error reporting gives the line/column of the offending token, a human-readable message, and - crucially - continues compilation afterward (error recovery) so the user sees many real errors from one compile run instead of just the first.

Part (b):

Part (a): Peephole optimization examines the generated target/assembly code through a small, sliding "peephole" window (typically 2-4 consecutive instructions) and replaces the pattern currently in the window with a shorter or faster equivalent whenever a recognized pattern matches, repeating (sliding the window and re-matching) until no further pattern fires. It is applied as a late, machine-dependent cleanup pass after code generation. Common pattern families include: redundant load/store elimination (a value stored to memory and immediately reloaded into the same register); redundant push/pop elimination (a value pushed and immediately popped back into the same register with no intervening use); algebraic simplification (e.g. ADD reg, 0 or MUL reg, 1 removed entirely); strength reduction (replacing a multiply by a power of two with a shift); unreachable code elimination (code after an unconditional jump/return, before the next label, is dead); and jump-to-jump / branch chaining (a jump whose target is itself an unconditional jump is rewritten to jump straight to the final target, collapsing the chain). Because each rewrite is purely local, peephole optimization is cheap to run and is typically applied repeatedly (a fixed point) since one rewrite can expose a new pattern for the next.

Part (b): Unoptimized 8086-style assembly containing a redundant PUSH/POP pair, a useless add, and a jump chain:

Three independent transformations fired here: the PUSH/POP pair around AX was eliminated because AX's value was unchanged and never used from the stack; ADD CX,0 was deleted as an algebraic identity; and the two-instruction jump chain JMP L1 -> JMP L2 was collapsed into a single direct JMP L2, also making the now-unreferenced label L1 eligible for removal.

Part (a): Loop unrolling replicates the body of a loop several times inside a single iteration (reducing the trip count by the same factor), cutting the relative overhead of loop-control instructions (increment, compare, branch) per unit of real work and exposing more independent instructions that the processor or compiler scheduler can overlap/pipeline. Loop jamming (loop fusion) merges two or more adjacent loops that iterate over the same index range into a single loop body, amortizing one loop's control overhead across both computations and improving data locality when both loops touch the same array (fewer separate passes over memory, better cache reuse) - it is legal only when no data dependence crosses from the second original loop back into an earlier iteration of the first. Software pipelining restructures a loop so that instructions from several different logical iterations are issued in an overlapping fashion within one physical loop iteration (a steady-state "kernel" preceded by a short prologue and followed by an epilogue), keeping every functional unit of the pipelined processor busy every cycle instead of stalling on a chain of true dependencies within one iteration.

Part (b): Original inner loop of a matrix-multiply kernel (accumulating one output element c[i][j]):

Unrolled by a factor of 4, exposing four independent multiply-add chains per iteration (with a cleanup loop for any remainder when n is not a multiple of 4):

The loop-control overhead (increment and bounds check on k) is now paid once per four multiply-accumulate operations instead of once per one, and the four a[i][k+m]*b[k+m][j] products have no dependence on each other, so an out-of-order or VLIW/pipelined processor (or a vectorizing compiler) can issue and execute them concurrently instead of serializing on the single accumulator - the accumulation into sum can also be split into partial sums to break even that final dependency chain, a common further refinement.

Part (a): LLVM structures a compiler into three independent, replaceable stages connected by a common intermediate representation. The front end (e.g. Clang for C/C++/Objective-C, or any other language's front end) parses source into an AST and lowers it into LLVM IR - a strongly typed, target-independent, Static Single Assignment (SSA) form three-address-code-like representation with an infinite set of virtual registers, available in an in-memory form, a human-readable textual .ll form, and a compact binary bitcode .bc form. The optimizer (driven by the opt tool, or invoked automatically at a chosen -O level) runs a pipeline of analysis and transformation passes purely on LLVM IR, so the same optimizations work for every source language and every target. The back end (per-target, driven by llc or the integrated code generator) lowers optimized IR through instruction selection, register allocation, and instruction scheduling into target-specific assembly or object code. Because only the back end is target-specific (its machine description is generated from declarative TableGen files), retargeting LLVM to a new CPU only requires writing a new back end, while every front end and every IR-level optimization is reused unchanged - this front end/middle end/back end separation around a single IR is LLVM's central architectural idea.

Part (b): The Pass Manager schedules and runs an ordered pipeline of analysis and transformation passes over the IR. Passes are scoped at different granularities - function passes (operate on one function at a time, e.g. -mem2reg which promotes stack-allocated variables into SSA registers), loop passes (operate on individual natural loops, e.g. loop-invariant code motion), and module passes (operate across the whole translation unit, e.g. -inline, which needs the whole call graph). Newer LLVM versions replaced the legacy Pass Manager with the "new Pass Manager", which represents passes and their required/preserved analyses more explicitly, enabling better caching of analysis results across passes and finer control over pipeline ordering. Representative passes include -mem2reg (SSA construction), -gvn (Global Value Numbering, redundant computation elimination), -dce/-adce (dead code elimination), -inline (inline expansion), and -instcombine (peephole-style IR simplification); the optimization level flags (-O1, -O2, -O3) simply select a curated, ordered sequence of such passes.

Trace of a = b + c * 60 (assume a, b, c are declared real; the literal 60 is an integer constant, forcing a type coercion), through all six phases:

Part (a): SLR(1) construction. Augmented grammar (0: S'→S, 1: S→L=R, 2: S→R, 3: L→*R, 4: L→id, 5: R→L). FOLLOW sets (mutually recursive via L↔R): FOLLOW(S)={$}, FOLLOW(L)={=,$}, FOLLOW(R)={=,$}.

Part (b): Conflict check. State I2 = {S→L.=R, R→L.}. This state has a shift action on '=' (from S→L.=R) and, because FOLLOW(R) contains '=' (via R→L and L's own FOLLOW set), also a reduce R→L action on '=' — a genuine shift-reduce conflict at I2 on the symbol '='. Every other reduce state (I3, I5, I7, I8, I9) is reduce-only with no competing shift, so no other conflicts exist.

Conclusion: this grammar is not SLR(1). The conflict is an artifact of SLR's imprecision — it uses the single global FOLLOW(R) set, which is forced to include '=' because R can derive L and L precedes '=' in S→L=R, even though in the specific context "after an L reached directly under S", R→L should only reduce on lookahead $. A canonical LR(1) or LALR(1) parser carries the more precise per-item lookahead and parses this grammar without conflict.

Part (a): Item-set generation compared.

Part (b): Safe merging, demonstrated on S→AA, A→aA|b. The CLR(1) construction for this grammar (see the canonical LR(1) automaton worked out for this same grammar elsewhere in this bank) produces states I4={[A→b.,a],[A→b.,b]} and I7={[A→b.,$]} that share the identical core {A→b.} and differ only in lookahead; likewise I8={[A→aA.,a],[A→aA.,b]} and I9={[A→aA.,$]} share core {A→aA.}. LALR(1) merges each same-core pair: I4∪I7 → one state {[A→b., a/b/$]}, and I8∪I9 → {[A→aA., a/b/$]}.

Since I4/I7 and I8/I9 each contain only reduce items (no shift or other action to clash with), the merged states remain pure "reduce on {a,b,$}" states — merging introduces no new conflict here, so this grammar is LALR(1) with only 8 states instead of CLR(1)'s 10, at identical parsing power for this input language.

General risk: merging is only guaranteed conflict-free with respect to shift actions (a state's shift/goto transitions depend only on the core, so they are unaffected by merging). It can introduce new reduce-reduce conflicts when two states with the same core have two different complete items whose merged lookahead sets overlap (e.g. core {[A→γ.,a1],[B→δ.,a2]} in one state and {[A→γ.,a2],[B→δ.,a1]} in the other core-sharing state) — a case that never arises in this particular grammar but is the classical reason "some LR(1) grammars are not LALR(1)".

Part (a): Backpatching. Rather than fixing jump targets immediately (which is impossible for forward jumps whose target instruction doesn't exist yet), the code generator emits jump instructions with the target left blank and records each blank in a synthesized list (truelist/falselist) of instruction numbers still needing a target. makelist(i) creates a new one-element list {i}; merge(p1,p2) concatenates two lists; backpatch(list,target) fills every instruction in list with the address target once it becomes known. A marker non-terminal M → ε {M.instr = nextinstr} is inserted at the grammar position right where the next instruction's address must be captured (e.g. right after 'or'/'and').

Part (b): Backpatched 3AC for if (a<b or c<d) and e<f then x=1; using B→id1 relop id2 (emits a conditional-goto and a goto, both blank), B→B1 or M B2 (backpatch(B1.falselist,M.instr)), and B→B1 and M B2 (backpatch(B1.truelist,M.instr)):

Trace of how the jumps were resolved: (a<b).falselist={101} is backpatched to 102 (start of c<d, the other 'or' operand) once that code is generated. B1=(a<b or c<d) then has truelist={100,102} and falselist={103}. When "and e<f" is processed, B1.truelist={100,102} is backpatched to 104 (start of e<f) — so either a<b or c<d being true jumps straight to testing e<f. The whole expression's truelist={104} is backpatched to 106 (the x=1 statement) once it is generated, and falselist={103,105} both fall through to statement 107. Manually tracing all four truth combinations of the three relations confirms x=1 executes iff (a<b or c<d) and e<f is true.

Part (a): C++ uses largely manual memory management: new allocates an object on the heap and invokes its constructor, delete invokes the destructor and frees the storage; because there is no collector, C++ idiomatically relies on RAII (Resource Acquisition Is Initialization) and smart pointers (unique_ptr/shared_ptr) so that destructors deterministically release memory when an owning object's scope ends, converting manual deallocation into automatic, scope-driven deallocation. Java (and most managed OOP languages) instead allocates every object on a garbage-collected heap; the programmer never frees memory explicitly, and the runtime reclaims unreachable objects using one of the collection algorithms discussed in gc-15 (typically a generational collector). The tradeoff is predictability versus safety: C++ gives precise, immediate, low-overhead control at the cost of manual-memory bugs (leaks, dangling pointers, double frees), while Java trades some throughput and pause-time unpredictability for the elimination of that entire bug class.

Part (b):

Every object of a class with virtual methods carries a hidden pointer (vptr) as the first field of its header, set by the constructor to point at that class's single shared VTable - an array of function pointers with one fixed slot index per virtual method, shared by all instances of the class. A virtual call obj->f() compiles to obj->vptr[slot_of_f](): the slot index is resolved at compile time (from the static declaration order), but which function pointer sits at that slot is resolved at run time because each subclass's VTable stores its own overriding implementation at the same slot - this indirection is exactly dynamic dispatch. Non-virtual methods need no such indirection since their target is fixed at compile time. Java's JVM uses an analogous mechanism (a per-class method table plus interface method tables/"itables" for interface dispatch). Single inheritance keeps this a simple one-vptr, one-vtable, fixed-slot scheme; multiple inheritance requires an object to carry several vptrs (one per base-class sub-object) and the compiler to generate small "thunk" functions that adjust the this pointer before forwarding a call through the correct base's vtable.

Part (a): Code generation must target the actual instruction set, and RISC and CISC machines demand different strategies. RISC (Reduced Instruction Set Computer) machines have fixed-length instructions, a strict load-store architecture (only explicit load/store instructions touch memory; arithmetic operates only on registers), a large uniform register file, and simple, single-cycle-friendly instructions - the code generator must therefore explicitly schedule separate load instructions before any computation and explicitly manage a comparatively large but still finite register set, relying heavily on the compiler (not the hardware) for instruction scheduling and pipeline-hazard avoidance. CISC (Complex Instruction Set Computer) machines allow variable-length instructions, rich addressing modes, and operands that may reside directly in memory (memory-to-memory or memory-to-register operations in a single instruction), with many complex operations implemented internally as microcode - the code generator can therefore often emit fewer, denser instructions per source statement (e.g. one ADD [mem], reg instead of separate load/add/store), shifting complexity from the compiler into the hardware's microcode decoder.

Part (b): Instruction selection by tree rewriting represents each IR expression as an expression tree and matches it against a library of tiles - small subtree patterns, each pre-associated with a target instruction and a cost. A tiling covers the whole tree with non-overlapping tiles, and a maximal-munch / dynamic-programming algorithm chooses, at each node, the minimum-total-cost combination of tiles bottom-up (computing the cheapest tiling of each subtree once and reusing it, which is what makes it dynamic programming rather than brute-force search over all tilings). For x = a + b * c, the IR tree is Assign(x, Add(a, Mul(b, c))). Tiling proceeds bottom-up: the subtree Mul(b, c) is matched by a single "MUL-tile" (target instruction MUL Rt, b, c), producing a temporary result; that temporary then combines with a under an "ADD-tile" (ADD Rt2, a, Rt); finally a "STORE-tile" covers the outer Assign node (MOV x, Rt2). Because the two-instruction tiling (one MUL-tile, one ADD-tile, one STORE) has lower total cost than any decomposition using more, smaller tiles, the dynamic-programming selector picks exactly this combination, directly producing the instruction sequence MUL Rt,b,c ; ADD Rt2,a,Rt ; MOV x,Rt2.

Part (a): In a control flow graph, node d dominates node n (written d dom n) if every path from the entry node to n passes through d (every node trivially dominates itself). The dominance relation for a CFG is captured compactly as a dominator tree: each node's parent is its immediate dominator - the unique closest dominator that is itself dominated by all of the node's other dominators - so ancestry in the dominator tree exactly encodes the dominance relation. A natural loop is identified from a back edge n -> h, an edge whose target h dominates its source n (i.e. control flows from later in the traversal back "up" to a point that always executes first); h is the loop's unique header, and the loop body is h together with every node that can reach n without passing through h.

Part (b): To find all natural loops: (1) compute the dominator tree of the CFG (e.g. via the standard iterative dominator algorithm); (2) scan every CFG edge n -> h and classify it as a back edge whenever h dom n; (3) for each back edge, compute the loop body by a reverse-CFG traversal starting at n: initialize the body set to {h, n}, then repeatedly walk predecessors of nodes already in the set (excluding h itself, which is never re-entered) adding any newly reached predecessor, stopping when no new node is added - every node collected this way can reach n without passing through h, which is exactly the definition of loop membership. A loop pre-header is then constructed by inserting a new, empty basic block immediately before h and redirecting every edge that enters h from outside the loop to instead target this new block, which falls through to h; edges from inside the loop (including the back edge) still go directly to h. The pre-header gives optimizations like loop-invariant code motion a single, safe location - executed exactly once per loop entry - to hoist invariant computations into.

Part (a): Local Value Numbering (LVN) processes one basic block at a time, maintaining a hash table that maps a canonicalized (operator, operand value numbers) key to a value number. Each new variable/constant gets a fresh value number the first time it is seen; for a computation like t = x op y, LVN looks up (op, VN(x), VN(y)) (with operands of a commutative operator sorted into a canonical order so that a+b and b+a hash identically) - if that key already exists, the new computation is provably redundant (computes the same value) regardless of what the source variable/temporary names were, and can be replaced by a copy of the earlier result; otherwise a new value number is assigned. Because LVN only tracks facts within a single block, it misses redundancies whose two occurrences are in different blocks. Global Value Numbering (GVN) extends the same idea across the whole procedure/CFG, typically operating on SSA-form IR (where each variable has exactly one definition, making value identity easier to reason about across blocks and merge points via phi-functions); GVN therefore catches cross-block redundant computations that LVN, restricted to one block, structurally cannot see.

Part (b): Basic block with a redundant computation via commutative operands and a repeated expression:

Value-numbering trace: VN(a)=1, VN(b)=2. For t1 = a+b, key (+, 1, 2) is new -> assign VN(t1)=3. For t2 = b+a, canonicalizing commutative operands gives the same key (+, 1, 2) -> already present, so VN(t2)=3 too and t2 is redundant (equal to t1). For t3 = t1*t2, key (*, 3, 3) is new -> VN(t3)=4. For t4 = a+b, key (+, 1, 2) is already present -> VN(t4)=3, also redundant with t1. For t5 = t3+t4, key (+, 4, 3) is new -> VN(t5)=5.

Only one real addition (a+b) and one real multiplication are computed; the second and third additions are eliminated as provably redundant, without any control-flow or cross-block reasoning being required since all four statements live in one basic block.

Part (a): Interprocedural Optimization (IPO) is the family of optimizations that analyze and transform code across function/procedure boundaries rather than one function at a time, since purely intraprocedural (local) analysis must otherwise make worst-case conservative assumptions about what a called function might do to memory or globals. Typical interprocedural analyses include interprocedural constant propagation (propagating a constant actual argument into the callee's body), interprocedural alias/points-to analysis (determining whether two pointers in different functions can refer to the same memory), and call-graph construction (needed before any of the above, especially in the presence of function pointers/virtual calls). Inline expansion (inlining) is the most impactful and widely used IPO transformation: the compiler replaces a call site with a full copy of the callee's body, substituting actual arguments for formal parameters. This removes the call/return overhead (stack frame setup, parameter marshalling, jump) outright, and - more importantly - exposes the callee's statements to the caller's local optimizer, enabling further constant folding, dead code elimination, and common subexpression elimination across what used to be a call boundary, which is why inlining is often called an "enabling" optimization rather than just a speed optimization in itself.

Part (b):

Because of this tradeoff, real compilers use a cost/heuristic-based inliner: a callee is inlined only if its estimated size is below a threshold (or the call site is judged "hot" by profile data), and recursive or very large functions are excluded outright, balancing the execution-speed benefit against the code-size and instruction-cache cost.

Part (a): A generic target machine model used for code generation typically assumes a small set of general-purpose registers, a byte-addressable memory, and a simple load-store/two-address instruction set: MOV dst, src for moves/loads/stores, and two-address arithmetic instructions of the form OP dst, src meaning dst := dst OP src (the destination is also an implicit source operand). Each instruction has an assumed cost (often uniform, e.g. 1 unit, possibly higher if either operand is a memory location rather than a register), and the code generator's job is to produce a correct instruction sequence for an expression while minimizing register usage and total instruction cost - critically, computing which operand subtree needs more registers first (Sethi-Ullman labeling) and evaluating that subtree first, so that if only a limited number of registers is available, "spilling" an intermediate result to memory is avoided or minimized.

Part (b): For x = a + b * c using only two registers R0, R1: the expression tree is Add(a, Mul(b,c)). By Sethi-Ullman reasoning, the Mul(b,c) subtree needs one register to hold its result but must be evaluated first and kept live while a is subsequently loaded, so it is computed into R0 before touching a; if the multiplication were evaluated last instead, its two leaf operands plus the pending value of a would together need three registers simultaneously, forcing a spill. Evaluating the heavier (multiply) subtree first keeps everything within two registers:

Register allocation reasoning: R0 is dedicated to holding the (higher register-need) multiplication result across the two multiply instructions; R1 is only brought in afterward for a, once R0's value is stable, and is immediately combined with R0 - at no point are more than two live values needed simultaneously, so no spill to memory is required, and total code length is minimal (five instructions, one per leaf load/store plus one per operator) for this two-register model.

Part (a): Static program analysis examines source or intermediate code without executing it, computing conservative facts about all possible runs of the program. A linter (e.g. the original Unix lint for C, or modern tools such as Clang Static Analyzer, ESLint, or Pylint) is a lightweight static analysis tool built on top of a compiler front end that flags suspicious-but-not-illegal constructs the compiler itself would silently accept - unused variables, unreachable code, format-string mismatches, implicit narrowing conversions, possible null-pointer dereferences - typically using the same data-flow and type-checking machinery a compiler already builds (reaching definitions, live variables) but applying stricter/heuristic rules aimed at catching likely bugs and style problems rather than establishing outright language-legality. Because static analysis reasons about all possible executions at once, without running the program, it can find bugs on rarely-exercised paths that testing would miss, at the cost of possible false positives (over-conservative warnings on paths that can never actually occur).

Part (b): Abstract Interpretation formalizes this "approximate all runs at once" idea: instead of executing a program over its real (concrete) domain of values, it executes a sound approximation of the program over an abstract domain - e.g. the "sign" domain {negative, zero, positive, unknown} instead of exact integers, or an interval domain [low, high] instead of exact values - with abstract versions of every operator (e.g. positive + positive = positive) defined so that the abstract result always safely over-approximates every concrete result that could actually occur. Because the abstract domain is small and has finite (or well-controlled infinite) height, fixed-point iteration over it (exactly the same iterative technique used for data-flow analyses like reaching definitions) terminates and yields provably sound bounds - e.g. proving an array index can never go negative - which is precisely how compilers and static analyzers prove properties that would be undecidable to check exactly. Model Checking takes a complementary, more expensive approach: it represents a program's (or protocol's, or hardware design's) behavior as a finite-state transition system and exhaustively explores its reachable state space to verify that a temporal-logic property (e.g. "no reachable state has a race" / "every request is eventually followed by a response") holds on every path, or produces a concrete counterexample trace if it does not. In compiler verification specifically, model checking and abstract interpretation are used to prove an optimization is behavior-preserving (the optimized and unoptimized programs are observationally equivalent) or to verify safety properties of generated code, complementing testing by offering exhaustive, mathematically certain coverage of the state space rather than sampled coverage.