Previous Year Questions: Intermediate Code Generation | Compiler Design - Computer Science Engineering (CSE) PDF Download

Q1: Consider the following expression: x [ i ] = ( p + r ) ∗ − s [ i ] + u / w x. The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6).  (2024 SET 2)
Which one of the following options fills in the missing entries CORRECTLY?
(a) (1) = [] s i =[]si , (3) * (0) (2) , (6) [] = x i
(b) (1)  [] = s i =[]si , (3) - (0) (2) , (6) [] = x (5)
(c) (1) = [] s i =[]si , (3) * (0) (2) , (6) [] = x (5)
(d)  (1)  [] = s i =[]si , (3) - (0)(2) , (6) [] = x i
Ans: (a)
Sol: Explanation: Going from left to right we resolve the brackets first. (p+r) is already given, now we solve s[i]. then comes unary minus as per operator preference. Then we solve * which acts between 0 & 2 (B & D eliminated) and / , + subsequently. Then x[i] address is calculated(step 6) where the final result (obtained in step 5) is stored in the last step (7). The assignment operator has lowest preference so it is done at last.
A is the correct answer.

Q2: Consider the following pseudo-code.  (2024 SET 1)
L1: t1= -1
L2: t2 = 0
L3: t3 = 0
L4: t4 = 4* t3
L5: t5=4t2
L6: t6t5*M
L7: t7=t4+t6
L8: t8 = a[t7]
L9: if t8 <= max goto L11
L10: t1= t8
L11: t3t3 +1
L12: if t3 < M goto L4
L13: t2t2 +1
L14: if t2< N goto L3
L15: max = t1
Which of of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?
(a) 6 and 6
(b) 6 and 7
(c) 7 and 7
(d) 7 and 6
Ans: (d)
Sol: Basic block: The collection of 3AC statements from the leader to the next leader without including the next leader is known as the basic block.
Steps to find the basic blocks:

• Identify the leader first. (The first statement of 3AC is the leader.)
• The address of conditional, unconditional goto is the leader. (target location of goto)
• immediate next line of goto is the leader.

Now construct the basic block from leader to line before the next leader.
In the given 3AC 7 leaders are there: 1, 3, 4, 10, 11, 13, 15
There are 7 basic block are there:
1. Block B₁ : statement 1 − 2
2. Block B₂ : statement 3
3. Block B₃ : statement 4 − 9
4. Block B₄ : statement 10
5. Block B₅ : statement 11 − 12
6. Block B₆ : statement 13 − 14
7. Block B₇ : statement
So the total number of basic blocks is 7 and the largest basic block is B₃ which contains a total of 6 instruction.
Correct option is  (D)

Q3: Consider the following statements regarding the front-end and back-end of a compiler.  (2023) 
S1: The front-end includes phases that are independent of the target hardware.
S2: The back-end includes phases that are specific to the target hardware.
S3: The back-end includes phases that are specific to the programming language used in the source code.
Identify the CORRECT option.
(a)  Only S1 is TRUE.
(b) Only S1 and S2 are TRUE.
(c) S1, S2, and S3 are all TRUE.
(d) Only S1 and S3 are TRUE.
Ans: (b)
Sol:  A compiler is a program that takes as input a program written in one language (the source language) and translates it into a functionally equivalent program in another language (the target language) without changing the meaning of the code.
Compiler process goes through lexical, syntax, and semantic analysis at the front end, and code generation and optimization at a back-end.
Front end and Back end of compiler:

The front end of a compiler is the part that takes the source language and produces an intermediate representation. This stage of compilation aims to detect any programmatic errors with the source code. It does this by performing lexical analysis, parsing (or syntax analysis) and semantic analysis. The output of the front end is an intermediate representation of the code, which can be passed to the middle end. The front end is also called analysis.
The back end is designed to produce a program for a target computer from the intermediate representation. It includes the code optimization phase and final code generation phase, along with the necessary error handling and symbol table operations. Back end phase of the compiler consists of those phases which depend on the target machine and are independent of the source program.
So, answer is Option B.

Q4: In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?  (2021 SET 2)

(a) Three address code

(b) Abstract Syntax Tree (AST)

(c) Control Flow Graph (CFG)

(d) Symbol table
Ans: (d) 

Sol: Symbol table is a data structure created and maintained by compilers in order to store info about occurrences of various entities like variable names, function names, objects, classes and interface.

Various forms of intermediate representation of code include Postfix Notation, Three address code ( x = y op z), Syntax Tree, DAG.
Abstract Syntax Tree is a condensed version of syntax tree/parse tree more to with program than the compiler.
Parse Tree and Syntax Tree:

Control Flow Graph is used in optimization phase of compiler, each basic block consists of linear code, the next block to access is determined by the last instruction of the current block.

An Example,

Q5: Consider the productions A → P Q and A → X Y. Each of the five non-terminals A,P,Q,X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.  (2020)
Rule 1: P.i=A.i+2, Q.i=P.i+A.i, and A.s=P.s+Q.s
Rule 2: X.i=A.i+Y.s and Y.i=X.s+A.i
Which one of the following is TRUE?
(a) Both Rule 1 and Rule 2 are L-attributed.
(b) Only Rule 1 is L-attributed.
(c) Only Rule 2 is L-attributed.
(d) Neither Rule 1 nor Rule 2 is L-attributed
Ans: (b)
Sol: In L-attributed definitions,
1. A parent can take its attribute values from any child (which is S−attributed and Every S−attributed is also L−Attributed).
2. A child can take its attribute values from the parent as well as from any left sibling but not from any right sibling.
Based on these properties, only Rule-1 is L−attributed.
Rule-2 is failed for the production A → X Y , and definition X . i = A . i + Y . s since X take
value from its sibling Y, which is present in its right in the production.
Answer : B.

Q6: Consider the expression ( a-1)* (((b + c) / 3) + d)) . Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture in which (i) only loads and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is _________.  (2017 SET 1)
(a) 2
(b) 3
(c) 4
(d) 5
Ans: (a)
Sol:  Load R1,b
Load R2,c
ADD R1, R2
Div R1, 3
Load R2, d
Add R1, R2
Load R2, a
Sub R2, 1
Mul R2 , R1

hence minimum 2 registers required

Q7: Consider the following intermediate program in three address code  (2017 SET 1)
p= a -b
q= p *c
p= u * v
q= p + q
Which one of the following corresponds to a static single assignment form of the above code?
(a) p1=a −b
q1=p1 ∗ c
p1=u ∗ v
q1=p1 + q1
(b) p3 = a − b
q4 = p3 ∗ c
p4 = u ∗ v
q3 = p4 + q4
(c) p1 = a − b
q1 = p2 ∗ c
p3 = u ∗ v
q2 = p4 + q4
(d) p1 = a − b
q1 = p1 ∗ c
p2 = u ∗ v
q2 = p + q
Ans: (b)
Sol:  Static Single assignment:
Each assignment to a temporary is given a unique name
All of the uses reached by that assignment are renamed

So, B is ans

Q8: Consider the following code segment.  (2016  SET 1)
x =u-t;
y =x*v;
x =y+w;
y =t-z;
y =x*y;
The minimum number of total variables required to convert the above code segment to static single assignment form is__________ .
(a) 8
(b) 9
(c) 10
(d) 11
Ans: (c)
Sol: In Static Single Assignment when we assign the values, the variables to which the value is being assigned should be unique.
T1=u-t
Τ2 = 11 * U
T3=T2 + w
T4-t-z
T5 = t3 * t4
So T1... T5 + (u, t, v, w, z) = 5
Total 10 variables.
Note: RHS of the operation can use the previously used variables, but LHS in SSA must always be unique.

Q9:  Consider the intermediate code given below.  (2015 SET 2)
(1) i = 1
(2) j = 1
(3) t1 = 5 * i
(4) t2 = t1 + j
(5) t3 = 4 * t2
(6) t4 = t3
(7) a[t4] = -1
(8) j = j + 1
(9) if j≤5 goto (3)
(10) i=i+1
(11) if i <5 goto (2)
The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
(a) 5 and 7
(b) 6 and 7
(c) 5 and 5
(d) 7 and 8
Ans: (b)
Sol:

Answer is 6,7 if we add an explicit start and end nodes. This follows from the definition of CFG in the below IITM link

Q10: In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?  (2015 SET 2)
(a) In both AST and CFG, let node N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding to N1
(b) For any input program, neither AST nor CFG will contain a cycle
(c) The maximum number of successors of a node in an AST and a CFG depends on the input program
(d) Each node in AST and CFG corresponds to at most one statement in the input program
Ans: (c)
Sol: A. is false , In CFG , code of N₂ may be present before N₁ when there is a loop or Goto.
B. is false , CFG contains cycle when input program has loop.
C. is true ,successors in AST and CFG depend on Input program. D. is false, In CFG a single node may belong to a block of statements.
Option (C) is Correct

Q11: The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s - t * 5 + u * v /w is _______________.  (2015 SET 1)
(a) 6
(b) 8
(c) 9
(d) 10
Ans: (b)
Sol: In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into versions, new variables.
We will need a temporary variable for storing the result of each binary operation as SSA (Static Single Assignment) implies the variable cannot be repeated on LHS of assignment.
q + r/ 3 + s - t * 5 + u * v/ w
t1 = r/3;
t2 = t * 5;
t3 = u * v;
t4 = t3/ w;
t5=q + t1;
t6 = t5 + s;
t7=t6 - t2;
t8 = t7 + t4

Q12: A variable x is said to be live at a statement S_i  in a program if the following three conditions hold simultaneously:  (2015 SET 1)
i. There exists a statement S j  that uses x
ii. There is a path from S _i  to S _j  in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at S_i and S_{j 
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are}
(a) p, s, u
(b) r, s, u
(c) r,u
(d) q,v
Ans: (c)
Sol:  r, u.
p, and s are assigned to in 1 and there is no intermediate use of them before that. Hence p, and s are not live in both 2 and 3.
q is assigned to in 4 and hence is not live in both 2 and 3.
v is live at 3 but not at 2.
u is live at 3 and also at 2
if we consider a path of length 0 from 2−2.
So, r, u is the answer.

Q13: Consider the basic block given below.  (2014 SET 3)
a= b + c
c =a + d
d =b + c
e =d - b
a =e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are
(a) 6 and 6
(b) 8 and 10
(c) 9 and 12
(d) 4 and 4
Ans: (a)
Sol: A normal DAG construction will give 8 nodes and 10 edges as shown below.
Since, this question asks for minimum possible, we can assume algebraic simplification is allowed. So, d = b + c , e = d − b ; can be simplified to d = b + c ; e = c ; Similarly, e = d − b ; a = e + b
; can be simplified to a = d . This gives the following DAG with 6 nodes and 6 edges.

Correct Answer: A

Q14: One of the purposes of using intermediate code in compilers is to  (2014 SET 3)
(a) make parsing and semantic analysis simpler
(b) improve error recovery and error reporting
(c) increase the chances of reusing the machine-independent code optimizer in other compliers.
(d) improve the register allocation
Ans: (c)
Sol: C. that is the actual use of intermediate code generator in a compiler.

Q15: The minimum number of arithmetic operations required to evaluate the polynomial P ( x ) = x⁵ + 4 x³ + 6 x + 5 for a given value of x, using only one temporary variable is _____.  (2014 SET 3)
(a) 4
(b) 12
(c) 7
(d) 10
Ans: (c)
Sol:  P(X) = x ⁵ + 4 x ³+ 6 x + 5
= x (x⁴+ 4  x ² + 6) +5
= x(x(x³ + 4 x) + 6) + 5
= x(x(x(x² + 4)) + 6) + 5
= x(x(x(x(x) + 4)) + 6) +5
mul = pair of brackets  4
add = num of signs 3
total 7

Q16: For a C program accessing x[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.  (2014 SET 2)
t0 = i * 1024
t1 = j * 32
t2 = k * 4
t3 = t1 + t0
t4 = t3 + t2
t5 = x[t4]
Which one of the following statements about the source code for the C program is CORRECT?
(a) x is declared as "int x[32] [32] [8]".
(b) x is declared as "int x[4] [1024] [32]".
(c) x is declared as "char x[4] [32] [8]".
(d) x is declared as "char x[32] [16] [2]".
Ans: (a)
Sol: k is multiplied by 4 , means size of(data type) is int.
 j is multiplied by 32  , means the inner most dimension of array is 32/4 =8  (we have to divide by the size of the inner dimension- which here is a simple integer)
i is multiplied by 1024, means the second dimension of array is 1024/32= 32 (32 = 8 ∗ 4 is the size of the inner dimension here)
So, (A) is correct. The first dimension is not needed for code generation and that is why in C language while passing an array to a function, we can omit the value of the first dimension but not any others.
We can also do as follows:
X[i][j][k] = *(*(*(X+i)+j)+k)
In Integer arithmetic, this equals
*(*(*(X+i*sizeo f(*X)) + j*sizeo f(**X)+k* sizeo f (***X))
as for every add to a pointer we have to multiply the size of the pointed value (to get a valid address)
So, from the given code we get
sizeo f(***X) = 4, - int
sizeo f(** X) = 32-int array of size 8
sizeo f(X) = 1024-2 D int array of size [32] havinf size of inner 1D array 32.
So, the inner dimensions must be 32 and 8 and type must be integer. So, only option A matches.

Q17: Which one of the following is FALSE?  (2014 set 1)
(a) A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
(b) Available expression analysis can be used for common subexpression elimination.
(c) Live variable analysis can be used for dead code elimination
(d) x=4* 5 ⇒x =20 is an example of common subexpression elimination
Ans: (d)
Sol:
A.  A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end is TRUE.
B. Available expression analysis can be used for common subexpression elimination is TRUE. Available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Available expression analysis is used to do global common subexpression elimination (CSE). If an expression is available at a point, there is no need to re-evaluate it.
C. Live variable analysis can be used for dead code elimination is TRUE.
D. x = 4 ∗ 5 ⇒ x = 20 is an example of common subexpression elimination is FALSE. Common subexpression elimination (CSE) refers to compiler optimization replaces identical expressions (i.e., they all evaluate to the same value) with a single variable holding the computed value when it is worthwhile to do so Source: Geeksforgeeks
Correct Answer: D

Q18: The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.  (2013)

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation
(a) 3
(b) 4
(c) 5
(d) 6
Ans: (b)
Sol: Here, we are told not to do code motion. So, we start with 3 registers
c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, e in register, d spilled.
So, now we try with 4 registers
c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, d, e in register
x = c * c; //a, x, d, e in register
if (x > a) {
  y = a * a;
}
else {
 d = d * d;
 e = e * e;
}
No spilling. So, 4 is the minimum number of registers needed for avoiding spilling. (If code motion was allowed, we need only 3 registers for avoiding spilling).

Q19: The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.  (2013)

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?
(a) 0
(b) 1
(c) 2
(d) 3
Ans: (b)
Sol:  We can do code motion as follows:So, we need minimum 1 spill in the compiled code.

Q20: Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?  (2011)

(a) 2
(b) 9
(c) 5
(d) 3
Ans: (d)
Sol: Given is Load Store Architecture, that means we can access memory using Load and Store Instructions.
Key Idea:- Pick new register only when it is required.
We want to add c and d, and initially both are in memory, therefore copy these into registers

• load R1,c (R1 ← c)
• load R2,d  (R1 ← d)

(here no compensation can be done, we need two registers)

• add  R1, R2, R3 (R1 ←  R1 + R2 )

(at this point R1 is holding c + d and R2 is holding d , i.e. R1 ← c + d and R2 ← d )
Now, e comes into picture and my question is, Can i make use of R1 or R2 to store e ?
 I can not use R1 to store e as its value will be needed later but I can use R2.

• loadR2,e
  (currentlyR1 ← c + d andR2 ← e)
• SubR1, R2,  R1 (R1 ← R2 - R1)

Doing this all gives, final value of right sub-tree is stored in R1 , and R2 stores e . Now, coming to left subtree, to perform " a − b " we need to copy both variables in registers. We can copy one of the variable in R2 , but we can not obviously copy in R1 as value of R1 will be required later.

•  Load R2,a
• Load R3,b (here comes extra register, and we can not avoid using it.)

Current mapping is R2 ← a , R3 ← b and R1 contains final value of Right subtree.

• SUB R2, R2, R3 (R2← R2 − R3)
• ADD R1, R1, R2

Hence answer is 3 i.e. D

Q21: The program below uses six temporary variables a, b, c, d, e, f.  (2010)
a =1
b= 10
c =20
d= a +b
e= c +d
f =c +e
b= c+ e
e =b +f
d =5 +e
return d +f
Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
(a)2
(b) 3
(c) 4
(d) 6
Ans: (b)
Sol: Here in these types of compiler questions, idea is "map/assign multiple temporaries to one registers."
here a , b , and c all are having 3 different values so i need atleast 3 registers r 1 , r 2 and r 3 . a is mapped to r 1 , b to r 2 and c to r 3 .
d = a + b , after this line if u notice ' a ' is never present on right hand side, so I can map (register of a which is r 1 ) d to r 1 .
e = c + d , after this line ' d ' is never present on rhs, so I can map (register of d which is r 1 ) e to r 1 .
at this time mapping is
r1- - - e
r2- - - b
r3- - - c
(at this moment I have registers for e, b and  c. if I introduce new variable then I may need different register)
now at this point if u see
f = c + e
b = c + e
these two are essentially doing same thing, after these two line 'b' and 'f' are same so I can skip computing 'f'. and whereever  f is present I will replace it with 'b'. (because neither of 'f' and 'b' are changing after these two lines, so value of these will be 'c +e' forever)
(seems like I introduced one more variable f, and register is needed for that, but actually I did not really introduce 'f'. I am skipping computation of 'f')
now at second last line "d = 5 + e"
here I introduced 'd', I can map it to any of the register r1  or r3, because after this line neither of 'e' or 'c' is required. (value of 'b' is required because I need to return 'd + f', and 'f' is essentially equal to 'b')
finally code becomes
r1 = 1
r2 = 10
r3 = 20
r1 = r1 + r2
r1 = r3 + r1
(skipping 'f' computation)
r2 = r3 + r1
r2 = r3 + r1
r1 = r2 + r2
r3 = 5 + r1
return r3 + r2
Therefore minimum 3 registers needed.
Correct Answer: B