Intermediate Code
Generation
Tutorial 08
CSCI415 – Compiler Design
What is Intermediate Code Generation?
➢ It is a step between high level language and machine
language.
➢ Used to help translate source code into a machine code.
➢ Takes input from the semantic phase in the form of annotated
parse tree.
CSCI415 – Compiler Design
Intermediate Representation (IR)
High Level IR Low Level IR
CSCI415 – Compiler Design
1. Very close to the source language.
2. Can be easily generated from the source
code and can easily apply code modifications
to enhance performance.
High Level IR
3. Less Preferred for target machine
optimization.
CSCI415 – Compiler Design
Intermediate code can be either language specific
1. Very close to the target machine (e.g., Byte Code for Java) or language independent
(three-address code).
language.
2. Suitable for register and memory
allocation, instruction set selection, etc. Low Level IR
3. Good for machine-dependent
optimizations.
CSCI415 – Compiler Design
Methods of IR
1) Postfix Notation
2) Three-Address Code
3) Syntax Tree
CSCI415 – Compiler Design
Postfix Notation
● Infix expressions are easily readable and solvable by humans whereas the
computer cannot differentiate the operators and parenthesis easily so, it is
better to convert the expression to postfix(or prefix) form before evaluation.
● It is a low-level IR
● No parentheses are needed in postfix notation because the position and arity
(number of arguments) of the operators permit only one way to decode a postfix
expression.
CSCI415 – Compiler Design
How to Convert to Postfix Notation?
1. Initialize an empty stack and an empty output string.
2. Scan the infix expression from left to right.
3. If the element is an operand, add it to the output.
4. If the element is a '(', push it onto the stack.
5. If the element is a ')', pop from the stack and add to output until '(' is
encountered.
6. If the element is an operator, pop from the stack all operators with higher
or equal precedence, then push the current operator.
7. After scanning, pop all remaining operators from the stack.
CSCI415 – Compiler Design
Operator Precedence Table
Operator Meaning Precedence
() Parentheses Highest
^% Exponentiation / Modulus 2
*/ Multiplication / Division 3
+- Addition / Subtraction 4 (Lowest)
Note: Higher precedence means the operation will happen first. When
operators have equal precedence, they are evaluated left-to-right (except
for exponentiation which is right-to-left).
CSCI415 – Compiler Design
Postfix Notation
Let’s convert these infix expressions to postfix
Infix Postfix
● a+b ● ab+
● (a+b)*c ● ab+c*
● (a – b) * (c + d) + (a – b) ● ab-cd+*ab-+
● a+b*c+d ● abc*+d+
Postfix Notation using Stack | Learn Postfix Evaluation in DSA with Code in JS, C, Python, Java
CSCI415 – Compiler Design
Three-Address Code
● It is a low-level IR
● A statement involving no more than three references (two for operands and one
for result) is known as a three-address statement.
● Three address statement is of form x = y op z, where x, y, and z will have
address (memory location).
● There are 3 ways to represent a Three-Address Code in compiler design:
○ Quadruples
○ Triples
○ Indirect Triples
CSCI415 – Compiler Design
Three-Address Code
Quadruples
It is a structure which consists of 4 fields namely op, arg1, arg2 and result. op
denotes the operator and arg1 and arg2 denotes the two operands and result is
used to store the result of the expression.
Advantage:
● Easy to rearrange code for global optimization.
● One can quickly access value of temporary variables using symbol table.
Disadvantage:
● Contain lot of temporaries.
● Temporary variable creation increases time and space complexity.
CSCI415 – Compiler Design
Three-Address Code
Example
Convert the expression ‘a = b * -c + b * -c’ into a quadruple.
Op Arg1 Arg2 Result
- (uniary minus) c T1
* b T1 T2
- (uniary minus) c T3
* b T3 T4
+ T2 T4 T5
= a T5 T6
CSCI415 – Compiler Design
Syntax Tree
● It is a high level IR
● It is a from of a parse tree.
● The operator and keyword nodes of the parse tree are moved to their parents,
and a chain of single productions is replaced by the single link in the syntax tree
the internal nodes are operators and child nodes are operands.
● There are 2 types of syntax trees, Abstract Syntax Tree (AST) and Directed
Acyclic Graph (DAG).
● Directed Acyclic Graph (DAG) is commonly used to represent the control flow and data
dependencies of a program. This representation is often used as an intermediate
representation (IR) that facilitates program optimization and transformation.
CSCI415 – Compiler Design
AST
Example =
Consider expression x = (a + b * c) / (a – b * c).
Construct the abstract syntax tree. x /
+ –
x = (a + (b * c)) / (a – (b * c))
a * a *
To form a syntax tree put parentheses in the
expression, this way it’s easy to recognize which
operand should come first. b c b c
CSCI415 – Compiler Design
AST & DAG
Example
Consider expression = DAG = AST
x = (a + b * c) / (a + b * c).
Construct the AST and DAG for
this expression. x / x /
+ + +
x = (a + (b * c)) / (a + (b * c))
a * a * a *
b c b c b c
CSCI415 – Compiler Design
Thank
You