The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.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 (69k points)
edited by | 2.6k views

1 Answer

+25 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 Veteran (19.8k points)
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

link: http://www.cs.sunysb.edu/~cse304/Fall09/Lectures/attributes-handout.pdf
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.
link:https://www.csee.umbc.edu/courses/331/fall11/notes/04/04cparsing.ppt.pdf
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 ?
yes.
L- attributed definition can contain synthesized attribute. So I think it should be D.
@bad_doctor

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

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

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.

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

33,687 questions
40,230 answers
114,268 comments
38,792 users