GATE CS 2012 Q.36 (CS Q.36): Runtime Environments and Parameter Passing

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

Program main;
   Var ...
       
   Procedure A1;
      Var ...
      Call A2;
   End A1
 
   Procedure A2;
      Var ...
              
      Procedure A21;
         Var ...
         Call A1;
      End A21
 
      Call A21;
   End A2
 
   Call A1;
End main.

Consider the calling chain: Main -> A1 -> A2 -> A21 -> A1

The correct set of activation records along with their access links is given by

Four candidate stacks of activation records with access links. (A) Main, A1, A2, A21, A1 with the frame pointer at the bottom A1; each record's access link points to the record directly above it. (B) Main, A1, A2, A21, A1 with the frame pointer at the bottom A1; access links: A2 to Main, A21 to A2, bottom A1 to A21; the upper A1 has no access link. (C) Main, A1, A2, A21 with the frame pointer at A1; access links: A1 to Main, A2 to Main, A21 to A2. (D) Main, A1, A2, A21, A1 with the frame pointer at the bottom A1; access links: upper A1 to Main, A2 to Main, A21 to A2, bottom A1 to Main. — Activation records with access links

(A)

(B)

(C)

(D)

Official answer and solution

Official answer: D
From: Official GATE 2012 answer key

Solution

Trace activation records and static access links under lexical scoping for nested procedures.

In block-structured languages with lexical scoping, an access link (static link) always points to the activation record of the procedure in which the called procedure is lexically declared.
Lexical nesting hierarchy:

main is the global root.
A1 is declared inside main. Its static enclosing scope is main. Every activation record for A1 must have its access link pointing to main.
A2 is declared inside main. Its access link must point to main.
A21 is declared inside A2. Its access link must point to A2.

Tracing call chain Main -> A1 -> A2 -> A21 -> A1:

Bottom of stack: Main.
Next: A1 (access link $\to$ Main).
Next: A2 (access link $\to$ Main).
Next: A21 (access link $\to$ A2).
Top of stack: second activation of A1. Because A1 is lexically enclosed by main, its access link points directly to Main (NOT to A21 or A2).

The frame pointer points to the most recent activation record (top A1).
Diagram (D) correctly depicts this exact set of 5 activation records and their access links.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 36 of 65, printed as CS Q.36
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source