CSC 408 – COMPILER CONSTRUCTION II

TOPIC: INTERMEDIATE CODE GENERATION

QUESTION 1:

What is the role of intermediate code generation in the entire compilation process?
Convert the following into three address code.

a+(b-c) *d

ANSWER:

Intermediate code is used to translate the source code into the machine code.
Intermediate code lies between the high-level language and the machine
language. The given program in a source language is converted into an equivalent
program in an intermediate language by the intermediate code generator.
Intermediate codes are machine independent codes.

Roles of Intermediate code are:

o It acts as a glue between front-end and backend (or source and machine
codes).
o If the compiler directly translates source code into the machine code without
generating intermediate code, then a full native compiler is required for each
new machine.
o The intermediate code keeps the analysis portion same for all the compilers
that's why it doesn't need a full compiler for every unique machine.
o Intermediate code generator receives input from its predecessor phase and
semantic analyzer phase. It takes input in the form of an annotated syntax
tree.

1
 o Using the intermediate code, the second phase of the compiler synthesis
phase is changed according to the target machine.
o Intermediate code generator lowers abstraction from source level.
o Complete some syntactic checks, perform more semantic checks. For e.g.,
break should be inside loop or switch only.

The intermediate code representation include:

• Graphical representation e.g., Syntax Tree, DAGS

• Postfix notations
• Three Address codes

Given expression:

a+(b-c) *d

Converting it into three address code:

t1 = b-c

t2 = t1*d

t3 = a+t2

For given expression the quadruples is:

op arg1 arg2 result

(0) - b c t1
(1) * t1 d t2
(2) + a t2 t3

For given expression, the triples is:

op arg1 arg2
(0) - b c
(1) * (0) d
(2) + a (1)

2
QUESTION 2:

Define three address codes. Write three address code for

a = -b*(c+d)

ANSWER:

The address code that uses at most three addresses, two for operands and one for
result is called three address code. Each instruction in three address code can be
described as a 4-tuple: (operator, operand1, operand2, result).

Given expression

a = -b*(c+d)

The three address code of the expression is given below:

t1 = -b

t2 = c + d

t3 = t1 * t2

a = t3

QUESTION 3:

Explain with example about different methods of intermediate code representation.

ANSWER:

The given program in a source language is converted into an equivalent program in

an intermediate language by the intermediate code generator. Intermediate codes
are machine independent codes. There are three kinds of intermediate
representations:

• Graphical representation (Syntax tree or DAGs)

• Postfix notations
• Three Address codes

3
Syntax Tree

Syntax tree is a graphic representation of given source program and it is also called
variant of parse tree. A tree in which each leaf represents an operand and each
interior node represents an operator is called syntax tree. For e.g., Syntax tree for
the expression a+b*c-d/(b*c)

Directed Acyclic Graph (DAG)

A DAG for an expression identifies the common sub expressions in the expression.
It is similar to syntax tree, only difference is that a node in a DAG representing a
common sub expression has more than one parent, but in syntax tree the common
sub expression would be represented as a duplicate sub tree. For e.g. DAG for the
expression a+b*c-d/(b*c)

Postfix Notation

4
The representation of an expression in operators followed by operands is called
postfix notation of that expression. In general if x and y be any two postfix
expressions and OP is a binary operator then the result of applying OP to the x and
y in postfix notation by "x y OP". For e.g. (a+ b) * c in postfix notation is: a b + c *

Three Address Code

The address code that uses at most three addresses, two for operands and one for
result is called three address code. Each instruction in three address code can be
described as a 4-tuple: (operator, operand1, operand2, result).

A quadruple (Three address code) is of the form: x = y op z where x, y and z are

names, constants or compiler-generated temporaries and op is any operator.

For e.g.

The three-address code for a+b*c-d/(b*c)

QUESTION 4:

How can you generate three-address code?

ANSWER:

The three-address code is generated using semantic rules that are similar
to those for constructing syntax trees for generating postfix notation.

QUESTION 5:

What is a syntax tree? Draw the syntax tree for the assignment
statement a := b* -c + b * -c.

ANSWER:
5
 A syntax tree depicts the natural hierarchical structure of a source program.

Syntax tree:

QUESTION 6:

What is postfix notation? and why is “Three address code” named so?

ANSWER:

• A Postfix notation is a linearized representation of a syntax tree. It is a list of

nodes of the tree in which a node appears immediately after its children.
• The reason for the term “Three address code” is that each usually contains
three addresses, two for operands and one for the result.

QUESTION 7:

Define three-address code.

ANSWER:

Three-address code is a sequence of statements of the general form

x := y op z

6
 where x, y and z are names, constants, or compiler-generated temporaries;
op stands for any operator, such as fixed or floating-point arithmetic
operator, or a logical operator on boolean-valued data.

Three-address code is a linearized representation of a syntax tree or a dag in

which explicit names correspond to the interior nodes of the graph.

QUESTION 8:

What are triples?

ANSWER:

The fields arg1,and arg2 for the arguments of op, are either pointers to the
symbol table or pointers into the triple structure then the three fields used in
the intermediate code format are called triples.

· In other words the intermediate code format is known as triples.

QUESTION 9:

Draw the DAG for a := b * -c + b * -c

ANSWER:

7
QUESTION 10(a):

List the types of three address statements.

ANSWER:

The types of three address statements are

a. Assignment statements
b. Assignment Instructions
c. Copy statements
d. Unconditional Jumps
e. Conditional jumps
f. Indexed assignments
g. Address and pointer assignments
h. Procedure calls and return

QUESTION 10(b):

What are the various methods of implementing three-address statements?

ANSWER:

i. Quadruples
ii. Triples
iii. Indirect triples