GATE CSE 2021 Set 1 | Question: 4

Question

Consider the following statements.

• $S_1:$ The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
• $S_2:$ The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

• A. $S_1$ is true and $S_2$ is false
• B. $S_1$ is false and $S_2$ is true
• C. $S_1$ is true and $S_2$ is true
• D. $S_1$ is false and $S_2$ is false

Comments

Option C, both are true?

---

These statements are directly copied from Aho-ullman book page no 432. see here

---

Compiler Principles Techniques & Tools – by – Aho, Lam. Sethi & Ullman

 

---

https://codingninjas.com/studio/library/activation-tree-in-compiler-design

Answer 1

Correct Answer: C

---

$S_1$: Is true because to perform procedure calls, first parent function will call child functions  and hence it resembles preorder.

$S_2$: Is true because to return parent function ,  we must return child functions first. Hence it resembles post order.

Comments

These statements are directly copied from Aho-ullman book page no 432. see here

---

calling sequence of activation   record is always in preorder traversal while return is always postorder.

Answer 2

Option C :- Both S1 and S2 are true.
Consider the recursion tree :-  
                  fun(A)                           Procedure Calls :- A → B → C → D → E   : Preorder
                //        \\                           Return :-               C → D → B → E → A    :Postorder
            fun(B)    fun(E)
           //     \\
     fun(C)   fun(D)

Answer 3

when we call a procedure, it goes to the stack

and as we know stack uses both pre-order and post-order traversal

Both statements are correct :)