GATE CSE 2012 | Question: 36

Question

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$: \text{Main} \rightarrow \text{A1} \rightarrow \text{A2} \rightarrow \text{A21}\rightarrow \text{A1}$

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

Comments

Self Note : Mandatory Watch -  https://youtu.be/mMK-TlvH5c4?si=wEtzLynmSG3rTt9S&t=520

---

out of syllabus or wot ?

---

It's not that mandatory....you just need to know static scoping

Answer 1

Activation record: 

Access link: to access non-local data

The calling chain$: \text{Main} \rightarrow \text{A1} \rightarrow \text{A2} \rightarrow \text{A21}\rightarrow \text{A1}$

PROCEDURE	non-local data present
A1	outside procedure A1 body i.e. in main procedure               So, A1---> main
A2	outside procedure A2 body i.e. in main procedure               So, A2---> main
A21	outside procedure A21 body i.e. in A2 procedure               So, A21---> A2

 

$$\begin{array}{c|c}\hline \textbf{PROCEDURE} & \textbf{non-local data present} \\\hline \text{A1} & \text{outside procedure A1 body i.e. in main procedure}  \\  & \text{So, A1} \rightarrow \text{main} \\\hline \text{A2} & \text{outside procedure A2 body i.e. in main procedure} \\ & \text{So, A2} \rightarrow \text{main} \\\hline \text{A21} & \text{outside procedure A21 body i.e. in A2 procedure} \\ & \text{So, A21} \rightarrow \text{A2} \\\hline   \end{array}$$

https://www.youtube.com/watch?v=mMK-TlvH5c4&t=1093s @18:00

Comments

Thanks for the link!

Answer 2

From main() there are three function calling sequence

1) A1 -> A2

2) A2 ->  A21  ->  A1

3) A1

These 1,2,3 are access links.

Now match with the given answer calling chains:

A)(FALSE)

It shows a linear chain(only one function call from main()) which isn't correct and doesn't follow above sequence at all.

B)(FALSE)

It is false because main() unable to call A1 directly.

C) (FALSE)

It shows there is only two function call made by main(). That is not true and Frame pointer will also get updated by new A1 address block not will be old one.

D) (TRUE)

main() has three function calling sequence present and Frame Pointer is holding the new A1 block address. That is true.

Comments

Loved reading, sharing another approach

We can make the tree from code given,

 

Main

├── A1

└── A2

        └── A21
 

Means, A1 and A2 should point to main, and A21 should point to A2

And now, check options done.

Answer 3

$Ans:D$

---

RTST$\rightarrow$P$\rightarrow$R$\rightarrow$Q$\rightarrow$R

program RTST;

  procedure P;

     procedure Q;
        begin R; end

     procedure R;

        begin Q; end

  begin R; end

begin P; end

---

$Similary\ we\ can\ approach\ the\ given\ Question !$

Answer 4

Note:-In the given pseudo-code, a procedure is allowed to run only when it is called, Like program main has many procedure declarations inside it but its functionality is to call procedure A1() only {last line}.

Activation records are created at procedure entry time and destroyed at procedure exit time.
First why we need access link(Static-link chain) in activation record? the access link is used to access the non-local data which is used inside of a procedure but defined outside of the procedure. 
Lexical Scoping means a variable defined outside a function can be accessible inside another function. one procedure can access only data from its parents or ancestors(if nested procedure allowed).

In simple words see the function in which function is defined, like A(21) is defined in A(2), for any value lets say "x" will be checked in local function A(21) if it is not present, check in A(2), then at global storage area of program. so A(21) access link to A(2) & A(2) access link to program main. when this code will execute, first program main & its global variables will be pushed into the stack. all the procedure declaration will not run until CALL A1; Now A1() is called so it will be pushed into the stack. now you are in inside A1 when u execute its code then A2 is called so A(2) will be pushed into stack and link will be established between main to A2(the reason is A2() is defined into program main).

Option D is correct.

Reference:- https://youtu.be/mMK-TlvH5c4?t=516

Answer 5

once a function gets called then only it gets activation record in stack and  then only it gets access link and  control link  now say f() got called
its  control link will point to activation record of the caller (simple)
now its  for the access link it checks where it was defined then sees immediate parent only and point to it only
thats why for both activation record of A1 we have same access link