4.2k views

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 | 4.2k views
0

For point 2 we can refer to  question https://gateoverflow.in/477/gate2008-54  (point 3)

1. Yes there does exist parsing algos less than $\Theta(n^3)$.
2. It cannot be implemented with static storage allocation. It needs dynamic memory allocation.
3. If the L-attributed definitions contain synthesized attributes then it can be evaluated.
4. True.
edited by
0
can u pls elaborate option C ?
+9
every s-attributed SDT is L-attributed SDT (vice-versa need not be true)

S-attributed SDT follows bottom up approach. Hence L-attributed SDT which are also S-attributed can be solved by bottom up parsing

0
which parsing algorithm takes less than O(n^3) plz explain .........i know CNF but in take O(n^3)

plz elaborate??
+19
CFG is O(n^3)
LL and LR parsers are linear time parsers.
0
how can be done code improvement in source code?
+9
As a programmer, you can always try to improve time complexity
You can even use code optimization techniques that happen in intermediate code level in your program
(like loop unrolling etc)
0
In recursion, we know that the recursion stack can grow to any extent. Is that the reason for recursion requiring dynamic memory allocation ?
0
yes.
0
L- attributed definition can contain synthesized attribute. So I think it should be D.
0

If L-attrib definition contains only synthesized attributes then it can be evaluated using bottom-up parser.
+3

@vishalshrm539

https://gateoverflow.in/908/gate2003-18

Some L-attributed grammars (including those with non-synthesized attributes)  can be evaluated by a bottom-up parser.

0
yeah, i just missed that, anyway option C is false.
+1

Predictive Parser runs in linear time.

+2

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

It needs Stack storage allocation instead of dynamic storage allocation.

0
recursion requires stack and not heap(used for dynamic memory allocation)

1
2