GATE CS 2021 Set 1 Q5 — Parsing (LL, LR)

Let us analyze the two statements individually:

Statement $S_1$: Every $\text{SLR(1)}$ grammar is unambiguous but there are certain unambiguous grammars that are not $\text{SLR(1)}$.

• Part 1: Any grammar that is parsable by a deterministic parser (like $\text{LR(0)}$, $\text{SLR(1)}$, $\text{LALR(1)}$, or $\text{LR(1)}$) is guaranteed to be unambiguous because the parser can uniquely determine the derivation (and thus the parse tree) for any valid string.
• Part 2: The class of $\text{SLR(1)}$ grammars is a strict subset of unambiguous grammars. For example, the classic grammar: $$\begin{aligned} S &\to L = R \mid R \\ L &\to *R \mid \text{id} \\ R &\to L \end{aligned}$$ is unambiguous, but it is not $\text{SLR(1)}$ because it contains a shift-reduce conflict in its $\text{SLR(1)}$ parsing table.

Thus, $S_1$ is true.

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

• General context-free grammar parsing algorithms, such as the CYK (Cocke-Younger-Kasami) algorithm and Earley's algorithm, can parse any arbitrary context-free grammar in at most $O(n^3)$ time, where $n$ is the length of the input string.

Thus, $S_2$ is true.

Since both statements $S_1$ and $S_2$ are true, the correct option is C.