# GATE2012-36

5.2k views

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 \rightarrow A1 \rightarrow A2 \rightarrow A21 \rightarrow A1$

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

edited
0
can any one describe it more ?
0
Need more explanation of this question
9
First why we need access link? acess link is used to access the non local data.why we need non local deta what it has to do with access link ? example :: In dynamic scoping we need to access the non local data this done using access link now come to question .....when this code will executed first main will pushed in stack. all the procedure declaration will not run until CALL A1; It will called so it will pushed into stack.now program will try to find the code of A1 so it will go to main using the access link to main .main will give code to A1.so access link will need here .now you are in inside A1 when u execute its code then A2 will be called .again using access link it will go main to find the code of A2 and then pushed into stack so link will be stablished between main to A2 reason is using main you came to know that A2 exist.this process will continue until whole program get executed. below link will be helpfull page 42

https://www.cse.iitk.ac.in/users/karkare/cs335/lectures/13RuntimeSystems.pdf
0
Thanks @a new one.
0
in simple words see the function in which it is defined like A(1) is defined in the program main so in lexical scoping for any value lets say "x" will be checked in local function A(1), if it is not present, then at the global storage area of the program. so A(1) access link to program main.
0
@a new one

0
0
If the Question is changed to find the control links instead of access links?

Does this below stack with the control links is correct? Am i  putting the frame pointer in right position ?

1
The concept behind these kinds of questions can be found in the dragon book for compilers, chapter 7, under "Access to Non-Local Data on the Stack" - "Manipulating Access Links".
0
Thanks
0
I also have the same doubt . Can you tell now if this is correct for control link ?

@shaktisingh
0
The calling sequence is already given.

Access links tell you where the non-local data might be present; use lexical scoping (static scoping) to trace out the links.

PS: Control links depict the calling sequence (or flow of control) — which is even easier to find out.

From main() there are three function calling sequence

1) A1 -> A2

2) A2 ->  A21  ->  A1

3) A1

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.

Activation record:

access link : to access non local data

Assume C lang.  like pseudo code,

the calling chain: Main→A1→A2→A21→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

1 vote

$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 !$

1 vote

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

## Related questions

1
4.3k views
For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\varepsilon$ is the empty string, \$indicates end of input, and,$ ... $E2 : B \rightarrow S, S \rightarrow \varepsilon$ $E3 : B \rightarrow S$
2
2.1k views
For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\varepsilon$ is the empty string, \$indicates end of input, and,$\mid$separates alternate right hand sides of productions.$ S\rightarrow a ... $\text{FOLLOW}(A) = \{a, b\}$ $\text{FOLLOW}(B) =\{a, b\}$
3
1.8k views
Consider the following program skeleton and below figure which shows activation records of procedures involved in the calling sequence. $p \rightarrow s \rightarrow q \rightarrow r \rightarrow q.$Write the access links of the activation records to enable correct access and variables in the procedures from ... q; procedure r; begin q end r; begin r end q; procedure s; begin q end s; begin s end p;