The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
3.6k 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
asked in Compiler Design by Veteran (59.7k points)
edited by | 3.6k views
0

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

1 Answer

+28 votes
Best answer

Answer is B.

  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.
answered by Boss (19.9k points)
edited by
0
can u pls elaborate option C ?
+7
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

link: http://www.cs.sunysb.edu/~cse304/Fall09/Lectures/attributes-handout.pdf
0
which parsing algorithm takes less than O(n^3) plz explain .........i know CNF but in take O(n^3)

plz elaborate??
+17
CFG is O(n^3)
LL and LR parsers are linear time parsers.
link:https://www.csee.umbc.edu/courses/331/fall11/notes/04/04cparsing.ppt.pdf
0
how can be done code improvement in source code?
+8
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
@bad_doctor

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

@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)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,150 questions
49,639 answers
163,322 comments
65,808 users