GATE CSE 2021 Set 1 | Question: 5

Question

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?

• A. $S_1$ is true and $S_2$ is false
• B. $S_1$ is false and $S_2$ is true
• C. $S_1$ is true and $S_2$ is true
• D. $S_1$ is false and $S_2$ is false

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

---

Thanks @palashbehra5

---

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

Answer 1

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

Comments

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

---

@amitkumar.chottu58

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

---

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

Answer 2

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