Inermediate Code Generation
Intermediate Code Generation
• After performing Semantic Analysis on the parse tree, the compiler
converts the translated parse tree into the intermediate language.
• Intermediate code is generated because it is not possible for compiler to
generate machine code directly in one pass.
• So, first it converts source program into intermediate code, which
performs efficient generation of machine code further.
Intermediate code
Parse Tree
Intermediate Code Generation
With translation
If we divide the compiler stages into two parts i.e. front end and back end, then
intermediate code generation phase comes in between
Back End
Front end
Intermediate Machine
Lexical Syntax Code
code
Analysis Analysis Generator code
Generation
Intermediate
code
Advantages
• It is Machine Independent. So can be executed on different
platforms
• It makes the task of code optimization easy.
• Performs efficient code generation.
Types of Intermediate code Generation
• Postfix Notation
• Syntax Tree
• Three Address Code
– Quadruples
– Triples
– Indirect Triples
Postfix Notation
• The operator appear after the operands
(a+b) -------- ab +
Postfix Notations
• Jump : Jump to label L can be written in postfix notation as
L Jump
• Jlt ( Jump if less than) : e1 e2 L jlt makes jump to L if e1 has
smaller value to e2.
• Jeqz (jump if equal to zero) : e L jeqz causes jump to L if e has
the value zero.
• If e then
• x
• Else
• L1 : y
• L2 : exit
• If a then
• if c+d then
• a+c
• else
• L1 : a*c
• Else
• L2 : a+b
• L3 : exit
Parse Tree and Syntax Tree
• Parse trees and Syntax Trees are also very useful way to
represent intermediate code.
• Syntax Trees : A tree in which each leaf node represents an
operand and each interior node an operator.
• Syntax Tree is condensed form of the parse tree.
x=y–z*3
Difference between parse tree and syntax tree
Parse Tree Syntax Tree
It can contain operators & It contains operands at leaf
operands at any node of tree node & operators at interior
i.e. either interior node or leaf nodes of Tree
node
It contains duplicate It does not contain any
information duplicate information
Parse Tree can be changed to Syntax Tree cannot be changed
Syntax tree by elimination of to Parse Tree.
duplicate information
E
+
E + E
*
3
E * E Digit(3) 1 2
Digit(1) Digit (2)
Parse Tree for 1 * 2 + 3 Syntax Tree for 1 * 2 + 3
Production Semantic Action
E -> E(1) + E(2) {[Link]= Node (+, E(1).VAL, E(2).VAL}
E -> E(1) * E(2) {[Link]= Node (*, E(1).VAL, E(2).VAL}
E -> (E(1)) {[Link]= E(1).VAL}
E -> -E(1) {[Link]= Unary (-, E(1).VAL}
E -> id {[Link]= Leaf (id)}
Three Address Code
• This is most important way of representing intermediate code.
• In three address code, at most three addresses are used to
represent any statement.
• Two addresses for operand & one for result.
e.g. a = b + c + d
T1= b+c
T2 = T1+d
a = T2
Representation of Three Address Statements
• Quadruples
• Triples
• Indirect Triples
Quadruples
• Quadruples is a structure which contains at most four fields i.e.
operator, argument1, argument2 and result.
Operator Argument1 Argument2 Result
e.g. a = b+c*d -> t1 = c*d, t2= b+t1, a=t2
Operator Arg1 Arg2 Result
2
Triples
• This three address code representation contain three fields i.e.
one for operator and two for arguments
Operator Argument1 Argument2
• e.g. a = b+c*d
• t1 = c*d
• t2= b+t1
• a=t2
Operator Arg1 Arg2
(0)
(1)
(2)
Indirect Triples
• In direct triples, all the pointers used in triples are indexed such
that one pointer will reference another pointer.
• e.g. a = b+c*d
• t1 = c*d
• t2= b+t1
• a=t2
Statement Operator Arg1 Arg2
Example-2
• -(a+b) * (c+d) – (a+b+c)
• Quadruples
Operator Arg1 Arg2 Result
5
• Triples
Operator Arg1 Arg2
5
• Indirect Triples
Statement Operator Arg1 Arg2
5
Assignment statements with Mixed types
• Identifiers can be of different types.
• Before generating three address code for mixed expression, It becomes necessary to
achieve type compatibility between sub-expression.
e.g. z=a+b*c-d
Where a, z are real no’s and b, c, d are integer no’s
T1=b int *c
T2 = t1 int – d
T3 = inttoreal T2
T4 = a real + T3
z = T4
Assignment Statements
Boolean Expressions
• Boolean means ture or false.
• It can also be represented by 1 or 0.
• Boolean expression are the expression which return true or
false.
• Boolean expressions can be represented in two ways :
– Conditional expressions
– Logical expressions : AND, OR and NOT
Control Statements
• Control statements are the statements which change the flow
of execution of statements.
• For example : if, if-else, Switch case, while-do statements
Assignment Statements
Boolean Expression
Boolean Expression
Boolean Expression
Control Statement
Control Statement
Control Statement
Case Statement