Log In
32 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
in Compiler Design
edited by

For point 2 we can refer to  question  (point 3)

2 Answers

33 votes
Best answer

Answer is B.

  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
can u pls elaborate option C ?
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

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

plz elaborate??
CFG is O(n^3)
LL and LR parsers are linear time parsers.
how can be done code improvement in source code?
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)
In recursion, we know that the recursion stack can grow to any extent. Is that the reason for recursion requiring dynamic memory allocation ?
L- attributed definition can contain synthesized attribute. So I think it should be D.

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


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

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

Predictive Parser runs in linear time.


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

 It needs Stack storage allocation instead of dynamic storage allocation.

recursion requires stack and not heap(used for dynamic memory allocation)
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.
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
Correct! :)

Related questions

25 votes
2 answers
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}$
asked Sep 22, 2014 in Compiler Design Kathleen 2.8k views
29 votes
3 answers
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$
asked Apr 23, 2016 in Operating System jothee 4.2k views
39 votes
3 answers
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$.
asked Apr 23, 2016 in Algorithms jothee 5.3k views
40 votes
6 answers
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$
asked Apr 23, 2016 in Databases jothee 10.3k views