in Compiler Design retagged by
7,696 views
10 votes
10 votes

Consider the following statements.

  • $S_1:$ Every $\text{SLR(1)}$ grammar is unambiguous but there are certain unambiguous grammars that are not $\text{SLR(1)}$.
  • $S_2:$ For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length $n$.

Which one of the following options is correct?

  1. $S_1$ is true and $S_2$ is false
  2. $S_1$ is false and $S_2$ is true
  3. $S_1$ is true and $S_2$ is true
  4. $S_1$ is false and $S_2$ is false
in Compiler Design retagged by
by
7.7k views

4 Comments

DCFGs are of great practical interest, as they can be parsed in linear time.

https://en.wikipedia.org/wiki/Deterministic_context-free_grammar
 

In computer science, LR parsers are a type of bottom-up parser that analyses deterministic context-free languages in linear time.

https://en.wikipedia.org/wiki/LR_parser
 

https://gateoverflow.in/84654/Complexityofparser

3
3
0
0
For S2 is there no need to specify that the CFG is not ambiguous?
0
0

2 Answers

19 votes
19 votes
Best answer

Correct option is C.  Both statements are correct.

An unambiguous grammar is not necessarily $\text{SLR}(1).$ But every $\text{SLR}(1)$ grammar is unambiguous.

We do have $\text{CYK}$ algorithm which takes $O(n^3)$ time (assuming size of the context-free grammar $|G|$ to be a constant) to parse any string of length $n$ using a context-free grammar $G.$

edited by

4 Comments

That too when the grammar is in the form of CNF.
0
0

Operator precedence (bottom up parser) can be applied on both ambiguous and unambiguous grammars.

1
1
edited by

@Arjun @GO Classes

i have a doubt in:

 For any context-free grammar, there is a parser that takes at most O(n^3) time to parse a string of length n.

CYK algo is a membership algo→ it only checks if a string can be generated from a given grammar, but it has asked for parsing, we have to generate a string.

so, can we use the term parsing and membership interchangeably?

0
0
1 vote
1 vote

ANS IS C, BOTH ARE TRUE

STMT 1:- NO AMBIGUOUS GRAMMAR IS LR(k) 

STMT 2:- READ ABOUT CYK ALGORITHM https://en.wikipedia.org/wiki/CYK_algorithm

Answer:

Related questions