Translating Arithmetic Expressions into Three-Address Code (TAC): From Syntax Tree to TAC

Three-address code [$\text{TAC}$]{def="An intermediate code where each instruction uses at most three operands: two inputs and one result"} is a linearized intermediate representation used in compilers. Each TAC instruction typically has the form $x := y \ \text{op}\ z$ (binary) or $x := \text{op}\ y$ (unary), where operands are names (identifiers, constants, or compiler-generated temporaries).2

A standard translation workflow is:

1. Parse the expression into a tree structure (AST/parse tree).
2. Traverse the tree (commonly postorder) so that child computations are emitted before the parent.
3. For each operator node, emit one TAC instruction using temporaries to hold intermediate results.
4. The final TAC value is the “place”/temporary of the root node.2

Mermaid view of the idea (AST node → emitted TAC line):

Key ideas/terms you will use:

• AST
• Temporary variable
• Postorder traversal
• Unary minus
• Intermediate code generation

Three-address code (TAC) translation process

TAC instruction constraints

In TAC, “complicated arithmetic expressions are represented as a sequence of three-address instructions, using temporaries for intermediate values.”2 Concretely:

• Binary operators (e.g., $+$, $*$, $-$):
  emit $t_k := \text{left.place} \ \text{op}\ \text{right.place}$
• Unary minus (e.g., $-b$):
  emit $t_k := \text{minus}\ \text{operand.place}$ (often written as a unary operator like minus to distinguish it from binary subtraction).2

The core generation can be described with a syntax-directed translation scheme where each expression node has attributes:

• $E.\text{place}$: where the value of $E$ lives (identifier or temporary)
• $E.\text{code}$: the TAC emitted to compute $E$.

In practice, the compiler performs a postorder walk: compute children TAC first, then emit the parent TAC using their resulting places.

Algorithm (tree → TAC)

Let each node in the AST return its $place$:

• If the node is an identifier $x$: $E.\text{place} := x$ and $E.\text{code} := \epsilon$.
• If the node is a binary operator $\text{op}(L,R)$:
  • translate $L$ and $R$ to get $L.\text{place}, R.\text{place}$
  • create a new temporary $t$
  • emit t := L.place op R.place
  • return $t$
• If the node is unary minus $\text{minus}(U)$:
  • translate $U$ to get $U.\text{place}$
  • create a new temporary $t$
  • emit t := minus U.place
  • return $t$.2

Unary minus vs binary minus: many compiler presentations explicitly use a special operator minus for unary negation so that TAC generation uses different instruction forms for unary negation and subtraction.

Expression to translate

Translate into TAC the arithmetic expression: $a * -b + (c - d) * e$

We must respect precedence:

• Unary minus binds to $b$ first.
• Multiplication $*$ binds tighter than addition $+$.
• Parentheses $(c-d)$ force subtraction before the multiplication by $e$.

Corresponding syntax tree (AST)

Using an AST whose internal nodes are operators and leaves are operands, the structure is:

• Root is $+$
• Left child is $*$ between $a$ and $(-b)$
• Right child is $*$ between $(c-d)$ and $e$

Mermaid syntax tree:

Translate AST to TAC

We perform postorder:

1. Compute $-b$
2. Compute $a * (-b)$
3. Compute $(c-d)$
4. Compute $(c-d) * e$
5. Compute the final sum

Let temporaries be $t_1,t_2,t_3,\dots$ in creation order. TAC instructions (quadruple style omitted, using the common assignment form):

TAC sequence

1. Unary minus $t_1 := \text{minus}\ b$ (i.e., $t_1 = -b$)2
2. Left multiplication $t_2 := a * t_1$
3. Subtraction in parentheses $t_3 := c - d$
4. Right multiplication $t_4 := t_3 * e$
5. Final addition $t_5 := t_2 + t_4$

If the expression is assigned to some destination $x$, you would finish with: $x := t_5$ (though your prompt only asks to translate the expression itself).

These steps mirror the standard rule that each TAC instruction corresponds to one operator node, and operator outputs flow upward via temporaries.3