Here are much more detailed notes for all 10 topics:

1. DAG — Directed Acyclic Graph ★★

Definition
A Directed Acyclic Graph (DAG) is a data structure used in
compilers to represent the computations performed in a basic
block. It is a directed graph with no cycles. Each node in the DAG
represents a value or expression, and edges represent
dependencies.

Why DAG?
When we write code, the same sub-expression may appear
multiple times. Recomputing it wastes time. DAG detects these
repeated computations automatically.

Structure of DAG nodes

 Leaf nodes: Represent initial values of variables or
constants (identifiers and literals)
 Interior nodes: Represent operators (+, −, *, /)
 Labels: Each node has a label — the operator or value it
represents
 Attached identifiers: Variables whose current value is
represented by that node

Algorithm to Construct DAG

For each 3-address statement of the form x = y op z:

1. If there is no node for y, create a leaf node for y. Call it

node(y). Same for z.
2. Check if there already exists a node with operator op, left
child node(y), right child node(z).
3. If yes → reuse that node (common subexpression found). If
no → create a new interior node.
4. Remove x from the list of identifiers attached to its old node
(if any).
5. Attach x to the found/created node.
Numerical Example 1 — Standard DAG
Construction
Statements:
(1) a = b + c
(2) b = a - d
(3) c = b + c
(4) d = a - d

Step 1: a = b + c
Create leaf(b), leaf(c)
Create node n1 = (+, b, c)
Attach label: a → n1

Step 2: b = a - d
node(a) = n1 (already exists)
Create leaf(d)
Create node n2 = (-, n1, d)
Attach label: b → n2

Step 3: c = b + c
node(b) = n2, node(c) = leaf(c)
Create node n3 = (+, n2, leaf_c)
Attach label: c → n3

Step 4: d = a - d
node(a) = n1, node(d) = leaf(d)
Check: does node (-, n1, leaf_d) exist? YES! That is n2!
Attach label: d → n2

Final: Both b and d point to n2

→ (a - d) computed only once
→ Common subexpression eliminated!

Numerical Example 2 — DAG with Constants

Statements:
(1) t1 = 4 * i
(2) t2 = t1 + 8
(3) t3 = 4 * i ← same as t1
(4) t4 = t3 + 8 ← same as t2
(5) t5 = t2 - t4

Step 1: n1 = (*, 4, i) → t1
Step 2: n2 = (+, n1, 8) → t2
Step 3: (*, 4, i) = n1 already! → t3 points to n1
Step 4: (+, n1, 8) = n2 already! → t4 points to n2
Step 5: n3 = (-, n2, n2) → t5

Result: t5 = n2 - n2 = 0 → DEAD CODE detected!

The entire computation t1 through t5 is useless if t5 = 0 always.

Applications of DAG
 Common Subexpression Elimination (CSE): Reuse nodes
instead of recomputing
  Dead code elimination: Nodes with no parents (no one uses
the value) are dead
 Array bounds checking: Can be optimized using DAG
structure
 Code reordering: Topological sort of DAG gives valid
execution order
 Register allocation: Nodes with more uses should be kept in
registers longer

2. Peephole Optimization ★★
Definition
Peephole optimization is a local machine-code optimization
technique. A small sliding window (the "peephole") is moved over
the generated code. Instructions within the window are examined
and replaced with equivalent but more efficient sequences.

Characteristics
 Applied on target code (assembly or machine code), not on
IR
 Window is typically 2–5 instructions
 Multiple passes may be needed (one optimization may
enable another)
 Simple to implement, yet produces significant improvements

All Techniques in Detail

1. Redundant Instruction Elimination
Generated code:
MOV R0, a ; load a into R0
MOV a, R0 ; store R0 back to a ← useless!

After:
MOV R0, a ; second MOV eliminated

Why: If R0 was just loaded from a, storing it back to a changes nothing.

2. Constant Folding

Evaluate constant expressions at compile time.

Before: t=3*7+2
After: t = 23 (computed at compile time, no runtime cost)
3. Algebraic Simplification / Identities
x = x+0 →x=x → eliminated entirely
x = x-0 →x=x → eliminated
x = x*1 →x=x → eliminated
x = x*0 →x=0
x = x/1 →x=x → eliminated
x = 0 - y → x = -y (use unary minus)

4. Strength Reduction

Replace slow operations with faster equivalents.

x *2 → x+x (addition is faster than multiply)

x * 4 → x << 2 (left shift is faster)
x * 8 → x << 3
x / 2 → x >> 1 (right shift)
x ^2 → x*x (no exponent instruction needed)

5. Dead Code Elimination

DEBUG = false;
if (DEBUG) {
print("debug info"); ← never executes, remove it
}

6. Unreachable Code After Jump

goto L
x=y+z ← never reached! Delete it.
L: ...

7. Jump-to-Jump Optimization
Before:
goto L1
...
L1: goto L2

After:
goto L2 (bypass intermediate label)

8. Conditional Jump Optimization

Before:
if x < y goto L1
goto L2
L1: ...

After:
if x >= y goto L2 (invert condition, remove one jump)
L2: ...

Numerical Example — Full Sequence

Source: z = (a * 1) + (b + 0) + (4 * 2)

Step 1 — Algebraic simplification:

a*1=a
b+0=b
Step 2 — Constant folding:
4*2=8

Step 3 — Simplified expression:

z=a+b+8

Original: 3 operations + 2 loads = 5 instructions

After: 1 addition + 1 addition + 1 store = 3 instructions
Saved: 2 instructions per execution of this code

3. Storage Allocation Strategies ★

Definition
Storage allocation is the process of deciding how and when
memory is assigned to the names (variables, temporaries,
constants) in a program. This is handled cooperatively by the
compiler and the runtime system.

Key Concepts
 Binding time: When is memory assigned — compile time
(static) or runtime (dynamic)?
 Lifetime: How long does the memory remain allocated?
 Activation record (stack frame): A block of memory for one
invocation of a function

Structure of an Activation Record

High address
┌──────────────────────┐
│ Return value │ ← result returned to caller
├──────────────────────┤
│ Parameters │ ← actual arguments passed
├──────────────────────┤
│ Control link │ ← pointer to caller's activation record
├──────────────────────┤
│ Access link │ ← pointer to enclosing scope (for nested functions)
├──────────────────────┤
│ Saved machine │ ← saved registers, program counter
│ status │
├──────────────────────┤
│ Local variables │ ← variables declared in this function
├──────────────────────┤
│ Temporaries │ ← compiler-generated temp values
└──────────────────────┘
Low address
Strategy 1: Static Allocation
 All memory is allocated at compile time
 Sizes must be known statically
 Each variable has a fixed absolute address for the entire
program run
 No recursion — only one activation of each procedure can
exist
 No dynamic data structures of unknown size
 Example: FORTRAN 77, global variables, static in C

Example:
static int count = 0; ← lives at fixed address 0x4000 always
int arr[100]; ← size known → static allocation OK

void f() {
static int x = 5; ← retained between calls, fixed address
}

Strategy 2: Stack Allocation

 Memory allocated at runtime using a stack (LIFO)
 When a function is called → push activation record onto
stack
 When function returns → pop activation record
 Supports recursion (each call has its own frame)
 Does not support variable surviving beyond function return
 Used in C, C++, Java, Python

Numerical Example:
void A() { int x = 1; B(); }
void B() { int y = 2; C(); }
void C() { int z = 3; }

Call sequence: main → A → B → C

Stack at deepest point:

┌──────────────┐ ← top
│ C: z = 3 │
├──────────────┤
│ B: y = 2 │
├──────────────┤
│ A: x = 1 │
├──────────────┤
│ main frame │
└──────────────┘ ← bottom

C returns → its frame popped

B returns → its frame popped
A returns → its frame popped
Strategy 3: Heap Allocation
 Memory allocated and freed explicitly at runtime in any
order
 Not LIFO — any block can be freed at any time
 Used when lifetime cannot be determined at compile time
 Examples: malloc/free in C, new/delete in C++, garbage
collector in Java

Example:
int *p = malloc(sizeof(int) * n); ← n unknown at compile time
// use p...
free(p); ← explicitly released

Heap layout:
[used][free][used][free][used]
→ Fragmentation can occur over time
→ Garbage collector handles this in managed languages

Comparison Table
Feature Static Stack Heap

Compile
Allocation time Runtime (call) Runtime (explicit)
time

Automatic
Deallocation Never Manual or GC
(return)

Supports
No Yes Yes
recursion

Flexible size No No Yes

Speed Fastest Fast Slowest

Memory leak,
Risk None Stack overflow
fragmentation

4. Dead Code Elimination ★

Definition
Dead code elimination (DCE) is an optimization that removes code
which does not affect the program's output. It reduces binary
size, reduces load on the processor, and can enable further
optimizations.
Types of Dead Code
Type 1 — Unreachable Code

Code that can never be executed regardless of input.

int f() {
return 5;
x = 10; ← UNREACHABLE — after return
}

if (1 == 2) {
doSomething(); ← UNREACHABLE — condition always false
}

Type 2 — Dead Variables

A variable is dead at a point if its value is never used after that

point.

x = 5;
x = 10; ← first x=5 is dead (overwritten before use)
print(x); ← only x=10 matters

Type 3 — Useless Assignments

A variable is assigned but the function ends or returns before the

variable is read.

void f() {
int y = compute(); ← y computed...
return; ← ...but never used. Dead!
}

Liveness Analysis — The Theory Behind DCE

Definition: A variable v is live at program point p if there exists at
least one execution path from p to a use of v that has no
redefinition of v in between.

Data flow equations (Backward analysis):

IN[B] = USE[B] ∪ (OUT[B] − DEF[B])

OUT[B] = ∪ IN[S] for all successors S of B

Where:

 USE[B]: Variables used in B before any definition in B

 DEF[B]: Variables defined in B before any use in B
Numerical Example — Liveness Analysis
Basic Blocks:
B1: t1 = a * a
t2 = a * b
t3 = 2 * t2
t4 = t1 + t3
t5 = b * b
t6 = t4 + t5 ← computes (a+b)²

B2: print(t6)

USE[B1] = {a, b} ← uses a and b from outside

DEF[B1] = {t1,t2,t3,t4,t5,t6}
OUT[B1] = IN[B2] = {t6} ← only t6 is used in B2

IN[B1] = USE[B1] ∪ (OUT[B1] − DEF[B1])

= {a, b} ∪ ({t6} − {t1,t2,t3,t4,t5,t6})
= {a, b} ∪ {}
= {a, b}

Since t6 is live, t4 and t5 are needed (they compute t6).

Since t4 is needed, t1 and t3 are needed.
Since t3 is needed, t2 is needed.
→ No dead code here; all computations contribute.

Numerical Example — Practical DCE

Original code:
1. x = 10
2. y = x + 5 ← y is never read later
3. x = 20
4. z = x * 2
5. return z

Liveness at each point (reading backwards from return):

After 5: {}
After 4: {z}
After 3: {x}
After 2: {x} ← y not in live set! → stmt 2 is dead
After 1: {x} ← x=10 overwritten at stmt 3 before use → dead

After DCE:
3. x = 20
4. z = x * 2
5. return z

Removed: stmt 1 (x=10, dead) and stmt 2 (y=x+5, y never used)

5. Basic Blocks & Flow Graphs ★★

Basic Block — Definition
A basic block is a maximal sequence of consecutive 3-address
code instructions such that:
  Control can only enter at the first instruction
 Control can only leave at the last instruction
 There are no jumps into the middle, and no jumps out of the
middle

"Maximal" means we make each block as long as possible before

breaking it.

Algorithm — Finding Basic Blocks

Step 1: Find all leaders A leader is the first instruction of a basic
block.

 Rule 1: The very first instruction of the program is a leader

 Rule 2: Any instruction that is the target of a conditional or
unconditional goto is a leader
 Rule 3: Any instruction that immediately follows a
conditional or unconditional goto is a leader

Step 2: Form blocks Each leader starts a new basic block. The
block extends from the leader up to (but not including) the next
leader.

Detailed Numerical Example

3-Address Code:
1: prod = 0
2: i = 1
3: if i > 20 goto 12 ← conditional jump → stmt 12 is leader (Rule 2)
4: t1 = 4 * i ← follows jump → leader (Rule 3)
5: t2 = a[t1]
6: t3 = 4 * i
7: t4 = b[t3]
8: t5 = t2 * t4
9: prod = prod + t5
10: i = i + 1
11: goto 3 ← jump → stmt 3 is leader (Rule 2), stmt 12 is leader
(Rule 3)
12: return prod ← leader

Leaders: 1, 4, 12 (stmt 3 is already in a block starting at 1)

Wait — also stmt 3 is target of goto 3 at stmt 11 → stmt 3 is a leader too!

Revised leaders: 1, 3, 4, 12

Basic Blocks:
B1 = {1, 2} (from leader 1 up to leader 3)
B2 = {3} (from leader 3 up to leader 4)
B3 = {4,5,6,7,8,9,10,11} (from leader 4 up to leader 12)
B4 = {12} (from leader 12 to end)

Flow Graph Edges:

B1 → B2 (fall-through)
 B2 → B3 (if i ≤ 20, fall-through)
B2 → B4 (if i > 20, goto 12)
B3 → B2 (goto 3 at end of B3)

Flow Graph Construction

A flow graph G = (N, E, Entry) where:

 N = set of basic blocks (nodes)

 E = set of directed edges (control flow)
 Entry = the initial block

Edge rules:

 If block B ends with goto L, add edge B → block starting at L

 If block B ends with if ... goto L, add edges B → block at L (true
branch) and B → next block (false branch)
 If block B does not end with a jump, add edge B → next
sequential block

How a Program is Converted to a Flow Graph —

Steps
1. Write the source program
2. Generate 3-address intermediate code
3. Apply leader-finding rules to identify all leaders
4. Group instructions into basic blocks
5. Add directed edges based on jump targets and fall-through
6. Add ENTRY node (before first block) and EXIT node (after
blocks that end the program)
7. The resulting graph is the flow graph used for optimization

6. Symbol Table ★
Definition
A symbol table is a central data structure maintained by the
compiler that records information about every identifier (variable
name, function name, class name, etc.) encountered in the source
program.

When it is used
 Lexical analysis: Identifier tokens are entered
 Syntax analysis: Scope information added
  Semantic analysis: Type checking uses symbol table
 Code generation: Memory addresses retrieved from symbol
table

Information Stored Per Identifier

Attribute Description Example

Name The identifier string "count"

Variable, function,
Kind Variable
array, class

int, float,
Type Data type
char*

Global,
Scope Where it is visible
Local

Size Memory size in bytes 4 for int

Position in activation
Offset 12
record

No. of params For functions 3

Return type For functions float

Array
For arrays [10][20]
dimensions

Scope Management — Scope Stack

When the compiler enters a new scope (e.g., a function or block),
it creates a new symbol table for that scope. All symbol tables are
linked in a scope chain.

Source code:
int x = 5; ← global scope
void f(int y) { ← function scope
int z = x + y; ← block scope
}

Symbol Table Stack:

[Global Table]
x: int, offset 0
↓
[Function f Table]
y: int, param 1
z: int, offset 4
When looking up a name, the compiler searches from innermost
to outermost scope.

Implementation Methods
Method 1: Linear List (Ad-Hoc)
Structure: Array of records
[ {name, type, scope, offset}, {name, type, scope, offset}, ... ]

Search: Linear scan from beginning

Insert: Add at end

Time complexity:
Search: O(n)
Insert: O(1)

Example with 4 variables (a, b, c, d):

Lookup "d" → check a, check b, check c, check d → 4 comparisons
As n grows, becomes very slow

Method 2: Hash Table (Systematic)

Structure: Array of buckets + hash function

h(name) = (sum of ASCII codes of characters) % TABLE_SIZE

Example (TABLE_SIZE = 11):

h("a") = 97 % 11 = 9 → bucket 9
h("b") = 98 % 11 = 10 → bucket 10
h("ab") = (97+98) % 11 = 8 → bucket 8
h("int") = (105+110+116)%11 = 2 → bucket 2

Lookup "a":
Compute h("a") = 9 → go directly to bucket 9 → found!
Time: O(1) average

Collision (two names hash to same bucket):

Resolved by chaining (linked list at each bucket) or
open addressing (probe next empty bucket)

Numerical Example — Complete Symbol Table

Source:
int a;
float b[10];
char c;
void f(int x, int y) {
int temp;
}

Global Symbol Table:

Name | Kind | Type | Size | Offset
──────┼──────────┼────────┼──────┼───────
a | variable | int | 4 | 0
b | array | float | 40 | 4
c | variable | char | 1 | 44
f | function | void | - | -
Symbol Table for function f:
Name | Kind | Type | Size | Offset
──────┼──────────┼────────┼──────┼───────
x | param | int | 4 | 0
y | param | int | 4 | 4
temp | variable | int | 4 | 8

7. Three-Address Code ★★
Definition
Three-address code (3AC) is an intermediate representation (IR)
used between the front-end (parsing) and back-end (code
generation) of a compiler. Each instruction has at most one
operator on the right side and at most three addresses (operands
+ result). The compiler generates temporary variables (t1, t2, …)
to hold intermediate results.

General form: result = operand1 op operand2

Why Use 3AC?

 Machine-independent (not tied to any CPU)
 Easy to apply optimizations
 Easy to translate to machine code
 Explicit temporaries make data flow obvious

All Types of 3AC Instructions

1. Binary Arithmetic
t1 = a +b (addition)
t2 = a -b (subtraction)
t3 = a *b (multiplication)
t4 = a /b (division)
t5 = a %b (modulo)

2. Unary Operations
t1 = -a (unary minus)
t2 = not a (logical not)
t3 = int_to_float(a) (type conversion)

3. Copy Instructions
a=b (simple copy)

4. Indexed Copy (Array Access)

t1 = a[i] (read from array)
a[i] = t1 (write to array)
5. Address and Pointer Operations
t1 = &a (address of)
t2 = *t1 (dereference)
*t1 = b (store through pointer)

6. Jump Instructions
goto L (unconditional)
if a < b goto L (conditional)
if a goto L (boolean condition)

7. Procedure Calls
param a (push argument)
param b
call f, 2 (call f with 2 arguments)
t1 = call f, 2 (call f, store return value in t1)
return t1 (return value)

Representations of 3AC
Quadruples

Each instruction stored as a 4-tuple: (operator, argument1,

argument2, result)

Expression: a = -b * (c + d) + (-b) * (c + d)

3AC:
t1 = -b
t2 = c + d
t3 = t1 * t2
t4 = -b
t5 = c + d
t6 = t4 * t5
t7 = t3 + t6
a = t7

Quadruples table:
No. | op | arg1 | arg2 | result
────┼────────┼──────┼──────┼───────
0 | uminus | b | | t1
1 | + | c | d | t2
2 | * | t1 | t2 | t3
3 | uminus | b | | t4
4 | + | c | d | t5
5 | * | t4 | t5 | t6
6 | + | t3 | t6 | t7
7 | = | t7 | |a

Triples

Only 3 fields: (operator, argument1, argument2). Result is implicit

— it's referenced by statement number.

No. | op | arg1 | arg2

────┼────────┼──────┼──────
0 | uminus | b |
1 | + |c |d
2 | * | (0) | (1) ← (0) means result of stmt 0
3 | uminus | b |
4 | + |c |d
5 | * | (3) | (4)
6 | + | (2) | (5)
7 | = | a | (6)

Advantage: Saves space (no result field)

Disadvantage: Cannot reorder instructions (statement numbers are used as
references)

Indirect Triples

A separate list of pointers into the triples table. Reordering is

done by rearranging the pointer list, not the triples themselves.

Pointer List: Triples Table:

[0] → stmt 0 0: (uminus, b, -)
[1] → stmt 1 1: (+, c, d)
[2] → stmt 2 2: (*, (0), (1))
... ...

To reorder: swap entries in pointer list only.

Advantage: Supports instruction scheduling without changing references.

Comprehensive Numerical Example — Source to

3AC
Source: if (a > b+c) x = a*b; else x = c;
Step 1 — Translate b+c:
t1 = b + c

Step 2 — Translate condition a > t1:

if a > t1 goto L_true

Step 3 — False branch (else x = c):

x=c
goto L_end

Step 4 — True branch (x = a*b):

L_true:
t2 = a * b
x = t2

L_end:
(continue...)

Complete 3AC:
t1 =b+c
if a > t1 goto L_true
x =c
goto L_end
L_true:
 t2 =a*b
x = t2
L_end:

8. Issues in Designing a Code

Generator ★
Definition
The code generator is the last phase of the compiler. It translates
intermediate representation (3-address code) into target machine
code. The quality of generated code (speed, size) depends heavily
on the code generator's design.

Issue 1: Input to the Code Generator

 The input is assumed syntactically and semantically correct
IR
 Also receives the symbol table to look up name → memory
address mappings
 The IR may be 3AC (quadruples), syntax tree, or postfix
notation

Issue 2: Target Programs

Three forms of output:

1. Absolute machine code

→ Can be placed in a fixed memory location and run immediately
→ Fastest execution
→ Cannot be linked with other modules
Example: Small embedded programs

2. Relocatable machine code (object file)

→ Addresses are relative (can be placed anywhere in memory)
→ Must be linked with other .o files before execution
→ Most common (used by gcc)

3. Assembly language
→ Human-readable symbolic machine code
→ Must be assembled then linked
→ Useful for debugging

Issue 3: Memory Management

 Compiler works with the runtime to manage memory
 Static data: Global and static variables → fixed addresses in
data segment
  Stack data: Local variables, parameters → accessed via
offset from stack pointer (SP)
 Heap data: Dynamically allocated → addressed via pointers

Example: Accessing local variable x in function f:

If x is at offset 8 from SP:
Machine code: MOV R0, 8(SP) ; load x from stack
ADD R0, R0, #5
MOV 8(SP), R0 ; store back

Issue 4: Instruction Selection

The same 3AC statement can be implemented by multiple
instruction sequences. The code generator must pick the best
one.

3AC: a = b + c

Option A (simple, 3 instructions):

LOAD R1, b ; R1 = b
LOAD R2, c ; R2 = c
ADD R1, R1, R2 ; R1 = b+c
STORE R1, a ; a = R1

Option B (if b is already in R1 from previous computation):

LOAD R2, c ; R2 = c
ADD R1, R1, R2 ; R1 = b+c
STORE R1, a ; a = R1
→ 1 fewer instruction

Option C (if machine has ADD from memory instruction):

LOAD R1, b ; R1 = b
ADD R1, R1, c ; R1 = b+c (c loaded directly)
STORE R1, a
→ Also 3 instructions but avoids one register

The code generator must know the machine's instruction set to

make the right choice.

Issue 5: Register Allocation

Registers are the fastest memory (0 clock cycles to access).
Memory accesses are slow (100+ cycles). Keeping values in
registers as long as possible is critical.

Sub-problems:

 Register allocation: Decide which variables/temporaries to

keep in a register
 Register assignment: Decide which specific register to use
Key insight: If a value in register R is needed later, and R is
needed for a new computation, the old value must be "spilled" to
memory. Minimizing spills is the goal.

Numerical Example — Register Usage:

3AC:
t1 = a+b
t2 = c+d
t3 = t1 * t2
t4 = t3 - e
t5 = t4 + f

With 2 registers R0, R1:

LOAD R0, a
ADD R0, R0, b ; R0 = t1
LOAD R1, c
ADD R1, R1, d ; R1 = t2
MUL R0, R0, R1 ; R0 = t3 (R1 now free)
SUB R0, R0, e ; R0 = t4
ADD R0, R0, f ; R0 = t5
STORE R0, t5

→ Managed with only 2 registers! No spills needed with right ordering.

Issue 6: Evaluation Order

The order in which expressions are evaluated can affect how
many registers are needed.

Expression: (a + b) * (c - d) + (e * f)

Order 1 (good):
t1 = a + b
t2 = c - d
t3 = t1 * t2 ← t1, t2 both available → 2 registers max
t4 = e * f
t5 = t3 + t4

Order 2 (needs more registers):

t1 = a + b
t2 = e * f ← keep t1 alive while computing t2
t3 = c - d ← now keep t1, t2 alive → 3 registers needed
t4 = t1 * t3
t5 = t4 + t2

→ Order 1 is better (needs fewer registers)

The Sethi-Ullman algorithm computes the optimal evaluation

order for expression trees.
9. Error Detection and Recovery ★
Definition
No real-world program is error-free during development. A
compiler must:

1. Detect errors accurately and precisely

2. Report them with helpful messages (line number, what went
wrong, what was expected)
3. Recover from the error and continue processing to find more
errors
4. Not report too many "spurious" errors that are caused by
earlier errors

Categories of Errors
1. Lexical Errors

Detected by the scanner (lexer). Errors in the formation of

tokens.

Examples:
3.14.15 ← invalid floating-point literal
"unterminated ← string not closed
@x ← @ is not a valid character
0x1G2 ← G is not a hex digit

2. Syntax Errors

Detected by the parser. Token sequence doesn't match grammar

rules.

Examples:
if x > 5 then { ← 'then' not valid in C/Java
int a = ; ← missing expression
a = (b + c; ← missing closing parenthesis
int int x; ← two type specifiers

3. Semantic Errors

Detected by semantic analysis. Grammar is correct but meaning

is wrong.

Examples:
int x = "hello"; ← type mismatch
int arr[10]; arr[15] = 5; ← index out of bounds (some compilers catch)
undeclaredVar = 5; ← variable not declared
int f(int x); f(1, 2); ← wrong number of arguments
return 5; (in void function) ← invalid return type
4. Logical Errors

Not detected by the compiler. The program runs but produces

wrong output.

Examples:
if (x = 5) instead of if (x == 5) ← assignment in condition
for (i=1; i<n; i--) ← infinite loop (i goes down)
area = length + width instead of length * width

Error Recovery Strategies in Detail

1. Panic Mode Recovery

Most widely used. When an error is detected, the parser discards

input tokens one at a time until it finds one of a set of designated
synchronizing tokens.

Synchronizing tokens are usually: ; (end of statement), } (end of

block), end, begin

Example:
Input: int a = ; int b = 5; float c = 3.14;

Parser at "=": expects expression, finds ";"

Error message: "Expected expression after '='"
Panic mode: discard ";" (the bad token)
Resume at: int b = 5; ✓ parsed
Resume at: float c = 3.14; ✓ parsed

Result: 2 out of 3 declarations parsed correctly despite error

Advantage: Simple, always terminates Disadvantage: May skip

large portions of valid code

2. Phrase-Level Recovery

Make a small local correction at the point of error — insert,

delete, or replace a single token.

Example 1 — Missing semicolon:

Input: int a = 5 int b = 3;
Error: Expected ';' before 'int'
Fix: Insert ';' after 5
Result: int a = 5; int b = 3; ✓

Example 2 — Extra token:

Input: int int x = 5;
Error: Unexpected 'int'
Fix: Delete the second 'int'
Result: int x = 5; ✓

Example 3 — Wrong token:

 Input: x := 5; (Pascal-style in a C compiler)
Error: Expected '=' found ':='
Fix: Replace ':=' with '='
Result: x = 5; ✓

3. Error Productions

Add special grammar rules that explicitly recognize common

mistakes.

Standard rule:
assignment → id '=' expr ';'

Error production added:

assignment → id '=' expr (missing semicolon — common mistake)

When the error production matches:

→ Parser recognizes it as the "missing semicolon" error
→ Reports: "Warning: missing ';' at end of statement"
→ Inserts semicolon and continues normally

Advantage: Very clean recovery for known common errors

Disadvantage: Must anticipate all common errors in advance

4. Global Correction

Find the minimal sequence of insertions, deletions, and

replacements to transform the erroneous input into a
syntactically valid program.

Example:
Erroneous input: "int x 5;"
Valid program: "int x = 5;" (insert '=')

Cost = 1 edit (one insertion)

This is globally optimal for this error.

Advantage: Best possible error correction Disadvantage: O(n³)

time complexity — too slow for large programs. Not used in
practice.

Numerical Example — Parser Error Recovery in

Detail
Source with errors:
{
int a = 5
int b = a +;
c = 10;
}

Line 2: int a = 5 — missing ';'

Phrase-level: insert ';' → int a = 5; ✓
Line 3: int b = a +; — missing right operand of '+'
Panic mode: error at ';', discard ';'
Try to recover to next statement
Message: "Expected expression after '+'"
b is not properly initialized — mark as undefined for rest

Line 4: c = 10; — c not declared

Semantic error: "c used without declaration"
Continue parsing normally

Total: 3 errors detected in one compile pass.

Without recovery, compiler would stop at first error.

10. Data Flow Analysis & Loop

Optimization ★★
Data Flow Analysis — Definition
Data flow analysis is a compile-time technique to collect
information about how data values are defined and used as they
flow through a program's control flow graph. This information
enables global optimizations — optimizations that span multiple
basic blocks.

The Framework
Every data flow analysis problem has:

 A direction (forward or backward through CFG)

 A domain (set of facts being tracked)
 A meet operator (∩ intersection or ∪ union — combines info
from multiple paths)
 Transfer functions (how each basic block transforms the
information)
 Boundary conditions (initial values at entry or exit)

Problem 1: Reaching Definitions

Question: At each program point, which variable definitions might
have "reached" that point (i.e., the value assigned has not been
overwritten)?

Direction: Forward (from entry to exit)

Equations:

OUT[B] = GEN[B] ∪ (IN[B] − KILL[B])

IN[B] = ∪ OUT[P] for all predecessors P of B
IN[Entry] = {}

Where:

 GEN[B]: Definitions generated inside B that reach the end of

B
 KILL[B]: Definitions from outside B that are killed (the same
variable is redefined in B)

Numerical Example:

Program:
B1: d1: x = 5 d2: y = x
B2: d3: x = 10 d4: z = x + y ← d3 kills d1 (redefines x)
B3: d5: y = z ← d5 kills d2 (redefines y)

Control flow: B1 → B2 → B3

GEN[B1] = {d1, d2} KILL[B1] = {d3, d5}

GEN[B2] = {d3, d4} KILL[B2] = {d1, d2} (d3 redefines x; kills d1. d4 uses
y,x)
GEN[B3] = {d5} KILL[B3] = {d2}

Initialize: OUT[B1] = OUT[B2] = OUT[B3] = {}

Iteration 1:
IN[B1] = {} (entry)
OUT[B1] = {d1,d2} ∪ ({} − {d3,d5}) = {d1, d2}

IN[B2] = OUT[B1] = {d1, d2}

OUT[B2] = {d3,d4} ∪ ({d1,d2} − {d1,d2}) = {d3, d4}

IN[B3] = OUT[B2] = {d3, d4}

OUT[B3] = {d5} ∪ ({d3,d4} − {d2}) = {d3, d4, d5}

Result:
At start of B3: definitions d3 (x=10) and d4 (z=x+y) reach here.
d1 (x=5) does NOT reach B3 → x=5 is a dead assignment.

Problem 2: Live Variable Analysis

Question: At each program point, which variables might be used
before being redefined (i.e., their current value matters)?

Direction: Backward (from exit to entry)

Equations:

IN[B] = USE[B] ∪ (OUT[B] − DEF[B])

OUT[B] = ∪ IN[S] for all successors S of B
OUT[Exit] = {}

Where:
  USE[B]: Variables used in B before any definition in B
 DEF[B]: Variables defined in B before any use in B

Numerical Example:

B1: a = 1
b=2
B2: c = a + b
d=c*2
B3: print(d)

Control flow: B1 → B2 → B3

USE[B1] = {} DEF[B1] = {a, b}

USE[B2] = {a, b} DEF[B2] = {c, d}
USE[B3] = {d} DEF[B3] = {}

Initialize: IN[B1]=IN[B2]=IN[B3]={}, OUT[B3]={}

Backward iteration:
OUT[B3] = {} (exit)
IN[B3] = USE[B3] ∪ (OUT[B3] − DEF[B3]) = {d} ∪ {} = {d}

OUT[B2] = IN[B3] = {d}

IN[B2] = {a,b} ∪ ({d} − {c,d}) = {a,b} ∪ {} = {a, b}

OUT[B1] = IN[B2] = {a, b}

IN[B1] = {} ∪ ({a,b} − {a,b}) = {}

Interpretation:
Before B1: no variables are live (nothing from outside needed)
After B1 (before B2): a and b are live
After B2 (before B3): d is live
→ a and b are needed (live); all assignments are necessary
→ c is defined in B2 but only used to compute d; keep it

Loop Optimization (Unit 5 — Sources of

Optimization)
Loops are the primary target for optimization because a loop
body executes n times — any improvement is multiplied n times.

Three Main Loop Optimizations

1. Loop-Invariant Code Motion (Code Motion)

A computation is loop-invariant if its operands are not modified

anywhere in the loop. Such computations can be moved before
the loop into a pre-header block.

How to detect loop-invariant code: An instruction t = x op y is loop-

invariant if, for each operand (x and y):
  It is a constant, OR
 All definitions of x that reach this instruction are outside the
loop, OR
 There is exactly one definition of x inside the loop and it is
itself loop-invariant

Example 1 — Simple code motion:

for (i = 0; i < n; i++) {
limit = max - 2; ← max and 2 don't change in loop
arr[i] = limit * i;
}

After code motion:

limit = max - 2; ← moved to pre-header (computed once)
for (i = 0; i < n; i++) {
arr[i] = limit * i;
}

Savings: n-1 subtractions eliminated

Example 2 — Nested loops:

for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
t = a[i] * b[i]; ← depends only on i, not j
c[i][j] = t + j;
}
}

After code motion (move t out of inner loop):

for (i = 0; i < m; i++) {
t = a[i] * b[i]; ← computed once per i
for (j = 0; j < n; j++) {
c[i][j] = t + j;
}
}

Savings: n-1 multiplications saved per outer iteration → total (m*n - m) mults
saved

2. Strength Reduction

An induction variable is a variable that changes by a fixed

constant each iteration. Strength reduction replaces expensive
operations (multiplication) involving induction variables with
cheaper operations (addition).

Example:
for (i = 0; i < n; i++) {
t = i * 4; ← i*4 = multiplication every iteration
a[t] = 0;
}

Introduce new variable s = i * 4:

s = 0; ← initialize: when i=0, s=4*0=0
for (i = 0; i < n; i++) {
a[s] = 0;
s = s + 4; ← add 4 each iteration instead of multiply
 i = i + 1;
}

Before: n multiplications
After: 0 multiplications, n additions (additions are much faster)

3. Induction Variable Elimination

After strength reduction, if an induction variable is only used in

the loop condition and nowhere else, it can be replaced by the
strength-reduced variable.

Before strength reduction:

i = 0;
while (i < n) {
arr[i * 4] = 0;
i++;
}

After strength reduction (introduce s = 4*i):

i = 0;
s = 0;
while (i < n) {
arr[s] = 0;
s = s + 4;
i++;
}

Now i is only used in the condition (i < n).

Rewrite condition in terms of s:
i < n → s < 4*n

After induction variable elimination (remove i):

s = 0;
while (s < 4*n) { ← compute 4*n once before loop
arr[s] = 0;
s = s + 4;
}

Final result: i eliminated entirely.

Before: n multiplications (i*4), n increments (i++), n compares (i<n)
After: 0 multiplications, n additions (s+=4), n compares (s<4n)

Data Flow Analysis — Structure of Flow Graph for

Loops
Pre-header ← invariant code is moved here
│
▼
Header ◄──────────────┐
│ │
▼ │
Body (B1) │
│ │
▼ │
Body (B2) ───────────────┘ (back edge)
│
 ▼
Exit

The back edge (from body back to header) is what defines a loop.
All nodes from which the header is reachable via forward edges
form the loop body.

Summary of Optimizations and Which Data Flow

Analysis Enables Them
Optimization Data Flow Analysis Used

Common Subexpression
Available Expressions
Elimination

Dead Code Elimination Live Variable Analysis

Constant Propagation Reaching Definitions

Loop-Invariant detection +
Code Motion
Dominator analysis

Register Allocation Live Variable Analysis

Induction Variable Strength Reduction + Reaching

Elimination Definitions