Compiler Design
Chapter 5: Intermediate Code Generation
Instructor: Fikru Tafesse (MSc.)
Email: fikrish2012@[Link]
Page 1
Introduction
• The task of compiler is to convert the source program into machine program.
• This activity is done directly, but it is not always possible to generate such a
machine code directly in one pass.
• Then, typically compilers generate as easy to represent form of source language
called intermediate language.
• An Intermediate Representation (IR) is a language for an abstract machine (or a
language that can be easily evaluated by an abstract machine)
• The generation of an intermediate language leads to efficient code generation.
Page 2
Benefits of Intermediate Code Generation
• There are certain benefits of generating machine independent intermediate code.
1.A compiler for different machines can be created by attaching different back end
to existing front end of each machine.
2.A compiler for different source language (on the same machine) can be created
by proving different front ends for corresponding source languages to existing
back end.
3.A machine independent code optimizer can be applied to intermediate code in
order to optimize code generation.
Page 3
Intermediate Code
• 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.
• 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.
• 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.
• Intermediate code generator receives input from its predecessor phase and semantic analyzer phase.
• It takes input in the form of an annotated syntax tree.
• Using the intermediate code, the second phase of the compiler synthesis phase is changed according
4
to the target machine.
Page 4
Cont'd ...
• Intermediate code can be represented in two ways:
1. High level Intermediate Code
It can be represented as source code.
2. Low level cede intermediate code
It is close to the target machine.
It is used for machine independent optimization.
• The different forms of intermediate code are
a. Abstract Syntax Tree (AST)
b. Polish Notation
c. Three Address Code (TAC)
5
Page 5
Cont'd ...
a. Abstract Syntax Tree (AST)
• AST are more compact than a parse tree and can be easily used by compiler.
• Example: consider the input string a * b + c
*
a
+
b c
Parse Tree for a*b+c
AST representation for a*b+c
b. Polish Notation can be :
• Infix a+b
• Prefix +ab
• Postfix ab+
• Postfix notation is a linear representation of syntax tree.
• Example: x+y => xy+ 6
Page 6
Cont'd ...
• The Posix notation is used to using postfix representation.
Productions Semantic Rule
E → E1+E2 [Link] = [Link] | [Link] | +
E→(E1) E,Val = [Link]
E→ id [Link] = id
• Example X = (A - B) * (C - D) + (E+(F/G))
• Solution: X = AB - * CD - + (E+FG/)
X = AB - * CD - + EFG/ +
X = AB - CD - * EFG/ + + Postfix Notation
Page 7
Cont'd ...
Three address code (TAC)
• Common intermediate representation of a program.
• It is used by an optimizing compiler.
• In three address code, the given expression is broken down into several separate
instructions.
• These instructions can be easily translated into Assembly Language.
• Each three-address code instruction has at most three operands.
• It is a combination of assignment and a binary operator.
• In TAC, there is at most one operator on the right side of an instruction.
• Each assignment instruction can have only one operator.
Page 8
Cont'd ...
Example1:
x+y*z • t1 and t2 are compiler generated temporary names.
t1=y*z
t2=x+t1
• Instruction may be implemented as objects or as records.
• Example2: a+a*(b-c) +d*(b-c)
t1 = b-c
t2 = a* t1
t3 = a+ t2
t4 = d+ t1
t5 = t3 + t4
Three address code can be classified into two: Quadruples and Triples
9
Page 9
Cont'd ...
1. Quadruples: has four Fields such as operator, source1, source2, result(destination).
Example: a := -b * c + d
TAC: t1 = -b
t2 = c + d
t3 = t1 * t2
a := t3
Reference Operator Source1 Source2 result
(0) Uminus b - t1
(1) + c d t2
(2) * t1 t2 t3
(3) := t3 - a
10
Page 10
Cont'd ...
[Link]: has three fields such as operator, source1 and source2.
Example: a := -b * c + d
TAC: t1 = -b
t2 = c + d
t3 = t1 * t2
a := t3
Reference Operator Source1 Source2
(0) - b -
(1) + c d
(2) * (0) (1)
(3) := (2) -
11
Page 11
Cont'd ...
Common Three-Address Instruction Forms
1. Assignment
• Example: x = y op z
where op is a binary arithmetic or logical operation, and x, y, and z are addresses.
x = op y
where op is a unary operation.
2. Copy
• Example: x=y
where x is assigned the value of y
3. Unconditional jump
• where the three-address instruction with
• Example: goto L label L is the next to be executed
12
Page 12
Cont'd ...
4. Conditional jumps
• Example: if x goto L
These instructions execute the instruction with label L next if x is true
if x reop y goto L
which apply a relational operator to x and y
5. Procedure calls
• Example: call p
return y 7. Address and pointer assignments
6. Indexed copy instructions • Example: x=&y
x = *y
Example : x = y[i] *x = y
x[i] = y
13
Page 13
Cont'd ...
End!!!
Thank You!!!
14
Page 14