GATE2009-42

7k 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
1

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

1. Yes there does exist parsing algorithms 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
0
can u pls elaborate option C ?
21
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??
32
CFG is O(n^3)
LL and LR parsers are linear time parsers.
0
how can be done code improvement in source code?
18
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.
5

@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.
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! :)

Related questions

1
2.8k views
Match all items in Group 1 with the correct options from those given in Group 2.Syntax analysis ... $\text{P-3, Q-4, R-1, S-2}$ $\text{P-2, Q-1, R-4, S-3}$
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common ... major order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ ... is in $3NF$ but not in $\text{BCNF}$ The schema is in $2NF$ but not in $3NF$ The schema is not in $2NF$