Question

Consider the following statements.
\[ S_1:\ \text{Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).} \] \[ S_2:\ \text{For any context-free grammar, there is a parser that takes at most } O(n^3) \text{ 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

Hint:

All LR grammars are unambiguous, but the converse is not true. General CFG parsing can always be done in polynomial time.

Answer 1

The Correct Option is C

Step 1: Analyze Statement S₁.
SLR(1) grammars form a proper subclass of LR grammars. Since LR parsers generate a unique rightmost derivation in reverse, all LR (and hence SLR(1)) grammars are unambiguous.

However, the converse is not true. There exist grammars that are unambiguous but do not satisfy the stricter FOLLOW-set conditions required for SLR(1) parsing.

Therefore, there exist unambiguous grammars that are not SLR(1), making statement S₁ true.

---

Step 2: Analyze Statement S₂.
For arbitrary context-free grammars, general parsing algorithms are available.

Algorithms such as the CYK (Cocke–Younger–Kasami) algorithm and Earley’s parser can parse any context-free grammar in O(n³) time in the worst case, where n is the length of the input string.

Hence, S₂ is also true.

---

Final Conclusion:
Since both statements S₁ and S₂ are true, the correct option is:

Final Answer: (C)