edited by
18,229 views
50 votes
50 votes

Which of the following statements are TRUE?

  1. There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$

  2. A programming language which allows recursion can be implemented with static storage allocation.

  3. No L-attributed definition can be evaluated in the framework of bottom-up parsing.

  4. Code improving transformations can be performed at both source language and intermediate code level.

  1. I and II
  2. I and IV
  3. III and IV
  4. I, III and IV
edited by

3 Answers

Best answer
46 votes
46 votes

Answer is B.

  1. Yes there does exist parsing algorithms (e.g. CYK algorithm) which run in $\Theta(n^3)$.
  2. It cannot be implemented with static storage allocation. It needs dynamic memory allocation.
  3. Every S-attributed definition is also an L-attributed definition and can be evaluated in the framework of bottom up parsing.
  4. True.
edited by
19 votes
19 votes

LL(1) and LR parsers are linear time parsers. ie, $O(n)$

I is True.

PS: Recursive descent parser runs in $O(2^n)$ time.


Recursion needs stack

II is False

L-attributed definitions have both inherited and synthesized attributes. Can be evaluated with top-down-left-to-right style.

S-attributed definitions have only synthesized attributes. Can be evaluated with bottom-up style.

 

So, in case a definition only has synthesized attributes, we can call it both L and S attributed. Such an L-attributed definition can be evaluated with bottom-up style.

So, III is False.

Code improvement can obviously be done at the user-level by not writing stupid code. And compiler also improves (optimises) the code. Hence,

IV is True.
0 votes
0 votes
  1. There exist parsing algorithms for some programming languages whose complexities are less than (O(n3):

    • True. There are parsing algorithms, such as LL(k) and LR(k), whose complexities are less than O(n3).
  2. A programming language which allows recursion can be implemented with static storage allocation:

    • False. Recursion generally requires dynamic storage allocation, as static allocation may not handle arbitrary levels of recursion.
  3. No L-attributed definition can be evaluated in the framework of bottom-up parsing:

    • True. L-attributed definitions require a top-down parsing approach, as they involve attributes associated with the leftmost derivations.
  4. Code improving transformations can be performed at both source language and intermediate code level:

    • True. Code optimizations can be applied at both the source language level (before compilation) and the intermediate code level (during compilation).

Therefore, the correct answer is:

I and IV

Answer:

Related questions

32 votes
32 votes
1 answer
1
Kathleen asked Sep 22, 2014
7,839 views
Match all items in Group 1 with the correct options from those given in Group 2.Syntax analysis$$\begin{array}{|ll|ll|}\hline \rlap{\textbf{Group 1}} & & \rlap{\textbf{Gr...
61 votes
61 votes
6 answers
4