Three-address code in Compiler Design - Time & Space Complexity

Time Complexity: Three-address code

O(n * m)

Understanding Time Complexity

Analyzing time complexity helps us understand how the steps to create three-address code grow as the input program gets bigger.

We want to know how the work needed changes when the program has more statements or expressions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for each statement S in program:
    for each expression E in S:
        generate three-address code for E

This code generates three-address code by visiting every statement and its expressions in the program.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating three-address code for each expression.
• How many times: Once for every expression inside every statement in the program.

How Execution Grows With Input

As the number of statements and expressions grows, the total steps to generate code grow roughly in proportion.

Input Size (n)	Approx. Operations
10 statements	About 10 times the expressions per statement
100 statements	About 100 times the expressions per statement
1000 statements	About 1000 times the expressions per statement

Pattern observation: The work grows linearly as the program size increases.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to generate three-address code grows in a straight line with the number of statements and expressions.

Common Mistake

[X] Wrong: "Generating three-address code takes the same time no matter how big the program is."

[OK] Correct: More statements and expressions mean more code to generate, so the time grows with program size.

Interview Connect

Understanding how code generation time grows helps you explain compiler efficiency clearly and confidently in interviews.

Self-Check

"What if expressions inside statements were nested deeply? How would the time complexity change?"

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