in Compiler Design
17,844 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

1 vote
1 vote

We read option I - it's false.

So we hv to decide between only A and D and to do that we need to determine whether III is true or false.

III is false so option A is the ans.

1 comment

I approached the same way ... :)
0
0
0 votes
0 votes

Explanation: 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”  [Source:  https://en.wikipedia.org/wiki/Call_stack ]

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.

source:_https://www.geeksforgeeks.org/gate-gate-cs-2008-question-54/

0 votes
0 votes

The answer is II and V only.

I. False. Recursion can be implemented with static storage allocation, but it requires careful management of the stack to ensure that the recursive calls don't overflow the available memory.

II. True. Multi-level access links are used to keep track of the activation records of nested procedures/functions. This allows the compiler to access variables and parameters from different levels of nesting.

III. False. Recursion can be implemented with dynamic storage allocation. In fact, this is the most common approach, as it allows for more flexibility in terms of memory usage.

IV. False. Nesting procedures/functions and recursion can be implemented with a stack-based allocation scheme for activation records. The stack is a LIFO (last-in, first-out) data structure that is well-suited for managing function calls and returns.

V. True. Functions that return functions as their results require a dynamic allocation scheme, as the lifetime of the returned function is not known at compile time. This cannot be implemented with a stack-based allocation scheme, as the stack is only used for storing local variables and function parameters.

Answer:

Related questions