in Compiler Design
17,820 views
41 votes
41 votes

Which of the following are true?

  1. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

  2. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

  3. Recursion in programming languages cannot be implemented with dynamic storage allocation

  4. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

  5. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

  1. II and V only
  2. I, III and IV only
  3. I, II and V only
  4. II, III and V only
in Compiler Design
17.8k views

2 Comments

please someone explain point 5
1
1
@gatecse @arjun sir

for which programming language/implementation  we can get option number 5?
0
0

7 Answers

36 votes
36 votes
Best answer
  1. False. Recursion cannot be implemented using static allocation.
  2. True. Yes, we do need multi level access link in case of nested functions. Each level to traverse ARB of same level of nesting.
  3. False. Recursion can only be implemented using dynamic memory allocation.
  4. False. Recursion is done using memory in stack (ARBs in stack), not in heap.
  5. True. Yes, they cannot, once a function returns its activation record is no longer valid, so we cannot return a function as a result.


So, option (A) is correct.

edited by

4 Comments

edited by
Can functions be returned as a result of a function call in any programming language?

In c we return pointer to function but not  function itself.So , cant we use pointers to get this done?

Also,if value,string etc. can be returned then why cannot a function be returned?
0
0

What is the difference between first option in this question and first option in this https://gateoverflow.in/2052/gate2014-3-18

0
0
About 4th point

Nesting of procedure / function and recursion require a dynamic heap allocation is TRUE

BUT THE POINT SAYS FUNCTION / PROCEDURE CANNOT BE IMPLEMENTED WITH A STACK BASED ALLOCATION WHICH IS FALSE

RECURSION IS SUPPORTED IN BOTH HEAP / STACK ALLOCATION
1
1
42 votes
42 votes

Answer is A.


1. is False, Recursion can not be implemented using static storage allocation.

Explanation:
in static storage allocation, a single value is reserved at compile time for each parameter and local variable of a function.
No place is provided to store any intermediate values calculated by repeated nested calls to the same function. Therefore, systems with only static storage allocation can not support recursion.

factorial (static int n)
{
if (n<=1)
return 1;

else
return (n*fact(n-1))
}

If you run this program for any value of n, say n=4. fact(4) will give output as 1.

2. is True.
Explanation: See my comment here.

3. False
We use run time stack that is one of the portion of Dynamic storage (Other portion is Heap, Both grows in opposite direction)

4. False (explanation same as above)

5. True
Explanation:  See this Code (Java script), Here function a() returns a function itself that is b().

function a() {

    alert('A!');

    function b(){
        alert('B!');
    }

    return b();
}

var s = a();

This wont be possible using stack, once activation record of a() pops out (remeber a() returns b()), now we need b(), bcoz a() just returned b(), And b() was defined in a() which no longer exists.

4 Comments

@Sachin Mittal 1

Sir, for point 5 can this be the reason,

That , whenever we call some function then it must return some value not any function as returning a function is not possible because nested functions (activation records) are the first to be evicted and that too after returning some values and not function.

Please check this Sir.

0
0

now we need b(), bcoz a() just returned b(), And b() was defined in a() which no longer exists.

Why do we even need b()? b() is a function while only b is a reference to a function. The function a() has already returned b(). So there should be no error. 

So, why can’t we use stack allocation scheme? 

0
0

@Deepak Poonia @Sachin Mittal 1 @GO Classes

Hi sir, can you please check the doubt of @MiNiPanda? Is it right? I am unable to understand the 5th point.

0
0
14 votes
14 votes
Answer is A.

I. Recursion can never be implemented with Static Storage Allocation.

II, Is TRUE.  

III. Recursion can be implemented with Dynamic Storage Allocation but not with Static Storage Allocation.

IV. Can be done with Stack based allocation scheme.

V. Is TRUE as with a stack based allocation once a function returns its activation record is no longer valid- so we cannot return a function as a result.

4 Comments

@ Saurabh, thanx a lot :)
0
0

sushmita @ saurabh rai 

Can you Pease help in understanding how 5th is true? Returning a function is something different than returning a value?We can return the address of the function as a return value?

1
1
If A calls B,the does A's register for return value hold the value return by B?
0
0
1 vote
1 vote

option- a

I.  Recursion cannot be implemented with Static Storage Allocation.   Static allocation means, compiler has to decide size for function calls.  In case of recursion, it is not possible for compiler to decide as depth of recursion depends on recursion parameter which may be an input from user also.

II. Is CORRECT.  Programming languages that support nested subroutines also have a field in the call frame that points to the stack frame of the latest activation of the procedure that most closely encapsulates the callee, i.e. the immediate scope of the callee. This is called an access link or static link (as it keeps track of static nesting during dynamic and recursive calls) and provides the routine (as well as any other routines it may invoke) access to the local data of its encapsulating routines at every nesting level. Some architectures, compilers, or optimization cases store one link for each enclosing level (not just the immediately enclosing), so that deeply nested routines that access shallow data do not have to traverse several links; this strategy is often called a “display”

III. Recursion CAN be implemented with any kind of  Dynamic Storage Allocation scheme.

IV. Nesting features are always implemented in a language using STACK and NOT Heap. (See above point II for details)

V. Is CORRECT.  In stack based allocation scheme, once a function has returned, it is removed from function call stack.  Therefore returning a function from a function doesn’t look possible.

Answer:

Related questions