Previous Year Questions: Runtime Environment | Compiler Design - Computer Science Engineering (CSE) PDF Download

Q1: Consider the control flow graph shown.  (2023) 

Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?
(a) B1: {}, B2: {a}, B3: {a}, B4: {a}
(b) B1: {i, j}, B2: {a}, B3: {a}, B4: {i}
(c) B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}
(d) B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}
Ans: (d)
Sol: We can say that a variable ‘v’ is live(at a statement ‘n’) if there exists a path in CFG from this statement to another statement ‘m’ such that ‘v’ is used in ‘m’ and for each n <= k < m and v is not defined in any statement k. simply, a variable is live(at a statement/point) if there exists a path in CFG where it is used before its modifying.
This question can be solved by definition and by using the algorithm.
Here, they’ve asked live variables at exit point of each basic block.
For B1 : there are 2 paths at exit of B1;
1. B2, B3, B4 : In this path ‘i’, ‘j’ are live as they both are used before modifying. ‘a’ is not live as it is            modified(defined) in B3 before being used in B4.
2. B2, B4 : In this path ‘i’, ‘j’ & ‘a’ all three are live as all these are used before being modified (defined).
Thus, set of live variables at exit of B1 is {a, i, j}.
For B2 : again there are 2 paths at exit of B2;
1. B3, B4 : In this path, only ‘j’ is live because ‘a’ & ‘i’ both are dead as they have been defined before  usage in B3 & B4 respectively and ‘j’ is being used before modifying in B2 (we can reach B2 from B4 as there is loop).
2. B4 : after B2,  there’s a direct path to B4. Here, ‘a’ & ‘j’ are live because they are being used before definition in B4 & B2 respectively and ‘i’ is dead because it is being defined before use in B4.
Thus, set of live variables at exit of B2 is { a, j}.
For B3 : In path B4 B2 B4 or B4 B2 B3, ‘a’ & ‘j’ are live and ‘i’ is dead because ‘i’ is defined before use in B4.
Thus, set of live variables at exit of B3 is { a, j}
For B4 : liveness analysis is same as for B1 because paths at exit of B4 (B2 B3 B4 & B2 B4) are same for B1
except for EXIT (which doesn’t change the ans).
Thus, set of live variables at exit of B4 is {a, i, j}.

Q2: For a statement S in a program, in the context of liveness analysis, the following sets are defined:  (2021 SET  2)
USE(S) : the set of variables used in S
IN(S) : the set of variables that are live at the entry of S
OUT(S) : the set of variables that are live at the exit of S
Consider a basic block that consists of two statements, S1 followed by S2. Which one of the following statements is correct?
(a) OUT(S1) = IN (S2)
(b) OUT (S1) = IN (S1) ∪ USE (S1)
(c) OUT (S1) =IN (S2) ∪ OUT (S2)
(d) OUT (S1) = USE (S1)∪ IN (S2)
Ans: (a)
Sol: When a basic block S₂ immediately follows another basic block S₁, all variables that are live at exit of S₁ must be live at entry of  S₂ (no intermediate place where they can get killed) and no other variable can be live at entry of  S₂ as a basic block is always single entry and single exit.
So, OUT ( S₁₎ = IN (S₂)
Correct option: A

Q3: Consider the following statements.  (2021 SET 1)
S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2: The sequence of procedure returns corresponds to a post order traversal of the activation tree.
Which one of the following options is correct?
(a) S1 is true and S2 is false
(b) S1 is false and S2 is true
(c) S1 is true and S2 is true
(d) S1 is false and S2 is false
Ans: (c)
Sol: 
S₁: Is true because to perform procedure calls, first parent function will call child functions  and hence it resembles preorder.
S₂: Is true because to return parent function ,  we must return child functions first. Hence it resembles post order.
Correct Answer: C

Q4: Match the following:  (2016 SET 2)
(P) Lexical analysis  (i) Leftmost derivation
(Q) Top down parsing  (ii) Type checking
(R) Semantic analysis  (iii) Regular expressions
(S) Runtime environments  (iv) Activation records
(a) P ↔ i, Q ↔  ii, R ↔  iv,S ↔  iii
(b) P ↔ iii, Q ↔ i, R ↔  ii, S ↔  iv
(c)  P ↔  ii, Q ↔  iii, R ↔  i, S ↔ iv
(d) P ↔  iv,Q ↔  i, R ↔  ii, S ↔  iii
Ans: (b)
Sol: 

• Lexical Analysis phase uses regular expressions.
• LMD is involved in top down parsing.
• Type checking is done in semantic analysis phase.
• Activation records are related to Run Time Environments.

 Correct Option: B

Q5: Which of the following statements are CORRECT?  (2014 SET 3)
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
(a) 1 and 2 only
(b) 2 and 3 only
(c) 3 and 4 only
(d) 1 and 3 only
Ans: (d)
Sol: It will be D.
option 2 is wrong because it is not necessary to have automatic garbage collection to implement recursion.
option 4  is wrong because it says that both are required to implement recursion, which is wrong. Either of them will suffice.

Q6: Which one of the following is NOT performed during compilation?  (2014 SET 2)
(a) Dynamic memory allocation
(b) Type checking
(c) Symbol table management
(d) Inline expansion
Ans: (a)
Sol: Dynamic means- at runtime. Dynamic memory allocation happens during the execution time and hence (A) is the answer

Q7: Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted.  (2012) 

Consider the calling chain: Main → A1 → A2 →  A21 →  A1
The correct set of activation records along with their access links is given by

(a) A
(b) B
(c) C
(d) D 
Ans: (d)
Sol: Activation record: 

Access link: to access non-local data
The calling chain: Main → A1 → A2 → A21 → A1

Q8: Which languages necessarily need heap allocation in the runtime environment?  (2010)
(a) Those that support recursion
(b) Those that use dynamic scoping
(c) Those that allow dynamic data structures
(d) Those that use global variables
Ans: (c)
Sol: Those that allow dynamic data structure.
malloc etc uses memory from heap area. Those that allow dynamic data structure.