Translating High-Level Constructs to Three-Address Code (TAC)

What is Three-Address Code?

Imagine you have a complex C statement like a = b * -c + b * -c;. The compiler needs to break this down into a sequence of simpler operations that a machine can execute. Three-Address Code provides a formal way to do this. The core idea is that each instruction should have at most one operator on its right-hand side.

The general form of a TAC instruction is result = operand1 op operand2. As the name suggests, this involves three "addresses": two for the operands and one for the result. An "address" can be:

• A variable name from your source code.
• A constant.
• A compiler-generated temporary variable (often named t1, t2, etc.) to hold intermediate results.

To understand why this is a crucial step, let's watch an introductory video.

As the video explained, TAC removes the ambiguity and complexity of high-level expressions. A statement like x = a + b * c would be broken down into:

1. t1 = b * c
2. t2 = a + t1
3. x = t2

This sequence makes the order of operations explicit and exposes each simple computation for potential optimization later.

The Building Blocks of TAC

Before we start translating, we need to know our "instruction set." The video introduced the general idea, but let's formalize the common types of TAC instructions. These are the building blocks you'll use to represent any high-level program.

We will now see how to combine these instruction types to translate the programming constructs you already know.

Translating High-Level Constructs to TAC

This is the core skill for this topic. We'll go through common constructs one by one and see the standard translation pattern.

1. Control Flow: if-else Statements

Consider a standard if-else block in C.

if (x < y) {
  z = x;
} else {
  z = y;
}
// statement after if-else

The logic for translation is as follows:

1. Evaluate the condition x < y.
2. If the condition is false, jump to the else part.
3. Otherwise, execute the then part.
4. After the then part, unconditionally jump over the else part to continue execution.

The following video demonstrates this exact translation.

The resulting TAC looks something like this:

      t0 = x < y
      ifz t0 goto L_ELSE  // if t0 is false (0), jump to else
      // THEN block
      z = x
      goto L_END        // Unconditionally jump to the end
L_ELSE:
      // ELSE block
      z = y
L_END:
      // ... code continues here

2. Control Flow: while Loops

A while loop has a similar logic, involving a loop condition check and jumps.

while (x < y) {
  x = x * 2;
}
// statement after while

The translation pattern is:

1. Create a label for the beginning of the loop to jump back to.
2. Evaluate the loop condition.
3. If the condition is false, jump out of the loop.
4. Otherwise, execute the loop body.
5. At the end of the loop body, unconditionally jump back to the beginning to re-evaluate the condition.

The TAC for the while loop example would be:

L_BEGIN:
      t0 = x < y
      ifz t0 goto L_END // If condition is false, exit loop
      // Loop body
      t1 = x * 2
      x = t1
      goto L_BEGIN     // Jump back to the start
L_END:
      // ... code continues here

3. Array Access: The Importance of Address Calculation

This is where the concepts from our previous lessons on symbol tables and memory layout become critical. When you write a[i] in a high-level language, the compiler automatically calculates the memory address. In TAC, we must make this calculation explicit.

The Crucial Difference:
In a high-level language, a[i] accesses the i-th element.
In TAC, an indexed instruction like x = y[i] typically means "access the memory at address y + i". It's a direct base + displacement calculation.

Therefore, to translate a[i], we must first compute the displacement in bytes: i * size_of_element.

Let's expand on this with a 2D array, where the calculation is more involved. For A[i][j] in a row-major language like C, the address is calculated as: base_address(A) + (i * num_columns + j) * element_size.

Putting It All Together

Let's solidify our understanding by translating a complete code snippet.

Consider the following C code, which initializes an array:

int a[20]; // Assume integers are 4 bytes
int i;
i = 0;
while (i < 20) {
    a[i] = i;
    i = i + 1;
}

Let's translate this into Three-Address Code step-by-step:

      i = 0                   // Initial assignment

L1:                           // Label for the start of the while loop
      if i >= 20 goto L2      // Condition check, jump to end if false

      // Body of the loop begins
      t1 = i * 4              // Address calculation: i * element_size (4 bytes)
      a[t1] = i               // Indexed assignment: base address 'a' + displacement 't1' gets value of i
      
      t2 = i + 1              // Increment i
      i = t2
      
      goto L1                  // Jump back to the start of the loop

L2:                           // Label for the statement after the loop
      // ... code continues

Notice how every single operation—the comparison, the address calculation, the assignment, the increment—has been broken down into its own simple, three-address instruction. This is the goal of this compiler phase.

Conclusion

In this lesson, we bridged the gap between semantic analysis and the final stages of compilation. You've learned how to systematically translate high-level code into Three-Address Code, a structured and machine-independent intermediate form.

Here are the key takeaways:

• Three-Address Code (TAC) breaks down complex operations into simple instructions of the form result = op1 op op2.
• This representation makes the order of operations explicit and is ideal for optimization.
• High-level control flow constructs like if-else and while are translated using labels and conditional/unconditional goto statements.
• Array access a[i] must be translated by first explicitly calculating the memory address as base_address + i * element_size.

In our next and final lesson of this module, we will explore Code Optimization. You will see firsthand why generating TAC is so beneficial, as we learn about techniques like constant folding and common subexpression elimination that operate directly on this intermediate code to make programs faster and more efficient.