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

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