Many students can define three-address code but freeze when asked to convert an expression, count temporaries, or select a quadruple row. Practice makes the process mechanical. Two expressions carry almost all of that work: a = b * -c + b * -c for the quadruple, triple and indirect-triple forms, and x = (a + b) * (c + d) - (a + b) / e for common subexpressions and temporary counting.
Why compilers bother with an intermediate representation
An intermediate representation, or IR, sits between the front end and back end. The front end handles lexing, parsing, and semantic analysis. Review lexical analysis as the first front-end phase, while the parser rests on the grammar machinery in Context-Free Grammars and Pushdown Automata. The back end optimises the IR and generates target code.
The shared IR makes retargeting easier. For 3 source languages, C, a Java-like language, and a Python-like language, and 3 targets, x86, ARM, and RISC-V, direct translation needs 3 x 3 = 9 translators. A shared IR needs 3 + 3 = 6 components: three front ends and three back ends.
IRs may be high level, such as syntax trees, medium level, such as TAC, or low level, close to machine instructions. GATE usually tests the middle level.
Three-address code: the complete instruction set
In three-address code, or TAC, each instruction has at most one operator on the right. The general binary form is x = y op z. The compiler creates temporaries such as t1 and t2 for intermediate results.
Know these standard forms:
Binary assignment:
x = y op zUnary assignment:
x = op yCopy:
x = yJumps:
goto Landif x relop y goto LIndexed access:
x = y[i]andx[i] = yAddress and pointer operations:
x = &y,x = *y, and*x = yProcedures:
param x,call p, n, andreturn y
Control-flow booleans normally become short-circuit jumps, not a temporary containing 0 or 1. That difference is a common exam trap.
Worked example 1: TAC, quadruples, triples, and indirect triples
Translate a = b * -c + b * -c from left to right. Unary minus is an operator, so it gets its own instruction each time.
t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5This gives 6 instructions and 5 temporaries. A quadruple records (op, arg1, arg2, result):
Row | op | arg1 | arg2 | result |
|---|---|---|---|---|
(0) | minus | c | - | t1 |
(1) | * | b | t1 | t2 |
(2) | minus | c | - | t3 |
(3) | * | b | t3 | t4 |
(4) | + | t2 | t4 | t5 |
(5) | = | t5 | - | a |
Triples refer to results by row number, so they do not need named temporaries:
Row | op | arg1 | arg2 |
|---|---|---|---|
(0) | minus | c | - |
(1) | * | b | (0) |
(2) | minus | c | - |
(3) | * | b | (2) |
(4) | + | (1) | (3) |
(5) | = | a | (4) |
An indirect triple adds a separate list: 35 -> (0), 36 -> (1), 37 -> (2), 38 -> (3), 39 -> (4), and 40 -> (5). Named results make quadruples easy to move. Triple row references can break when rows move. Indirect triples restore reorderability by moving pointers instead of rows.
Worked example 2: common subexpressions, DAG, and temporary counting
Consider x = (a + b) * (c + d) - (a + b) / e. A naive translation is:
t1 = a + b
t2 = c + d
t3 = t1 * t2
t4 = a + b
t5 = t4 / e
t6 = t3 - t5
x = t6That is 7 instructions and 6 temporaries, with a + b computed twice. A directed acyclic graph, or DAG, shares one node for both uses. Re-emitting gives:
t1 = a + b
t2 = c + d
t3 = t1 * t2
t4 = t1 / e
t5 = t3 - t4
x = t5The optimised form has 6 instructions and 5 temporaries, saving one of each. The DAG has 5 leaves, a, b, c, d, and e, plus 5 interior nodes: two +, one *, one /, and one -. Variable x labels the minus node and is not another operator node.
From grammar to code: syntax-directed translation and control flow
Syntax-directed translation attaches E.place and E.code to grammar symbols. For E -> E1 + E2, set E.place = newtemp(), then generate E.place = E1.place + E2.place. The code attribute is a concatenation, E.code = E1.code || E2.code || gen(E.place '=' E1.place '+' E2.place), which is why instructions come out in the order the subexpressions were reduced: both operands are already computed before the row that combines them.
Control flow uses labels and jumps. For while (a < b) x = x + 1, generate:
L1: if a < b goto L2
goto L3
L2: t1 = x + 1
x = t1
goto L1
L3: (next statement)The condition is at L1, the body at L2, the exit at L3, and goto L1 closes the loop. In one pass the goto L3 target is still unknown at the moment that jump is emitted, so backpatching puts the incomplete instruction on a list and writes L3 into it once the loop body has been generated.
Traps that cost marks
Forgetting the unary-minus temporary. Writing
t1 = b * -cuses two operators. Generateminus cfirst. In example 1, the two minus instructions account for two of the five temporaries.Mixing triples and quadruples. Row-number operands such as
(1)signal triples. A named result column signals quadruples.Computing every boolean into a temporary.
t1 = a < b; if t1 goto Lis numeric translation. Standard control-flow translation jumps directly withif a < b goto L2. Follow any convention fixed by the question, otherwise use jump-based translation.Ignoring common subexpressions. For the minimum number of temporaries, build the DAG first. Example 2 falls from six to five. For a fixed scheme, count its output, not the optimum.
How GATE and interviews test intermediate code generation
GATE questions ask you to convert an expression and count instructions or temporaries, identify a quadruple or triple row, count DAG nodes, or fill a syntax-directed action. All four reduce to the same three habits: allow one operator per instruction, give unary minus its own row, and build the DAG before counting anything.
Intermediate code generation appears under Compiler Design in the official GATE CS syllabus from the organising institute. For another attempt, check that cycle's official portal. Interviews use TAC to test what happens between parse tree and assembly, while DAG-based common subexpression elimination leads into optimisation. The usual interview version is why a compiler does not emit assembly straight from the parse tree, and the answer is six components rather than nine translators, plus the fact that machine-independent optimisation has nowhere to run until the IR exists.
The short version, and where to go next
IR separates front ends from back ends. TAC allows one operator per instruction. Quadruples name results, triples number them, and indirect triples point to them. DAGs share repeated subexpressions and can reduce both instructions and temporaries. Control flow normally becomes jumps rather than boolean temporaries.
Redo both worked examples from a blank page, then practise conversion questions under time. Use GATE Guidance by Sanchit Sir for structured preparation and the GATE Test Series: Mocks and Topic-wise Tests for timed practice. The Syntax-Directed Translation and Code Optimization guide carries the attribute rules further and covers the local optimisations that run on this IR.
