🧠 Backpatching and Switch Statements (Compiler Construction)

These topics are part of Intermediate Code Generation and Code Generation phase in a compiler. They are very important for exams because they are often asked with diagrams and examples.

---

📌 1. Backpatching

📖 Definition

Backpatching is a technique used in compiler design to handle forward jumps in intermediate code by filling in (patching) missing addresses later.

👉 In simple words:

We write code first, and fill the correct jump addresses later when they become known.

---

❓ Why Backpatching is Needed?

In programming, sometimes we need to jump to a label that is not yet known.

Example:

if (a < b)
    goto L1;

But at this time, we don’t know where L1 is located in code.

👉 So we leave it empty and fill it later.

---

⚙️ Basic Idea

• Generate incomplete jump instructions
• Store their locations in a list
• Fill correct addresses later

---

📊 Example (Three Address Code)

1. if a < b goto __
2. goto __
3. ...
4. L1: t = a + b

Later we fill:

• First blank → L1
• Second blank → next instruction

---

🔄 Steps of Backpatching

🔹 Step 1: Generate code with blanks

if a < b goto _

🔹 Step 2: Maintain list of incomplete jumps

List = {1}

🔹 Step 3: When label is found, fill address

patch(1, L1)

---

🧠 Key Data Structures in Backpatching

🔹 1. List of incomplete jumps

Stores unresolved goto statements

🔹 2. Functions used:

• makelist(i) → creates list with instruction i
• merge(p1, p2) → merges two lists
• backpatch(p, addr) → fills address

---

⭐ Important Exam Points

✔ Used in control flow statements ✔ Handles forward jumps ✔ Used in if, if-else, loops ✔ Uses three address code (TAC) ✔ Helps in code generation phase

---

📌 2. Switch Statements in Compiler Design

📖 Definition

A switch statement is a multi-way branch statement that allows selection of one block among many based on the value of an expression.

---

🔍 Example (High-level code)

switch(x) {
  case 1: a = 10; break;
  case 2: a = 20; break;
  default: a = 0;
}

---

⚙️ Translation into Intermediate Code

Switch statements are converted into:

1. Jump Table OR

2. Sequence of conditional jumps

---

📊 Method 1: If-Else Chain (Simple)

if x == 1 goto L1
if x == 2 goto L2
goto L3

L1: a = 10
goto end

L2: a = 20
goto end

L3: a = 0

end:

---

📊 Method 2: Jump Table (Efficient)

Used when cases are dense.

index = x - 1
goto table[index]

Where:

table[0] → L1
table[1] → L2
table[2] → L3

---

⚙️ Working of Switch Statement

Step-by-step:

1. Evaluate expression
2. Compare with cases
3. Jump to matching label
4. Execute block
5. Exit switch

---

📌 Types of Implementation

🔹 1. Linear Search (If-Else Chain)

• Slower
• Used for fewer cases

🔹 2. Binary Search (Optimized)

• For sorted cases

🔹 3. Jump Table (Fastest)

• Constant time access
• Used when cases are dense

---

⭐ Important Exam Points

✔ Switch is a multi-way branching statement ✔ Implemented using:

• if-else chain
• jump table ✔ Jump table is most efficient ✔ Used in intermediate code generation ✔ Helps reduce number of comparisons

---

🔗 3. Relationship Between Backpatching & Switch

Concept	Role
Backpatching	Fills missing jump addresses
Switch statement	Uses multiple jumps to labels
Connection	Both involve control flow & jumps

---

📊 FINAL REVISION TABLE

🔹 Backpatching

Feature	Description
Purpose	Handle forward jumps
Used in	Control flow statements
Technique	Fill addresses later
Functions	makelist, merge, backpatch
Code type	Three address code

---

🔹 Switch Statement

Feature	Description
Type	Multi-way branch
Implementation	if-else or jump table
Best method	Jump table
Use	Efficient selection
Optimization	Reduces comparisons

---

🎯 Final Exam Definitions

📌 Backpatching:

Backpatching is a technique used in intermediate code generation where incomplete jump instructions are temporarily left with blank addresses and are filled later when target labels become known.

📌 Switch Statement:

A switch statement is a multi-way decision construct that is translated into intermediate code using either conditional jumps or jump tables for efficient execution.

---