Experiment No.
7
Implementation of Intermediate Code Generation (ICG)
Date of Performance:21/3/2025
Date of Submission:28/3/2025
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
Aim: Implementation of Intermediate Code Generation (ICG)
Objective: To develop an ability to apply and develop Intermediate Code representation
techniques in Compiler construction.
Theory:
In the analysis-synthesis model of a compiler, the front end of a compiler translates a source
program into an independent intermediate code, and then the back end of the compiler uses
this intermediate code to generate the target code.
The benefits of using machine independent intermediate code are:
● Because of the machine independent intermediate code, portability will be enhanced.
For ex, suppose, if a compiler translates the source language to its target machine
language without having the option for generating intermediate code, then for each
new machine, a full native compiler is required. Because, obviously, there were some
modifications in the compiler itself according to the machine specifications.
● Retargeting is facilitated.
● It is easier to apply source code modification to improve the performance of source
code by optimizing the intermediate code.\
● If a compiler translates the source language to its target machine language without
having the option for generating intermediate code, then for each new machine, a full
native compiler is required.
● Intermediate code eliminates the need of a new full compiler for every unique
machine by keeping the analysis portions same for all the compilers.
● The second part of compiler, synthesis, is changed according to the target machine.
The following are commonly used intermediate code representation:
1. Postfix Notation –
The ordinary (infix) way of writing the sum of a and b is with operator in the middle: a + b
The postfix notation for the same expression places the operator at the right end as ab +. In
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
general, if e1 and e2 are any postfix expressions, and + is any binary operator, the result of
applying + to the values denoted by e1 and e2 is postfix notation by e1e2 +. 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. In postfix notation the operator
follows the operand.
Example – The postfix representation of the expression (a – b) * (c + d) + (a – b) is : ab –
cd + *ab -+.
2. Three-AddressCode
A statement involving no more than three references (two for operands and one for
result) is known as three address statement. A sequence of three address statements is
known as three address code. Three address statement is of the form x = y op z , here
x, y, z will have address (memory location). Sometimes a statement might contain less
than three references, but it is still called three address statement.
Example – The three-address code for the expression a + b * c + d:
T 1 = b * c
T 2 = a + T 1
T3=T2+d
T 1, T 2, T 3 are temporary variables.
3. Quadruples
Each instruction in quadruples presentation is divided into four fields: operator, arg1, arg2,
and result. The above example is represented below in quadruples format:
Op arg1 arg2 result
* c d r1
+ b r1 r2
+ r2 r1 r3
= r3 a
4. Triples
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
Each instruction in triples presentation has three fields : op, arg1, and arg2.The results of
respective sub-expressions are denoted by the position of expression. Triples represent
similarity with DAG and syntax tree. They are equivalent to DAG while representing
expressions.
Op arg1 arg2
* c d
+ b (0)
+ (1) (0)
= (2)
Triples face the problem of code immovability while optimization, as the results are
positional and changing the order or position of an expression may cause problems.
5. Indirect Triples
This representation is an enhancement over triples representation. It uses pointers instead of
position to store results. This enables the optimizers to freely re-position the sub-expression
to produce an optimized code.
6. Syntax Tree
Syntax tree is nothing more than condensed form 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 single link in syntax tree the internal nodes are operators and child nodes are
operands. To form syntax tree put parentheses in the expression, this way it's easy to
recognize which operand should come first.
This representation is an enhancement over triples representation. It uses pointers instead of
position to store results. This enables the optimizers to freely re-position the sub-expression
to produce an optimized code.
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
Example –
x = (a + b * c) / (a – b * c)
Note: students need to implement at least two ICG for given input statement.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
// Function to return precedence of operators
int prec(char c) {
if (c == '^')
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
// Function to perform infix to postfix conversion
void infixToPostfix(char* exp, char* postfix) {
int len = strlen(exp);
char stack[len];
int j = 0, top = -1;
for (int i = 0; i < len; i++) {
char c = exp[i];
if (isalnum(c))
postfix[j++] = c; // Operand to output
else if (c == '(')
stack[++top] = '(';
else if (c == ')') {
while (top != -1 && stack[top] != '(')
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
postfix[j++] = stack[top--];
top--;
} else {
while (top != -1 && prec(c) <= prec(stack[top]))
postfix[j++] = stack[top--];
stack[++top] = c;
while (top != -1)
postfix[j++] = stack[top--];
postfix[j] = '\0';
// Function to generate Three-Address Code
void generateTAC(char* postfix) {
char stack[100][10];
int top = -1, tempVarCount = 1;
printf("\nThree-Address Code:\n");
for (int i = 0; postfix[i] != '\0'; i++) {
char c = postfix[i];
if (isalnum(c)) {
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
char operand[2] = {c, '\0'};
strcpy(stack[++top], operand);
} else {
char op2[10], op1[10], tempVar[10];
strcpy(op2, stack[top--]);
strcpy(op1, stack[top--]);
sprintf(tempVar, "T%d", tempVarCount++);
printf("%s = %s %c %s\n", tempVar, op1, c, op2);
strcpy(stack[++top], tempVar);
int main() {
char exp[] = "A+B*C-D/E";
char postfix[100];
printf("Infix Expression: %s\n", exp);
infixToPostfix(exp, postfix);
printf("Postfix Expression: %s\n", postfix);
generateTAC(postfix);
return 0;
CSL601: System Programming and Compiler Construction Laboratory
Vidyavardhini’s College of Engineering & Technology
Department of Computer Engineering
Output:
Input Expression: A+B*C-D/E
Postfix Expression: ABC*+DE/-
Three-Address Code:
T1 = B * C
T2 = A + T1
T3 = D / E
T4 = T2 - T3
Conclusion:
The Intermediate Code Representation (ICR) simplifies complex expressions into
sequential Three-Address Code (TAC) using temporary variables. It ensures correct
operator precedence and helps in optimization techniques like constant folding and common
subexpression elimination. This structured format makes code translation and execution more
efficient in compilers.
CSL601: System Programming and Compiler Construction Laboratory
