GATE CS 2021 Set 1 Q4 — Runtime Environments

To understand the relationship between procedure execution and the activation tree, let us analyze how activations begin and end:

• Activation Tree: A tree representation where each node corresponds to an activation of a procedure, and an edge from node $A$ to node $B$ exists if procedure $A$ calls procedure $B$.

Statement $S_1$: Sequence of procedure calls

• A procedure activation begins when it is called.
• In any execution, a caller procedure must start its activation before it can call any callee procedures (its children in the activation tree).
• Since a parent node is visited before its children, and children are called in left-to-right order, the sequence of procedure calls corresponds exactly to a preorder traversal of the activation tree. Thus, $S_1$ is true.

Statement $S_2$: Sequence of procedure returns

• A procedure activation ends (returns) only after all the nested procedures it called (its children in the activation tree) have completed and returned.
• Since a parent node is exited only after all its children have been fully processed and exited, the sequence of procedure returns corresponds exactly to a postorder traversal of the activation tree. Thus, $S_2$ is true.

Since both statements $S_1$ and $S_2$ are true, the correct option is C.