🌺Compiler Design

1. Introduction to Various Phases of a Compiler

Main aim of a compiler = convert HLL → LLL (High Level Language to Low Level Language).

flowchart TD
    HLL[HLL Source Code] --> PP[Pre-processor]
    PP -->|Pure HLL| C[Compiler]
    C -->|Assembly Language| A[Assembler]
    A -->|Machine Code / Relocatable| LL[Loader / Linker]
    LL --> EXE[Executable Code / Absolute Machine Code]

Assembler is dependent on the platform.

Pre-processor tasks

• File inclusion — replacing #include with the relevant file content.
• Macro expansion — expanding #define constants and small functions.

Linker

• Combines various pieces of code and source codes to obtain an executable code.
• Combines object modules.
• Input: Machine code → Output: Executable code.

Loader

• Part of the OS responsible for loading programs into memory.
• Input: Executable code generated by the Linker.

---

2. Phases of a Compiler

flowchart TD
    LA[Lexical Analysis] -->|Stream of tokens| SA[Syntax Analysis]
    SA -->|Parse tree| SEM[Semantic Analysis]
    SEM -->|Semantically verified parse tree| ICG[Intermediate Code Generator]
    ICG -->|3-Address Code| CO[Code Optimisation]
    CO --> TCG[Target Code Generation]
    TCG --> ASM[Assembly]

    STM[Symbol Table Manager] --- LA
    STM --- SA
    STM --- SEM
    STM --- ICG
    STM --- CO
    STM --- TCG

    EH[Error Handler] --- LA
    EH --- SA
    EH --- SEM
    EH --- ICG
    EH --- CO
    EH --- TCG

Worked Example: x = a + b * c

1. Lexical Analyzer — identifies identifiers/tokens using regular expressions called patterns.
   $id=id+id\ast id,\text{pattern: }l(l+d{)}^{\ast }$

2. Syntax Analyzer — uses a Context Free Grammar (CFG):

Rule	Meaning
$S\to id=E;$	Statement can be identifier = expression;
$E\to E+T\mid T$	Expression can be expr + term or term
$T\to T\ast F\mid F$	Term can be term * factor or factor
$F\to id$	Factor is an identifier

Parse Tree:

graph TD
  S --> id1[id]
  S --> Eq[=]
  S --> E1[E]
  E1 --> E2[E]
  E1 --> plus[+]
  E1 --> T1[T]
  E2 --> T2[T] --> F1[F] --> ida[id a]
  T1 --> T3[T] --> F2[F] --> idb[id b]
  T1 --> star[*]
  T1 --> F3[F] --> idc[id c]

3. Semantic Analyzer — checks whether the parse tree is meaningful or not.
   → Output: Parse tree, semantically verified.

4. Intermediate Code Generator — 3-address code is most common. In every statement, only 3 addresses are present.

   t1 = b * c
   t2 = a + t1
   x  = t2
   

5. Code Optimisation

   t1 = b * c
   x  = a + t1
   

6. Target Code Generator

   MUL R1, R2      ; a → R0
   ADD R0, R2      ; b → R1
   MOV R2, X       ; c → R2
   

---

3. Symbol Table

Definition

The symbol table is an important data structure created and maintained by compilers to store information about occurrences of various entities — variable names, function names, objects, classes, interfaces, etc.

• Information is collected during the analysis phase and used during the synthesis phase.

Usage of Symbol Table in Various Phases

Phase	Usage
Lexical Analysis	Creates new entries for each new identifier.
Syntax Analysis	Adds info regarding attributes — type, scope, dimension, line of reference/use.
Semantic Analysis	Uses the available information to check semantics; is updated.
Intermediate Code Generation	Info in symbol table helps add temporary variable info (type etc.)
Code Optimisation	Info in symbol table used for optimisation, considering address & aliased variable info.
Target Code Generation	Generates code using the address info of identifiers.

Symbol Table Entries

1. Name
2. Type
3. Size
4. Dimension
5. Line of declaration
6. Line of usage (linked list)
7. Address

Warning

• All attributes are not of the same size.
• Size of symbol table should be dynamic, to allow increase in size during compilation phase.

Operations on the Symbol Table

1. Non-block structured language

• Contains only one instance of variable declaration; scope is throughout the program.
• Operations: Insert, Lookup.

2. Block structured language (C++, Java)

• Variables may be re-declared; scope is only within that particular block.
• Operations: Insert, Set, Lookup, Reset (changing scope of a variable).

GATE 2012

Access time of a table is logarithmic if it is implemented by —
a) Linear list $O(n)$
b) Search Tree $O({\log }_{k}n)$ ✅
c) Hash Table $O(1)$
d) NOTA

---

4. Lexical Analyzer

• The only phase that reads the input character by character.
• Ignores comments.
• Eliminates white spaces.

Pipeline: Input preprocessing (removes comments) → Tokenization (generates tokens) → Token classification (identifier/keyword/operator) → Token validation (checks if a token adheres to rules) → Output generation.

Example: int max(x,y) { int x,y; /* find max of x & y */ return(x>=y?x:y); } → 25 tokens present.

Example: printf("%d Hai", &x); → 8 tokens.

Syntax Analyzer is also called the parser.

---

5. Grammar

Ambiguity

If a grammar has more than one derivation tree (parse tree) for the same string, the grammar is ambiguous.
Ambiguity problems are undecidable.

Ambiguous grammars need to be converted to unambiguous grammars to be used by parsers, by resolving:

1. Associativity — to overcome associativity, grammar should be left/right recursive.
2. Precedence — highest precedence operator should be as far from the start symbol as possible.

Eliminating Left Recursion

Grammars should not be left recursive because Top-Down parsers can’t process left recursive grammars.

$A\to A\alpha \mid \beta ⟹A\to \beta A^{\prime },A^{\prime }\to ϵ\mid \alpha A^{\prime }$

Eliminating Non-determinism (Left Factoring)

Grammars should not be non-deterministic. Non-deterministic grammars are converted into deterministic ones using common prefix (left factoring).

Example:
$S\to bSSaaS\mid bSSaSb\mid bSb\mid a$
$\Downarrow$
$S\to bS{S}^{\prime }\mid a,S^{\prime }\to \underline{S}aaS\mid \underline{Sa}Sb\mid b\mid ϵ$
$\Downarrow$
$S\to bS{S}^{\prime }\mid a,S^{\prime }\to Sa{S}^{\prime \prime }\mid b,S^{\prime \prime }\to aS\mid Sb$

Non-deterministic because common prefix exists for productions of the same variable.

Elimination of non-determinism does not eliminate ambiguity.

---

6. Parsers — Overview

flowchart TD
    P[Parsers ambiguity ✗] --> TDP[Top Down Parsers TDP]
    P --> BUP[Bottom Up Parsers BUP - shift reduce SR parser]

    TDP --> TDPB[TDP with backtracking]
    TDP --> TDPWB["TDP without backtracking (left recursion ✗, non-determinism ✗)"]

    TDPB --> BF[Brute force method]

    TDPWB --> RD[Recursive Descent]
    TDPWB --> NRD["Non Recursive Descent LL(1)"]

    BUP --> OPP["Operator Precedence Parser (ambiguous grammars allowed)"]
    BUP --> LR[LR Parser - which to reduce]

    LR --> LR0[LR0]
    LR --> SLR1[SLR1]
    LR --> LALR1[LALR1]
    LR --> CLR1[CLR1 / Canonical LR]

---

7. LL(1) Parser / Non-Recursive Descent

L L (1)

• L → Input is scanned Left to Right.
• L → Leftmost Derivation is used.
• (1) → Number of look-aheads (characters we can see when making a decision).

flowchart LR
    Buf["Input Buffer"] --> Parser["LL(1) Parser (Parsing algorithm)"]
    Stack[Stack] --> Parser
    Table["LL(1) Parsing Table (Data structure constructed using grammar)"] --> Parser

For LL(1) parsing table — FIRST and FOLLOW functions are used so the parser can apply the correct production rule at the correct position.

FIRST( )

$First(\alpha )$ is the set of terminal symbols that begin the strings derived from $\alpha$.

Example:
$A\to abc\mid def\mid ghi\Rightarrow First(A)=\{a,d,g\}$

Rules for calculating FIRST

• Rule 01: For production $X\to ϵ$: $First(X)=\{ϵ\}$
• Rule 02: For any terminal $a$: $First(a)=\{a\}$
• Rule 03: For production $X\to Y_1{Y}_2{Y}_3$:
  $First(X)=First(Y_1)\text{if }ϵ\notin First(Y_1)$
  $First(X)=\{First(Y_1)-ϵ\}\cup First(Y_2{Y}_3)\text{if }ϵ\in First(Y_1)$

Example:

S → aABCD        First(S) = a
A → b            First(A) = b
B → C            First(B) = c
C → d            First(C) = d
D → e            First(D) = e

FOLLOW( )

$Follow(A)$ is the set of terminal symbols that appear immediately to the right of $A$.

FOLLOW cannot contain $ϵ$.

Rules for calculating FOLLOW:

• Rule 01: For the start symbol $S$: place $ in $Follow(S)$.
• Rule 02: For production $A\to \alpha B$: $Follow(B)=Follow(A)$.
• Rule 03: For production $A\to \alpha B\beta$:
  $Follow(B)=First(\beta )\text{if }ϵ\notin First(\beta )$
  $Follow(B)=\{First(\beta )-ϵ\}\cup Follow(A)\text{if }ϵ\in First(\beta )$

---

Worked Question — FIRST & FOLLOW

Grammar:
$S\to aBDh,B\to cC,C\to bC\mid ϵ,D\to EF,E\to g\mid ϵ,F\to f\mid ϵ$

Symbol	FIRST	FOLLOW
S	$\{a\}$	\{\}$
B	$\{c\}$	$\{g,f,h\}$
C	$\{b,ϵ\}$	$\{g,f,h\}$
D	$\{g,f,ϵ\}$	$\{h\}$
E	$\{g,ϵ\}$	$\{f,h\}$
F	$\{f,ϵ\}$	$\{h\}$

More Examples of FIRST/FOLLOW

(a)

S → A
A → aB | Ad     (left recursive)
B → b
C → g

After eliminating left recursion:

S → A
A → aBA'
A' → dA' | ε
B → b
C → g

	FIRST	FOLLOW
S	{a}	{$}
A	{a}	{$}
A’	{d, ε}	{$}
B	{b}	{d, $}
C	{g}	N/A

(b)

S → (L) | a
L → SL'
L' → , SL' | ε

	FIRST	FOLLOW
S	{(, a}	{), $}
L	{(, a}	{)}
L’	{,, ε}	{)}

(c)

S → AaAb | BbBa
A → ε
B → ε

FIRST(S) = {a,b}, FOLLOW(S) = {$}, FOLLOW(A) = {a,b}, FOLLOW(B) = {a,b}

(d)

S → Bb | Cd
B → aB | ε
C → cC | ε

FIRST(S)={a,b,c,d}, FOLLOW(S)={$}, FOLLOW(B)={b}, FOLLOW(C)={d}

(e) — Classic Expression Grammar

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → id | ( E )

	FIRST	FOLLOW
E	{id, (}	{$, )}
E’	{+, ε}	{$, )}
T	{id, (}	{+, ), $}
T’	{*, ε}	{+, ), $}
F	{id, (}	{*, +, ), $}

(f)

S → ACB | CbB | Ba
A → da | BC
B → g | ε
C → h | ε

FIRST(S) = {d,g,h,ε,b,a}, FOLLOW(S) = {$}
FIRST(A) = {d,g,h,ε}, FOLLOW(A) = {h,g,$}
FIRST(B) = {g,ε}, FOLLOW(B) = {$,a,h,g}
FIRST(C) = {h,ε}, FOLLOW(C) = {g,$,b}

---

8. Construction of LL(1) Parsing Table

• Variables are in columns (vertical).
• Terminals are in rows (horizontal).
• Each production should be placed in:
  • Row of the left-hand-side variable.
  • Column in FIRST of the right-hand-side. (For $ϵ$-productions, use FOLLOW of LHS.)

Example: Expression Grammar

Production	First	Follow
$E\to T{E}^{\prime }$	{id, (}	{$, )}
$E^{\prime }\to +T{E}^{\prime }\mid ϵ$	{+, ε}	{$, )}
$T\to F{T}^{\prime }$	{id, (}	{+, ), $}
$T^{\prime }\to \ast F{T}^{\prime }\mid ϵ$	{*, ε}	{+, ), $}
$F\to id\mid (E)$	{id, (}	{*, +, ), $}

LL(1) Parsing Table:

	id	+	*	(	)	$
E	$E\to T{E}^{\prime }$			$E\to T{E}^{\prime }$
E’		$E^{\prime }\to +T{E}^{\prime }$			$E^{\prime }\to ϵ$	$E^{\prime }\to ϵ$
T	$T\to F{T}^{\prime }$			$T\to F{T}^{\prime }$
T’		$T^{\prime }\to ϵ$	$T^{\prime }\to \ast F{T}^{\prime }$		$T^{\prime }\to ϵ$	$T^{\prime }\to ϵ$
F	$F\to id$			$F\to (E)$

Every cell has only one entry ⇒ the grammar can be parsed by an LL(1) parser.

Simple Examples

$S\to (S)\mid ϵ$

	(	)	$
S	$S\to (S)$	$S\to ϵ$	$S\to ϵ$

$S\to AaAb\mid BbBa,A\to ϵ,B\to ϵ$

	a	b	$
S	$S\to AaAb$	$S\to BbBa$
A	$A\to ϵ$	$A\to ϵ$
B	$B\to ϵ$	$B\to ϵ$

Grammars which are Left Recursive & Non-Deterministic cannot be used for LL(1) parsing.

---

9. Check Whether Grammars are LL(1)

Q1) $S\to aSbS\mid bSaS\mid ϵ$
$First(S)=\{a,b\},Follow(S)=\{a,b,\$\}$
Production $S\to aSbS$ should be placed in S-row & a-column; production $S\to ϵ$ should also be placed in S-row & a-column (since $a\in Follow(S)$).
∴ Not LL(1) grammar.

Q2)

S → aABb   {a}   {$}
A → c|ε    {c,ε} {d,b}
B → d|ε    {d,ε} {b}

No 2 entries in the same cell. ∴ LL(1) grammar.

Q3) $S\to A\mid a,A\to a$
FIRST(S) = {a} (from both productions) → 2 entries in same cell.
∴ Not LL(1) grammar.

---

10. Recursive Descent Parser

• Top Down Parser.
• Every variable has a function.

Grammar: $E\to i{E}^{\prime },E^{\prime }\to +i{E}^{\prime }\mid ϵ$

E() {
    if (l == 'i') {
        match('i');
        E'();
    }
}
 
E'() {
    if (l == '+') {
        match('+');
        match('i');
        E'();
    }
    else return;
}
 
match(char t) {
    if (l == t) {
        l = getchar();
    } else {
        printf("Error");
    }
}
 
int main() {
    E();
    if (l == '$')
        printf("Parsing successful");
}

$l\to$ look ahead.

---

11. Operator Precedence Parser

• Bottom up parser.
• Parser that interprets an operator grammar.
• Ambiguous grammars are allowed.
• Creates an Operator Relation Table.

Operator Grammar

The grammar used to define mathematical operators is called operator grammar / operator precedence parser.

• No null productions.
• No 2 adjacent non-terminals on R.H.S.

Example: $E\to E+E\mid E\ast E\mid id$

• id has higher precedence than other operators.
• $ has least precedence than other operators.

Operator Relational Table

	id	+	*	$
id	—	$>$	$>$	$>$
+	$<$	$>$	$<$	$>$
*	$<$	$>$	$>$	$>$
$	$<$	$<$	$<$	—

For $w=id+id\ast id$:

$ id + id * id $

Algorithm

• Whenever the top of the stack is $<$ than the look-ahead → push it.
• Whenever the top of the stack is $>$ than the look-ahead → pop it & then push it.

Bottom-up parse tree produced:

graph TD
  E1[E] --> E2[E]
  E1 --> E3[E]
  E2 --> id1[id]
  E2 --> plus[+]
  E2 --> E4[E]
  E4 --> id2[id]
  E1 --> star[*]
  E3 --> id3[id]

Disadvantage of Operator Relation Table

If there are $n$ operators, $O(n^2)$ space is required.

Operator Function Table (solves the space problem)

	id	*	+	$
id	—	$>$	$>$	$>$
*	$<$	$>$	$>$	$>$
+	$<$	$<$	$>$	$>$
$	$<$	$<$	$<$	—

Relations built via functions $f$ and $g$:
$\text{‘}>\text{’}=F_{id}\to g_{id}(F\to g)$
$\text{‘}<\text{’}=g_{id}\to f_{id}(g\to F)$

Graph of $f_x,g_x$ nodes is built and the longest path from each node is computed:

• Longest path from $f_{id}$: $f_{id} \to g_* \to f_+ \to g_+ \to f_$$
• Longest path from $g_{id}$: $g_{id} \to f_* \to g_* \to f_+ \to g_+ \to f_$$

Operator Functions Table

	id	+	*	$
f	4	2	4	0
g	5	1	3	0

To compare $(+,+)$: $f_{+}=2,g_{+}=1\Rightarrow 2>1\Rightarrow (+\dot{>}+)$

Info

• Size of the table for $n$ operators is of the order $O(2n)$.
• In Operator Function Table there cannot be any blank entries.
• EDC (Error Detecting Capability): $\text{EDC[Operator Functional Table]}<\text{EDC[Operator Relation Table]}$.

Example: Create Operator Relation Table

Grammar:

P → SR | S
R → bSR | bS
S → wbS | w
W → L*W | L
L → id

After removing adjacent non-terminals:

P → SbP | SbS | S
S → wbS | w
W → L*W | L
L → id

	id	*	b	$
id	—	$>$	$>$	$>$
*	$<$	$<$	$>$	$>$
b	$<$	$<$	$<$	$>$
$	$<$	$<$	$<$	—

• $W\to L\ast W\Rightarrow$ * is right associative.
• $S\to WbS,P\to SbP\Rightarrow$ b is right associative.

---

12. LR Parsers

flowchart TD
    LR[LR Parsers] --> LR0["LR(0)"]
    LR --> SLR1["SLR(1) Simple LR"]
    LR --> LALR1["LALR(1) Look Ahead LR"]
    LR --> CLR1["CLR(1) Canonical LR"]

flowchart LR
    IB[I/P Buffer] --> LRP[LR Parser]
    Stack[Stack] --> LRP
    LRP --> PT["LR Parsing Table"]

The only difference between LR(0), SLR(1), LALR(1), CLR(1) is the LR Parsing Table.
$LR(0)$ and $SLR(1)$ use LR(0) items. $LALR(1)$ and $CLR(1)$ use LR(1) items.

In LR parsers, we perform CLOSURE and GOTO operations.

Item

Any production with a dot ($\cdot$) in the R.H.S. is called an item.

LR(0) Parsing — Worked Example

Grammar: $S\to AA,A\to aA\mid b$

Augmented grammar:
$S^{\prime }\to \cdot S(0)$
$S\to \cdot AA(1)$
$A\to \cdot aA\mid \cdot b(2)(3)$

LR(0) Parsing Tree = Canonical collection of LR(0) items.

graph TD
  I0["I0: S'→·S, S→·AA, A→·aA|·b"] -->|S| I1["I1: S'→S. (final)"]
  I0 -->|A| I2["I2: S→A·A, A→·aA|·b"]
  I0 -->|a| I3["I3: A→a·A, A→·aA|·b"]
  I0 -->|b| I4["I4: A→b. (final)"]
  I2 -->|A| I5["I5: S→AA. (final)"]
  I2 -->|a| I3
  I2 -->|b| I4
  I3 -->|A| I6["I6: A→aA. (final)"]
  I3 -->|a| I3
  I3 -->|b| I4

Parsing Table

State	ACTION a	ACTION b	ACTION $	GOTO A	GOTO S
0	S3	S4		2	1
1			Accept
2	S3	S4		5
3	S3	S4		6
4	R3	R3	R3
5	R1	R1	R1
6	R2	R2	R2

Parsing string aabb$

• Always the top of stack contains a state (the first state is 0).
• Initially, on a at $I_0$: S3 (shift the input and move to state 3, increment I/P pointer).
• If a Reduce (R) action is to take place: pop $2\times$(number of terminals/non-terminals from RHS of that production) elements. If length of RHS = $x$, pop $2x$ symbols from stack, push LHS symbol, and consult GOTO using the state now exposed at the top.

When we see a reduce move, we do not increment the input pointer.

SLR(1)

Main difference between LR(0) and SLR(1) parsing tables:

“Reduce moves are placed only if the next symbol is in the FOLLOW of the current LHS symbol.”

SLR(1) Parsing Table (same grammar)

State	a	b	$	GOTO A	GOTO S
0	S3	S4		2	1
1			Accept
2	S3	S4		5
3	S3	S4		6
4	R3	R3	R3
5			R1
6	R2	R2	R2

• $R_3$ ($A\to b$) placed only where next symbol \in Follow(A) = \{a, b, \}$.
• $R_1$ ($S\to AA$) placed only in Follow(S) = \{\}$.

---

13. Conflicts in LR Parsing

Not all grammars are suitable for LR parsing due to a shift-reduce conflict.

	a	b
5	$S_6/r_1$	$r_1$

→ SR-conflict.

Example: LR(0) vs SLR(1)

Grammar:

E' → E
E → E+T | T
T → TF | F
F → F* | a | b

Building the canonical collection of LR(0) items shows a state ($I_2$) with both:

• Reduce move: $E\to T$
• Shift move: $F\to \cdot a\mid \cdot b$

→ $I_2\to$ SR conflict ∴ the grammar is not LR(0).

To check SLR(1): a part of the parsing table is constructed for states with SR conflict.

State	a	b	*	+	$
2	S4	S5		R2	R2
3	R4	R4	S8	R4	R4
9	S4	S5		R1	R1
7	R3	R3	S8	R3	R3

$Follow(E)=\{+,\$\},Follow(T)=\{+,\$,a,b\}$

Since the conflicting rows have no overlap between shift-symbol and reduce-symbol’s FOLLOW set → Grammar is SLR(1), though not LR(0).

---

14. Checking LL(1) / LR(0) / SLR(1) — Full Worked Questions

Question A

$S\to AaAb\mid BbBa,A\to ϵ,B\to ϵ$

For LL(1):

	a	b	$
S	$S\to AaAb$	$S\to BbBa$
A	$A\to ϵ$	$A\to ϵ$
B	$B\to ϵ$	$B\to ϵ$

∴ The grammar is LL(1).

For LR(0): Building the canonical collection reveals no SR conflict (grammar looks LR(0)) but an RR conflict is present in $I_0$ (2 reduce moves at the same state). ∴ The grammar is NOT LR(0).

For SLR(1):
$Follow(A)=\{a,b\},Follow(B)=\{a,b\}$
Since $Follow(A)\cap Follow(B)\ne \varphi$ → RR conflict persists. ∴ Not SLR(1).

---

Question B

$S\to AS\mid b,A\to SA\mid a$

For LL(1): Parsing table shows conflict between $S\to AS$ / $S\to b$ productions in the same cell. ∴ Not LL(1).

For LR(0): In state $I_1$, an apparent SR conflict is not actually there, because $S^{\prime }\to S\cdot$ is not a reduce action counted the normal way (it’s the accept state). ∴ The given grammar IS LR(0).

For SLR(1): Since there are no SR/RR conflicts, the grammar is SLR(1) as well.

---

Question C

$S\to AS\mid b,A\to SA\mid a$ (mirrored version)

For LL(1): Conflict in parsing table. ∴ Not LL(1).

For LR(0): SR conflict found in state $I_3$ (not in $I_1$, since $S^{\prime }\to S\cdot$ is not a reduce action). ∴ Not LR(0).

For SLR(1):
$Follow(A)=\{a,b\}$
SR conflict persists. ∴ Grammar is not SLR(1).

Note

The grammar is ambiguous. Therefore, it can’t be parsed by any parser.

---

Question D

S → Aa | bAc | dc | bda
A → d

For LL(1): Parsing table shows conflict between S→bac/S→bda in the same cell (both under b). ∴ Not LL(1).

For LR(0): SR conflict in state $I_3$. ∴ Grammar is not LR(0).

For SLR(1):
$Follow(A)=\{a\}$
No conflict. ∴ Grammar is SLR(1).

---

15. LALR(1) and CLR(1)

Canonical collection of LR(1) items is used.
$LR(1)item=LR(0)item+look\text{-}ahead$
$LR(0)item=itemendingwithdot(\cdot )$

Closure rule with lookahead:
$A\to \alpha \cdot B\beta ,a/b\Rightarrow B\to \cdot \gamma ,FIRST(\beta )$

Example: $S\to AA,A\to aA\mid b$

Canonical collection of LR(1) items:

graph TD
  I0["I0: S'→·S,$  S→·AA,$  A→·aA,a/b  A→·b,a/b"] -->|S| I1["I1: S'→S·,$"]
  I0 -->|A| I2["I2: S→A·A,$  A→·aA,$  A→·b,$"]
  I0 -->|a| I3["I3: A→a·A,a/b  A→·aA,a/b  A→·b,a/b"]
  I0 -->|b| I4["I4: A→b·,a/b"]
  I2 -->|A| I5["I5: S→AA·,$"]
  I2 -->|a| I6["I6: A→a·A,$  A→·aA,$  A→·b,$"]
  I2 -->|b| I7["I7: A→b·,$"]
  I3 -->|A| I8["I8: A→aA·,a/b"]
  I3 -->|a| I3
  I3 -->|b| I4
  I6 -->|A| I9["I9: A→aA·,$"]

Important Points

• $I_4,I_7\to$ same in LR(0) but different states in LR(1).
• $I_3,I_6\to$ same in LR(0) but of different state (different lookahead) in LR(1).

The GOTO part and shift operation are same as in LR(0), SLR(1) parsing tables. The main difference lies in the placement of reduce moves:

• Reduce moves in $LR(0)$ = entire row.
• Reduce moves in $SLR(1)$ = FOLLOW of LHS.
• Reduce moves in $CLR(1)\&LALR(1)$ = only in look-ahead symbols.

CLR(1) Parsing Table

State	ACTION a	ACTION b	ACTION $	GOTO S	GOTO A
0	S3	S4		1	2
1			Accept
2	S6	S7			5
3	S3	S4			8
4	R3	R3
5			R1
6	S6	S7			9
7			R3
8	R2	R2
9			R2

Merging states $I_4\equiv I_7=I_{47}$, $I_3\equiv I_6=I_{36}$, $I_8\equiv I_9=I_{89}$:

$\text{No. of states in }LALR(1)=LR(0)=SLR(1)\le CLR(1)$

LALR(1) Parsing Table (after merging)

State	a	b	$
0	S36	S47
1			Accept
2	S36	S47
36	S36	S47
47	R3	R3	R3
5			R1
89	R2	R2	R2

---

16. Conflicts in LR(1)

Conflicts are less frequent than LR(0) items.

SR Conflict:
$$A \to \alpha \cdot a\beta,\ c/d \qquad B \to \gamma \cdot,\ a/$$$
→ Shift move in a column, Reduce move in a column ⇒ SR conflict.

RR Conflict:
$A\to \alpha \cdot ,aB\to \alpha \cdot ,a$
→ 2 reduce moves in the same state for the same look-ahead ⇒ RR conflict.

Worked Example

Grammar:
$S^{\prime }\to S,S\to AaAb\mid BbBa,A\to ϵ,B\to ϵ$

Checking with LL(1) / LR(0) / SLR(1) / CLR(1) / LALR(1):

The grammar is LL(1) because:

• $S\to AaAb$ is placed in row S & column ‘a’.
• $S\to BbBa$ is placed in row S & column ‘b’.
• $A\to ϵ$ is placed in row A, columns {a, b}.
• $B\to ϵ$ is placed in row B, columns {a, b}.

Canonical collection of LR(0) items: 2 reduce moves in state $I_0$ → RR conflict. ∴ Not LR(0).

$Follow(A)=\{a,b\},Follow(B)=\{a,b\}$
∴ The given grammar is not SLR(1), because $Follow(A)\cap Follow(B)\ne \varphi$.

Canonical collection of LR(1) items shows the reduce items now carry distinct lookaheads, so no conflicts remain in the CLR(1) construction.

CLR(1) Parsing Table

State	a	b	$
2	S4
3		S7
4			R3
5			S8
6	S9
7	R4
8	R1
9			R2

∴ The given grammar is CLR(1).

Also, since number of LR(0) items = number of LR(1) items, the number of states is the same for all parsers → ∴ LALR(1) grammar too.

---

17. More LL(1)/LR(0)/SLR(1)/CLR(1)/LALR(1) Comparisons

$S\to Aa\mid bAc\mid dc\mid bda,A\to d$

• Not LL(1) — because $S\to bAc$ and $S\to bda$ fall in the same cell.
• Not LR(0) — because RR conflict in $I_5$.
• $Follow(A)=\{a,c\}$, $Follow(B)=\{c,a\}$; $Follow(A)\cap Follow(B)\ne \varphi$ ⇒ Not SLR(1).
• Canonical collection of LR(1) items → no merging causes conflicts ⇒ the grammar is CLR(1) as well as LALR(1).

---

18. Handles & Bottom-Up Parsing

Handle

The tokens selected to be reduced (in a right sequential form of reduction) are called handles.
$\text{Right sequential form}=\text{Bottom Up Parsing}$

Example: For the string $n+n\ast n$:

Handles are: $n,E+n,E\ast n$.

---

19. Syntax Directed Translation (SDT)

$\text{Syntax directed parsing}=\text{Grammar}+\text{Semantic rules}$

(Adding attributes to variables.)

E → E + T   { E.value = E.value + T.value }
  | T       { E.value = T.value }
T → T * F   { T.value = T.value * F.value }
  | F       { T.value = F.value }
F → num     { F.value = num.Lvalue }

(Lvalue = lexical value)

Example: 2 + 3 * 4

E → E + T   { printf("+"); }   (1)
  | T       { }                (2)
T → T * F   { printf("*"); }   (3)
  | F       { }                (4)
F → num     { printf(num.val); } (5)

Parse tree postfix output order (rule numbers applied): $5,4,2,5,4,2,5,3,1$
Postfix output: 2 3 4 * +

Bottom-Up Parser for Same Grammar

Traversal order produces postfix directly: 2 3 4 * +.

Another Example (order of operations)

S → xxw   { printf(1); }   (1)
  | y     { printf(2); }   (2)
W → sz    { printf(3); }   (3)

String to be generated: xxxxyzz

• Bottom Up output order: 2 3 1 3 1
• Top Down output order: 2 3 1 3 1 (built in the opposite tree traversal direction — same numeric output but reached via reverse traversal)

Right-Associativity Example

E → E*T  { E.val = E.val * T.val }
  | T    { E.val = T.val }
T → F-T  { T.val = F.val - T.val }
  | F    { T.val = F.val }
F → 2    { F.val = 2 }
  | 4    { F.val = 4 }

'-' is right associative.

String to be generated: 4 - 2 - 4 * 2

Inferences

• * has higher precedence than -.
• - is right associative.

$\therefore \text{Ans}=(4-(2-4))\ast 2=(4-(-2))\ast 2=6\ast 2=12$

$\text{No. of reductions}=\text{No. of non-leaves}=10$

---

20. SDT to Build a Syntax Tree

E → E1+T  { E.nptr = mknode(E1.nptr, '+', T.nptr) }
  | T     { E.nptr = T.nptr }
T → T1*F  { T.nptr = mknode(T1.nptr, '*', F.nptr) }
  | F     { T.nptr = F.nptr }
F → id    { F.nptr = mknode(null, id.name, null); }

Example 2 + 3 * 4:

graph TD
  plus["+"] --> two["2"]
  plus --> star["*"]
  star --> three["3"]
  star --> four["4"]

Abstract Syntax Tree

A parse tree in which variables are not present.

---

21. SDT for Type Check (Data Type of Expressions)

E → E1 + E2   { if((E1.type == E2.type) && (E1.type == int)) then E.type = int else error }
  | E1 == E2  { if((E1.type == E2.type) && (E1.type == int|boolean)) then E.type = boolean else error }
  | (E1)      { E.type = E1.type }
  | num       { E.type = int }
  | true      { E.type = boolean }
  | false     { E.type = boolean }

Expression: (2+3) == 8

graph TD
  Eeq["E (==) : boolean"] --> Ebr["E (paren) : int"]
  Ebr --> Eplus["E (+) : int"]
  Eplus --> num2["num 2 : int"]
  Eplus --> num3["num 3 : int"]
  Eeq --> num8["num 8 : int"]

---

22. SDTs for Binary Numbers

Count all 1s

N → L    { N.count = L.count }
L → L1B  { L.count = L1.count + B.count }
  | B    { L.count = B.count }
B → 0    { B.count = 0 }
  | 1    { B.count = 1 }

Count all 0s

Symmetric: B.count=1 for 0; B.count=0 for 1.

No. of bits

Symmetric with B.count=1 for both 0 and 1.

Decimal Value

N → L    { N.dval = L.dval }
L → L1B  { L.dval = L1.dval * 2 + B.dval }
  | B    { L.dval = B.dval }
B → 0    { B.dval = 0 }
  | 1    { B.dval = 1 }

---

23. S-Attributed and L-Attributed Definitions

$11.01_2=3.25\frac{1}{2^2}=\frac{1}{4}=0.25$

$\text{Value of fractional part}=\frac{\text{Decimal value of fraction}}{2^{\text{no. of bits in fraction}}}$

SDT to Find Decimal Value of a Fractional Binary Number

N → L1.L2  { N.dval = L1.dval + L2.dval / 2^L2.count }
L → L1B    { L.count = L1.count + B.count; L.dval = L1.dval*2 + B.dval }
  | B      { L.count = B.count; L.dval = B.dval }
B → 0      { B.count = 1; B.dval = 0 }
  | 1      { B.count = 1; B.dval = 1 }

SDT to Generate 3-Address Code

S → id = E    { gen(id.name = E.place) }
E → E1 + T    { E.place = newtemp(); gen(E.place = E1.place + T.place) }
  | T         { E.place = T.place }
T → T1 * F    { T.place = newtemp(); gen(T.place = T1.place * F.place) }
  | F         { T.place = F.place }
F → id        { F.place = id.name }

S-Attributed vs L-Attributed

Attributes in SDT are of 2 types:

1. Synthesized attributes — value of the attribute is derived from its children.
2. Inherited attributes — value of the attribute is derived from either its parent or siblings.

S-attributed SDT	L-attributed SDT
Uses only synthesized attributes.	Uses both synthesized & inherited attributes. Each inherited attribute is restricted to inherit from parent or left sibling only.
Semantic actions placed at the right end of the production: $A\to BCC\{...\}$	Semantic actions can be placed anywhere in the production: $A\to \{...\}BC\{...\}D\{...\}E\{...\}FG\{...\}$
Attributes evaluated using bottom-up parsing.	Attributes evaluated using top-to-bottom, left-to-right parsing.

Example: x = a + b*c

graph TD
  S["S (id=E)"] --> id_x[id x]
  S --> E1["E (place=t2)"]
  E1 --> E2["E (place=a)"] --> Fa[F.place=a] --> id_a[id a]
  E1 --> plus["+"]
  E1 --> T1["T (place=t1)"]
  T1 --> T2["T (place=b)"] --> F1[F.place=b] --> id_b[id b]
  T1 --> star["*"]
  T1 --> F2["F.place=c"] --> id_c[id c]

t1 = b*c
t2 = a+t1
x  = t2

Checking whether SDTs are S-attributed or L-attributed

(1)

A → LM  { L.i = f(A.i); M.i = f(L.s); A.s = f(M.s); }
A → QR  { R.i = f(A.i); Q.i = f(R.i); A.s = f(Q.s); }   ← Q.i not L-attributed

Answer: L-attributed (option b) — not pure S-attributed since inherited attributes used, and one branch ($Q.i=f(R.i)$, inheriting from right sibling) breaks strict L-attribution.

(2)

A → BC   { B.s = A.s }     (inherited, not synthesized)

Answer: L-attributed (option b).

---

24. SDT to Store Type Information in Symbol Table

L-attributed SDT (backward propagation of type):

D → TL      { L.in = T.type }
T → int     { T.type = int; }
  | char    { T.type = char; }
L → L1 id   { L1.in = L.in; addtype(id.name, L1.in); }
  | id      { addtype(id.name, L.in); }

S-attributed SDT:

D → D1, id  { addtype(id.name, D1.type); }
  | T id    { addtype(id.name, T.type); D.type = T.type; }
T → int     { T.type = int }
  | char    { T.type = char }

---

25. Intermediate Code Generation

flowchart TD
    IC[Intermediate Code] --> Lin[Linear Form]
    IC --> Tree[Tree Form]

    Lin --> Postfix[Postfix]
    Lin --> TAC[Three Address Code]

    Tree --> ST[Syntax Tree]
    Tree --> DAG["DAG - Directed Acyclic Graph"]

Example: $(a+b)\ast (a+b+c)$

• Postfix: ab+ab+c+*
• Three Address Code:

  t1 = a + b
  t2 = t1 + c
  t3 = t1 * t2
  

  (Note: original handwritten example uses $t_4=t_1+b$; corrected general form shown above for consistency)

Syntax Tree vs DAG for $(a+b)\ast (a+b+c)$

graph TD
  star["*"] --> plus1["+"]
  star --> plus2["+"]
  plus1 --> a1[a]
  plus1 --> b1[b]
  plus2 --> a2[a]
  plus2 --> b2[b]
  plus2 --> c2[c]

DAG (shares common sub-expression $a+b$):

graph TD
  star["*"] --> plus1["+ (a+b)"]
  star --> plus2["+ (a+b+c)"]
  plus1 --> a[a]
  plus1 --> b[b]
  plus2 --> plus1
  plus2 --> c[c]

Types of 3-Address Code

#	Form	Description
1	$x=y⟨op⟩z$	Binary operation
2	$x=⟨op⟩y$	Unary operation
3	$x=y$	Assignment
4	if x <rel op> y goto L	Conditional
5	goto L	Jump
6	A[i] = x, y = A[i]	Arrays
7	x = *p, y = &x	Pointers

Various Representations of 3-Address Code

1. Quadruple
2. Triple
3. Indirect Triple

Example: $(a+b)\ast (c+d)+(a+b+c)$

1) t1 = a+b
2) t2 = c+d
3) t3 = t1*t2
4) t4 = a+b
5) t5 = t4+c
6) t6 = t3+t5

Quadruple:

opr	opt1	opt2	Result
+	a	b	t1
+	c	d	t2
*	t1	t2	t3
+	a	b	t4
+	t4	c	t5
+	t3	t5	t6

Adv: Statements can be moved around. Dis: More space wasted.

Triple:

#	opr	opt1	opt2
1	+	a	b
2	+	c	d
3	*	(1)	(2)
4	+	a	b
5	+	(4)	c
6	+	(3)	(5)

Adv: Space not wasted. Dis: Statements can’t be moved around.

Indirect Triple:

i)   (1)
ii)  (2)
iii) (3)
iv)  (4)
v)   (5)
vi)  (6)

Adv: Statements can be moved. Dis: Two accesses of memory.

---

26. Backpatching

Example:

if (a < b) then t = 1
else t = 0

(i)  : if a < b goto i+3
(i+1): t = 0
(i+2): goto i+4
(i+3): t = 1
(i+4):

Leaving the table as empty and filling them back is called backpatching.

While Loop in 3-Address Code

while (a<b) do
    x = y+z

L:  if a<b goto L1
    goto L2
L1: t = y+z
    x = t
    goto L
L2:

General While form:

L:  if (E) goto L1
    goto L2
L1: S
    goto L
L2:

flowchart TD
    E{E} -->|T| S[S]
    E -->|F| Exit
    S --> E

For Loop in 3-Address Code

for (E1; E2; E3)
    S

flowchart TD
    E1 --> E2{E2}
    E2 -->|F| Exit
    E2 -->|T| S[S]
    S --> E3
    E3 --> E2

Example:

for (i=0; i<10; i++)
    a = b+c

    i = 0
L1: if i<10 goto L2
    goto L3
L2: t1 = b+c
    a = t1
    t2 = i+1
    i = t2
    goto L1
L3:

---

27. Switch Statement Using 3-Address Code

switch (i+j) {
    case 1: a = b+c; break;
    case 2: p = q+r; break;
    default: x = y+z; break;
}

    t = i+j
    goto L4
L1: t1 = b+c
    a = t1
    goto last
L2: t2 = q+r
    p = t2
    goto last
L3: t3 = y+z
    x = t3
    goto last
L4: if t==1 goto L1
    if t==2 goto L2
    goto L3
last:

---

28. 2-Dimensional Array to 3-Address Code

$x=A[y,z]$

Row major ordering, $A:10\times 20$ (rows × columns)

t1 = y * 20
t2 = t1 + z
t3 = t2 * 4        (size of each element)
t4 = base address of A
x  = t4[t3]

---

29. GATE 2007 — Register/Memory Instructions

In a simplified computer, the instructions are:

• OP Rj, Ri — performs Rj OP Ri, stores result in Ri.
• OP m, Ri — performs val OP Ri, stores in Ri (val = value in memory location m).
• MOV m, Ri — moves content of memory location m to register Ri.
• MOV Ri, m — moves content of register Ri to memory location m.

The computer has only 2 registers, and OP is either ADD or SUB.

Basic block:

t1 = a+b
t2 = c+d
t3 = e-t2
t4 = t1-t3

Assume all operands are initially in memory. The final value of computation should be in memory. Find the minimum number of MOV instructions.

Solution attempt shown:

MOV a, R1
ADD b, R1
MOV c, R2
ADD d, R2
SUB e, R2
SUB R1, R2
MOV R2, m

→ 3 MOV operations (for load a, load c, store result) — minimum achievable given only 2 registers.

---

30. Runtime Environments

Runtime environment refers to the support provided by the OS to run a program.

• Heap grows upwards.
• Stack grows downwards.

flowchart TD
    Stack["Stack (grows down)"] --> Heap["Heap (grows up)"]
    Heap --> Static["Static / Global variables"]
    Static --> Code["Machine code"]

Storage Allocation Strategies

1) Static

• Allocation done at compile time.
• Bindings do not change at runtime.
• One activation record per procedure.

Disadvantages

• Recursion not supported.
• Size of data objects must be known beforehand.
• Data structures cannot be created dynamically.

2) Stack

• Whenever a new activation begins, an activation record is pushed onto the stack; whenever activation ends, the activation record pops off.
• Local variables are bound to fresh storage.

Disadvantage

Local variables cannot be retained once activation ends.

3) Heap

• Allocation and deallocation can be in any order.

Disadvantage

Heap management is overhead.

Summary — Activation Lifetimes

• Permanent lifetime in case of static allocation.
• Nested lifetime in case of stack allocation.
• Arbitrary lifetime in case of heap allocation.

---

31. Code Optimisation

Reducing the number of lines in a program (3-address code).

flowchart TD
    Opt[Optimisation] --> MI[Machine Independent]
    Opt --> MD[Machine Dependent]

    MI --> L1["1) Loop Optimisations"]
    L1 --> L1a["(a) Code motion / Frequency reduction"]
    L1 --> L1b["(b) Loop unrolling"]
    L1 --> L1c["(c) Loop jamming"]
    MI --> L2["2) Folding - Constant Propagation"]
    MI --> L3["3) Redundancy Elimination"]
    MI --> L4["4) Strength Reduction"]

    MD --> M1["1) Register allocation"]
    MD --> M2["2) Use of addressing modes"]
    MD --> M3["3) Peephole Optimisation"]
    M3 --> M3a["(a) Redundant load/store"]
    M3 --> M3b["(b) Flow of control options"]
    M3 --> M3c["(c) Strength Reduction"]
    M3 --> M3d["(d) Use of machine idioms"]

Loop Optimisations

• To apply optimisations, we must first detect loops.
• For detecting loops, we use Control Flow Analysis (CFA) using a Program Flow Graph (PFG).
• To find the PFG, we need basic blocks.

Basic Block

A sequence of 3-address statements where control enters at the beginning and leaves at the end without any jumps or halts.

flowchart TD
    Opt[Optimisation] --> Loops
    Loops --> CFA["CFA (PFG)"]
    CFA --> BB[Basic Block]
    BB --> Leaders

Finding Basic Blocks — Identifying Leaders

• First statement is a leader.
• Statement that is the target of a conditional or unconditional statement is a leader.
  • e.g. if(...) goto 300 → 300 is a leader; goto 400 → 400 is a leader.
• Statement that immediately follows a conditional/unconditional statement is a leader.

Worked Example — fact(x)

int f=1;
for (i=2; i<=x; i++) {
    f = f*i;
}
return f;

*3-Address Code (with leaders marked ):

*(1) f = 1                     } B1
 (2) i = 2
*(3) if i>x goto 9              } B2
 (4) t1 = f*i
 (5) f = t1
 (6) t2 = i+1                  } B3
 (7) i = t2
 (8) goto 3
*(9) goto calling program       } B4

PFG:

flowchart TD
    B1 --> B2
    B2 --> B3
    B3 --> B2
    B2 --> B4

(Loop detected via CFA between B2 and B3.)

Types of Loop Optimisations

Frequency Reduction (Code Motion) — moving code from a high-frequency region to a low-frequency region.

while (i<5000) {
    A = sinx/cosx * i;
    i++;
}

flowchart LR
    Before["while(i<5000) A=sinx/cosx*i; i++;"] --> After["t=sinx/cosx; while(i<5000) A=t*i; i++;"]

Loop Unrolling

while (i<10) { x[i] = 0; i++; }

↓

while (i<10) { x[i]=0; i++; x[i]=0; i++; }

Loop Jamming — combining bodies of 2 loops.

for(i=0;i<10;i++)
    for(j=0;j<10;j++)
        x[i,j] = 0;
for(i=0;i<10;i++)
    x[i,i] = 0;

↓

for(i=0;i<10;i++) {
    for(j=0;j<10;j++)
        x[i,j] = 0;
    x[i,i] = 0;
}

Other Machine Independent Optimisations

1) Folding — replacing an expression that can be computed at compile time by its value.
$2+3+C+B\Rightarrow 5+C+B$

2) Redundancy Elimination (DAG) — an expression that is already evaluated is used again and again.

A = B + C
D = 2 + B + 3 + C

↓

D = 2 + 3 + A

3) Strength Reduction — replacing a costly operation with a cheaper one.

Multiplication & division are costly; bit manipulation is cheaper.

B = A*2  →  B = A<<1

4) Algebraic Simplification — eliminate trivial statements.

A = A+0   (eliminated)
B = B*1   (eliminated)

Machine Dependent Optimisations

• Register allocation (max. utilization of registers) → Local allocation, Global allocation.
• Use addressing modes.
• Peephole optimisation:
  • (a) Redundant load and store

    x = y+z          MOV y, R0
                     ADD z, R0
                     MOV R0, x
    

    a = b+c          MOV b, R0
    d = a+e          ADD c, R0
                     MOV R0, a  ← redundant
                     MOV a, R0
                     ADD e, R0
    

  • (b) Flow of control optimisation:
    • Avoid jumps on jumps:

      L1: jump L2
      ...
      L2: jump L3
      ...
      L3: jump L4
      

    • Eliminate dead code:

      #define x 0
      if (x) {
          // dead code
      }

  • (c) Use of machine idioms:

    i = i+1        MOV R0, i
                   ADD R0, 1
                   MOV i, R0
    

    → replaced by machine code for increment: inc i

---

32. Data Flow Analysis

Structured graph-based analysis of the program.

1) Constant Propagation

int x = 14;
int y = 7 - x/2;
return y * (28/x + 2);

Propagate x →

int x = 14;
int y = 7 - 14/2;
return y * (28/14 + 2);

Propagate y (evaluates to 0) →

int x = 14;
int y = 0;
return 0;         // dead code elimination applies here

2) Common Subexpression Elimination (CSE)

Redundancy elimination is a form of CSE.

a = b*c + g   ...(1)
d = b*c + e   ...(2)

b*c is the common subexpression.

temp = b*c;
a = temp+g
d = temp+e

Space required increased due to the additional temporary variables.

Trade-off: If $cost(b\ast c)>cost(\text{temp creation \& fetching})$, then it is useful.

• Local CSE → within a single block.
• Global CSE → entire function/procedure.

---

33. Live Variable Analysis

Definition

A variable $v$ is live at point $P$ if the value of $v$ is used in some path in the flow graph starting at $P$. Else it is dead.

Application: Register Allocation — live variables are stored in registers (instead of dead variables).

$DEF(B)=\text{all variables defined in }B\text{ before being used}$
$USE(B)=\text{variables used in the block before defining them}$

Worked Example

flowchart TD
    Entry --> B1
    B1 --> B2
    B2 --> B3
    B2 --> B4
    B3 --> B4
    B4 --> B2
    B4 --> Exit

B1: d1: i = m-1
    d2: j = n
    d3: a = u1
B2: d4: i = i+1
    d5: j = j-1
B3: d6: a = u2
B4: d7: i = a+j

Block	IN	DEF	USE	OUT
B1	{m,n,u1,u2}	{i,j,a}	{m,n,u1}	{i,j,u2,a}
B2	{i,j,u2,a}	{}	{i,j}	{a,j,u2}
B3	{u2,j}	{a}	{u2}	{a,j,u2}
B4	{a,j,u2}	{i}	{a,j}	{i,j,u2,a}

Formulas

$OUT[B]={\bigcup }_{S:successorofB}IN[S]$
$IN[B]=USE[B]\cup (OUT[B]-DEF[B])$

Algorithm: Live Variable Analysis

Input: Flow graph with DEF and USE calculated for each block.
Output: IN[B] and OUT[B], the set of variables live at entry and exit of each block.

IN[EXIT] = φ
for (each basic block B other than EXIT)
    IN[B] = φ

while (changes to any IN occur) {
    for (each basic block B other than EXIT) {
        OUT[B] = ⋃ (over S = successor of B) IN[S]
        IN[B]  = USE[B] ∪ (OUT[B] - DEF[B])
    }
}

Summary (Data Flow Framework)

#	Component	Value
1	Domain	Variables
2	Transfer function	Backward: $IN[B]=f(OUT[B])$; $f_B(x)=US{E}_B\cup (x-DE{F}_B)$ (because using OUT, we calculate IN)
3	Meet operation	$OUT[B]={\bigcup }_{S}IN[S]$
4	Boundary condition	$IN[EXIT]=\varphi$
5	Initial interior points	$IN[B]=\varphi$

---

34. Static Single Assignment (SSA)

• Very similar to 3-address code but different.
• Optimization becomes easy.

Basic Concept

Each variable can have at most one assignment / definition.

Example:

i ← 0
...
if (i < 0)   ; i is sure to have not been modified since
...

→ Optimisation can be done always here (in SSA), because $i$ is guaranteed unmodified.

In 3-address code: $i$ might have been redeclared elsewhere → optimisation can’t be done as confidently.

Optimisations must be safe.

Execution of transformed code must yield the same results as the original code, for all possible executions.

Optimisation Techniques

• Common subexpression elimination
• Dead code elimination
• Copy propagation
• Constant propagation

Other Optimisations

• Arithmetic simplification: $x=4+a\Rightarrow x=a<<2$
• Constant folding: $x=4\ast 5\Rightarrow x=20$

Tip

• Liveness analysis is used for dead code elimination.
• Available expression analysis is used for common subexpression elimination.