Question

Consider the following statements:
$S_1:$ Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
$S_2:$ For any context-free grammar, there is a parser that takes at most $O\left(n^3\right)$ time to parse a string of length n.

Which one of the following options is correct?

• A. $S_1\text{is false and}{S}_2\text{is false}$
• B. $S_1\text{is true and}{S}_2\text{is true}$
• C. $S_1\text{is true and}{S}_2\text{is false}$
• D. $S_1\text{is false and}{S}_2\text{is true}$

Answer 1

The correct option is B $S_1\text{is true and}{S}_2\text{is true}$

$S_1:$ Every SLR(1) is unambiguous but every unambiguous in not SLR(1). So $S_1$ is true.
$S_2:$ Using CYK algorithm which takes at most $O\left(n^3\right)$ time to parse a string, where n is the length of the string. So $S_2$ is true.

Both $S_1$ is true and $S_2$ is true.