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: Analysis of Statement $S_1$.
SLR(1) grammars are a subclass of LR grammars and are always unambiguous because LR parsing constructs a unique rightmost derivation in reverse. However, not all unambiguous grammars satisfy the strict conditions required to be SLR(1). Hence, there exist unambiguous grammars that are not SLR(1).

Step 2: Conclusion for $S_1$.
Therefore, statement $S_1$ is true.

Step 3: Analysis of Statement $S_2$.
For any context-free grammar, general parsing algorithms such as the CYK (Cocke–Younger–Kasami) algorithm and Earley's parser can parse strings in at most $O(n^3)$ time, where $n$ is the length of the input string.

Step 4: Conclusion for $S_2$.
Thus, statement $S_2$ is also true.

Step 5: Final conclusion.
Since both $S_1$ and $S_2$ are true, the correct option is (C).