Translating Expressions and Assignments
We have met three-address
code as a target; now we ask the real question of a front end: how does the compiler
actually produce it, mechanically, from a parse tree? The answer is one of the most satisfying
ideas in compiling — a syntax-directed translation scheme that walks the expression
tree and, at each node, emits a single instruction while threading a small amount of information up the
tree. There is no cleverness, no search: the structure of the grammar is the algorithm.
The engine has two parts. A generator \textit{newtemp}() that hands out a
fresh temporary each time it is called (t_1, t_2, t_3, \dots), and a synthesized
attribute E.\textit{addr} attached to every expression node, holding
the address where that sub-expression's value ends up living. Leaves already know their address
(a variable's name, a constant's value); interior nodes compute one by emitting an instruction into a
fresh temporary and reporting that temporary upward. Assemble those two pieces and TAC generation writes
itself.
The translation scheme
Here is the classic SDT for expressions and assignments (following the Dragon Book). Each production
carries a semantic action in braces; \Vert denotes appending an instruction
to the output, and gen builds one three-address instruction:
S -> id = E { gen( id.addr '=' E.addr ) }
E -> E1 + E2 { E.addr = newtemp();
gen( E.addr '=' E1.addr '+' E2.addr ) }
E -> E1 * E2 { E.addr = newtemp();
gen( E.addr '=' E1.addr '*' E2.addr ) }
E -> - E1 { E.addr = newtemp();
gen( E.addr '=' 'minus' E1.addr ) }
E -> ( E1 ) { E.addr = E1.addr } // parentheses carry the address up unchanged
E -> id { E.addr = id.addr } // a leaf already has an address
E -> num { E.addr = num.value }
Read the pattern: a leaf production copies an existing address up (no instruction emitted); an
operator production calls \textit{newtemp}(), emits exactly one
instruction, and reports the new temporary as its own address. Because the children's actions run before
the parent's (a post-order, bottom-up traversal), each child's addr is
already filled in by the time the parent needs it. One node, one temporary, one instruction.
A worked example, node by node
Take x = a + b \times c. Precedence makes the tree
a + (b \times c). Reveal the traversal: each interior node lights up as it
emits its instruction and is labelled with the temporary it produces.
The emitted three-address code, in the order the post-order walk produces it:
t1 = b * c
t2 = a + t1
x = t2
Every interior node contributed exactly one line, and the temporaries chain the values together bottom
to top. This is the mechanical heart of a compiler's front end: give it any expression tree and it grinds
out correct TAC without a moment's thought.
Arrays: address arithmetic and type-driven widths
Expressions over scalars are the easy case. The moment an array reference like
a[i] appears, the translator must compute a memory address,
and that is where element widths enter. For a one-dimensional array a whose
elements each occupy w bytes, the element a[i] lives
at
\textit{base}(a) \; + \; i \times w.
The width w is type-driven: an array of 4-byte ints uses
w = 4, of 8-byte doubles uses w = 8.
The compiler reads it from the symbol table's type information. So x = a[i]
(with int elements) lowers to an offset computation followed by an indexed load:
t1 = i * 4 // scale the index by the element width
t2 = a[t1] // indexed read: fetch the element at offset t1
x = t2
Two dimensions compose the same idea by a
row-major formula: for
a[i][j] with n_2 columns, the offset is
(i \times n_2 + j) \times w. The key insight is that array indexing is not a
primitive — it is arithmetic on addresses, generated by the same
\textit{newtemp}() machinery as everything else.
The emitter, in code
Below is the SDT scheme made real: a recursive emitter over an expression AST. Each node type maps to
one case; operators call newtemp(), push one instruction, and return the temporary as their
address. We translate x = a + b \times c and an array read
y = m[k], then print the TAC.
type Expr =
| { kind: "num"; value: number }
| { kind: "var"; name: string }
| { kind: "bin"; op: string; l: Expr; r: Expr }
| { kind: "neg"; e: Expr }
| { kind: "index"; arr: string; idx: Expr; width: number }; // a[idx], element width in bytes
const code: string[] = [];
let counter = 0;
const newtemp = () => `t${++counter}`;
const emit = (line: string) => code.push(line);
// Returns the ADDRESS (a string) where this sub-expression's value lives.
function gen(e: Expr): string {
switch (e.kind) {
case "num": return String(e.value);
case "var": return e.name;
case "neg": {
const a = gen(e.e);
const t = newtemp();
emit(`${t} = minus ${a}`);
return t;
}
case "bin": {
const a = gen(e.l); // children first (post-order)
const b = gen(e.r);
const t = newtemp();
emit(`${t} = ${a} ${e.op} ${b}`);
return t;
}
case "index": {
const i = gen(e.idx);
const off = newtemp();
emit(`${off} = ${i} * ${e.width}`); // scale by element width
const t = newtemp();
emit(`${t} = ${e.arr}[${off}]`); // indexed read
return t;
}
}
}
function assign(lhs: string, e: Expr): void {
const a = gen(e);
emit(`${lhs} = ${a}`);
}
// x = a + b * c
assign("x", {
kind: "bin", op: "+",
l: { kind: "var", name: "a" },
r: { kind: "bin", op: "*", l: { kind: "var", name: "b" }, r: { kind: "var", name: "c" } },
});
emit("---");
counter = 0; // restart temp numbering for the second example
// y = m[k] (int array, width 4)
assign("y", { kind: "index", arr: "m", idx: { kind: "var", name: "k" }, width: 4 });
code.forEach((line) => console.log(line));
The first block prints t1 = b * c, t2 = a + t1, x = t2; the second
prints the scaled-offset pattern t1 = k * 4, t2 = m[t1], y = t2.
The same recursive walk handles arithmetic and array addressing — that uniformity is the whole
pay-off of syntax-directed translation.
Yes — and it should, eventually, but not here. The naive scheme mints a brand-new temporary at every
operator, which for a deep expression produces a long parade of t1 … tk, most of which are
alive for only a single instruction. That is fine: at IR level temporaries are free and unbounded, and
keeping them distinct helps later analysis. A classic refinement is Sethi–Ullman numbering,
which computes the minimum number of registers an expression needs and reuses temporaries on a stack
discipline, so a + b and c + d can share a temporary once the first is dead. But
that is an optimisation; the correctness of translation never depends on it. Generate freely,
then let register allocation tidy up.
Two subtle traps. First, evaluation order: the scheme evaluates a binary node's
left child before its right. For pure arithmetic that never matters, but if operands
have side effects (a function call, a ++), the order the compiler picks becomes observable —
C famously leaves it unspecified, so f() + g() may run either first. Fix the order in your
scheme and document it. Second, array offsets: the index must be scaled by the element
width, not used raw. Writing a[i] as offset i instead of
i * w is a classic off-by-a-factor bug that reads the wrong element (and for
doubles, lands halfway inside one). Always multiply the index by the type's width before the
indexed access.