5k 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 | 5k views
+1

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.
by Boss (19.9k points)
edited by
0
can u pls elaborate option C ?
+17
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??
+28
CFG is O(n^3)
LL and LR parsers are linear time parsers.
0
how can be done code improvement in source code?
+17
As a programmer, you can always try to improve time complexity
Also a programmer can use addition instead of multiplication
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.
+4

@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.

+3
recursion requires stack and not heap(used for dynamic memory allocation)
0
Can you please, state an example.
+1 vote

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.
by Loyal (6.4k points)
0
Every S attributed grammer is L attributed too and S-attributed SDTs are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes. This means some L attributd SDT are also solved in bottom up fashion , which prooves 3rd statement is FALSE
0
Correct! :)