CSE4129: Formal languages and Compilers
Three Address Code
In the analysis-synthesis model of a compiler, the front end analyzes a source
program and creates an intermediate representation, from which the back end
generates target code.
The two most important intermediate representations are:
Trees, including parse trees and (abstract) syntax trees.
Linear representations, especially “three-address code”.
In the three-address code, the given expression is broken down into several separate
instructions.
In this kind of instructions, at most three addresses can be used.
There is at most one operator on the right side of an instruction.
General Form:
x = y op z
where x, y and z are addresses and op is a binary operator.
Example: A source-language instruction like x+y*z might be translated into the
sequence of three-address instructions:
t1 = y * z
t 2 = x + t1
where t1 and t2 are compiler-generated temporary names.
An address can be one of the following:
A name (source-program names).
A constant.
A compiler-generated temporary.
Common three-address instruction forms:
o Assignment Instructions:
x = y op z, where op is a binary operator and x, y, z are addresses.
x = op y, where op is a unary operator.
o Copy Instructions: x = y, where x is assigned the value of y.
o Unconditional Jump: goto L. The three-address instruction with label L is the
next to be executed.
o Conditional Jumps:
if x goto L: This instruction executes the instruction with label L next
if x is true.
if False x goto L: This instruction executes the instruction with label L
next if x is false.
CSE4129: Formal languages and Compilers
if x relop y goto L: This instruction executes the instruction with label
L next if x stands in relation relop to y.
Otherwise, the following three-address instruction in sequence is executed next,
as usual.
o Procedure Calls and Returns:
param x for parameters.
call p, n and y = call p, n for procedure calls.
return y, where y, representing a returned value, is optional.
o Index Copy Instructions:
x = y[i]: This instruction sets x to the value in the location i memory
units beyond location y.
x[i] = y: This instruction sets the contents of the location i units
beyond x to the value of y.
o Address and Pointer Assignments:
x = &y
x = *y
*x = y
Examples:
1. x = a + b * c + d
2. –(a * b) + (c+d)-(a+b+c+d)
3. If a<b then a=3 else b=2
4. i=2;
j=1;
for( ; i<5; i++){
j++;
}
Implementation of Three Address Code:
There are 3 representations of the three-address code namely:
1. Quadruples
2. Triples
3. Indirect Triples
Quadruples:
It is a structure with 4 fields namely op, arg1, arg2 and result.
Example: a = b * -c + b * -e
CSE4129: Formal languages and Compilers
t1 = uminus c
t2 = b * t1
t3 = uminus e
t4 = b * t3
t5 = t2 + t4
a = t5
# Op Arg1 Arg2 Result
(0) uminus c t1
(1) * b t1 t2
(2) uminus e t3
(3) * b t3 t4
(4) + t2 t4 t5
(5) = t5 A
Triples:
This representation doesn’t make use of extra temporary variable to represent a single operation
instead when a reference to another triple’s value is needed, a pointer to that triple is used. So, it
consists of only three fields namely op, arg1 and arg2.
# Op Arg1 Arg2
(0) uminu c
s
(1) * b (0)
(2) uminu e
s
(3) * b (2)
(4) + (1) (3)
(5) = a (4)
Indirect Triples:
This representation makes use of pointer to the listing of all references to computations which is
made separately and stored.
# Op Arg1 Arg2 # Statement
(14) uminu c (0) (15)
s (1) (14)
(15) * b (14) (2) (16)
(16) uminu e (3) (17)
s (4) (18)
(17) * b (16) (5) (19)
(18) + (15) (17)
(19) = a (18)
CSE4129: Formal languages and Compilers
