Three-address code in Compiler Design - Full Explanation

Introduction

When a computer program is translated from a high-level language to machine code, it first needs a simpler form that is easier to analyze and optimize. Three-address code solves this by breaking complex instructions into simple steps with at most three parts, making the translation process clearer and more manageable.

Explanation

Structure of Three-address code

Three-address code consists of instructions that have at most three addresses or operands. Typically, these are two source operands and one destination operand. Each instruction performs a simple operation like addition, subtraction, or assignment, making the code easy to understand and manipulate.

Each instruction in three-address code has at most three operands, simplifying complex operations into basic steps.

Types of Instructions

The instructions in three-address code include assignments, arithmetic operations, conditional and unconditional jumps, and function calls. This variety allows it to represent most programming constructs in a simple, linear form that is easy for the compiler to work with.

Three-address code supports various instruction types to represent different programming actions simply.

Use in Compiler Design

Compilers use three-address code as an intermediate step between the source code and machine code. It helps in optimization by making it easier to spot redundant calculations or simplify expressions. It also aids in generating efficient machine code later.

Three-address code acts as a bridge in compilers to optimize and generate machine code efficiently.

Temporary Variables

To break down complex expressions, three-address code introduces temporary variables to hold intermediate results. These variables help keep each instruction simple and focused on a single operation, which makes the code easier to analyze and optimize.

Temporary variables store intermediate results to keep instructions simple and clear.

Real World Analogy

Imagine assembling a piece of furniture by following a step-by-step instruction manual. Instead of trying to build the whole thing at once, you complete one small task at a time, like attaching one leg or tightening one screw. This makes the process easier and less confusing.

Structure of Three-address code → Each small furniture step involves only a few parts, similar to instructions with at most three operands.

Types of Instructions → Different furniture steps like attaching legs, tightening screws, or placing shelves represent various instruction types.

Use in Compiler Design → The instruction manual helps you build the furniture correctly and efficiently, like three-address code helps the compiler optimize and generate machine code.

Temporary Variables → Using a small container to hold screws temporarily is like using temporary variables to hold intermediate results.

Diagram

Diagram

┌─────────────────────────────┐
│   Three-address code example │
├─────────────────────────────┤
│ t1 = a + b                 │
│ t2 = t1 * c                │
│ d = t2 - e                 │
└─────────────────────────────┘

This diagram shows a simple three-address code sequence breaking down a complex expression into steps with temporary variables.

Key Facts

Three-address code → An intermediate code with instructions having at most three operands.

Temporary variable → A variable used to hold intermediate results in three-address code.

Intermediate code → A code form between source code and machine code used for optimization.

Instruction types → Includes assignments, arithmetic operations, jumps, and function calls in three-address code.

Common Confusions

Believing three-address code is the final machine code.

Believing three-address code is the final machine code. Three-address code is an intermediate representation used inside the compiler, not the actual machine code executed by the computer.

Thinking all instructions must have exactly three operands.

Thinking all instructions must have exactly three operands. Instructions have at most three operands; some may have fewer, like simple assignments with two operands.

Summary

Three-address code breaks complex operations into simple instructions with up to three operands to make compilation easier.

It uses temporary variables to hold intermediate results, helping with code clarity and optimization.

This code form acts as a bridge in compilers to optimize and generate efficient machine code.

Practice

1. What is the main purpose of three-address code in compiler design?

easy

A. To execute machine code directly on hardware

B. To break complex instructions into simpler steps with at most three parts

C. To store source code in a compressed format

D. To replace high-level language syntax with natural language

Solution

1. Step 1: Understand the role of intermediate code

   Intermediate code like three-address code simplifies complex instructions for easier processing.

2. Step 2: Identify the key feature of three-address code

   It breaks instructions into steps with at most three parts (two operands and one result).

3. Final Answer:

   To break complex instructions into simpler steps with at most three parts -> Option B

4. Quick Check:

   Three-address code = simple 3-part instructions [OK]

Hint: Three-address code simplifies instructions into three parts [OK]

Common Mistakes:

• Confusing three-address code with machine code
• Thinking it compresses source code
• Believing it replaces programming languages

2. Which of the following is a correct example of a three-address code instruction?

easy

A. if a > b goto L1 else goto L2

B. while (a < b) { a = a + 1; }

C. print(a, b, c)

D. t1 = a + b

Solution

1. Step 1: Identify the format of three-address code

   It typically has one operator and up to two operands, assigning result to a temporary variable.

2. Step 2: Check each option

   t1 = a + b matches the format: one operator (+), two operands (a, b), and a result (t1). Others are control flow or high-level statements.

3. Final Answer:

   t1 = a + b -> Option D

4. Quick Check:

   Three-address code = one operator, two operands, one result [OK]

Hint: Look for one operator and two operands with a result variable [OK]

Common Mistakes:

• Choosing control flow statements as three-address code
• Confusing function calls with three-address code
• Ignoring the assignment to a temporary variable

3. Given the three-address code:
t1 = a + b
t2 = t1 * c
d = t2 - e
What is the final value assigned to d in terms of a, b, c, e?

medium

A. (a + b) * c - e

B. a + b * c - e

C. a + (b * c) - e

D. (a + b) - (c * e)

Solution

1. Step 1: Evaluate intermediate expressions step-by-step

   t1 = a + b; then t2 = t1 * c = (a + b) * c; finally d = t2 - e = (a + b) * c - e.

2. Step 2: Substitute and simplify

   The final expression for d is (a + b) * c - e, matching (a + b) * c - e.

3. Final Answer:

   (a + b) * c - e -> Option A

4. Quick Check:

   Follow code stepwise = (a + b) * c - e [OK]

Hint: Follow temporary variables stepwise to build final expression [OK]

Common Mistakes:

• Ignoring parentheses changing operation order
• Multiplying b by c before adding a
• Mixing subtraction order

4. Identify the error in this three-address code snippet:
t1 = a + b
t2 = t1 *
d = t2 - e

medium

A. Missing operand after '*' operator in second line

B. Incorrect use of temporary variables

C. Assignment to 'd' should be before 't2'

D. No error, code is correct

Solution

1. Step 1: Examine the second line syntax

   The second line ends with '*' operator but lacks the second operand after '*', which is invalid.

2. Step 2: Confirm other lines are correct

   First and third lines have proper assignments and operands; only second line has syntax error.

3. Final Answer:

   Missing operand after '*' operator in second line -> Option A

4. Quick Check:

   Operator must have two operands [OK]

Hint: Check each operator has two operands in three-address code [OK]

Common Mistakes:

• Ignoring incomplete operator usage
• Thinking variable order causes error
• Assuming code is correct without checking syntax

5. How would you represent the high-level statement if (a < b) c = a + b; else c = a - b; in three-address code?

hard

A. if a < b then c = a + b else c = a - b

B. c = a + b if a < b else c = a - b

C. if a < b goto L1c = a - bgoto L2L1: c = a + bL2:

D. t1 = a < bc = t1 ? a + b : a - b

Solution

1. Step 1: Translate conditional jump

   Use 'if a < b goto L1' to jump to true branch, else execute false branch.

2. Step 2: Write false branch, jump over true branch

   False branch: c = a - b; then jump to L2 to skip true branch.

3. Step 3: Write true branch and label

   Label L1: c = a + b; Label L2 marks end of conditional.

4. Final Answer:

   if a < b goto L1
   c = a - b
   goto L2
   L1: c = a + b
   L2: -> Option C

5. Quick Check:

   Use labels and jumps for if-else in three-address code [OK]

Hint: Use labels and jumps to represent if-else in three-address code [OK]

Common Mistakes:

• Writing high-level if-else syntax directly
• Using ternary operator not valid in three-address code
• Missing jump to skip true branch after false branch