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

Thanks @palashbehra5

---

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

---

CYK is a Bottom-Up, Chart-Based, Dynamic-Programming Parser.

Bottom-up → It builds larger structures from smaller substrings.

Parser for Context-Free Grammars (CFGs).

Requires grammar in CNF (Chomsky Normal Form).

A membership parser → checks if a string belongs to the language.

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

for any cfg there is a parser, isn't this phrase is wrong because there is some ambiguous grammar for which no parsing algorithm exists.

---

@Ankur29  @Arjun   in second statement its saying for any cfg,there is a parser, isnt this phrase wrong bcz we cant have parser for any grammar,coz grammar could be ambiguous.

---

Does CYK algorithm work only for unambiguous grammar?

---

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?

---

Same question

 

---

The LR family of parsing methods only works with unambiguous grammars. Operator precedence is not from LR family.

---

@robinofautumn Checking if a string is generated by a grammar is the same as parsing right?

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