The GATE Grind

GATE 2021 CS – Question 15

Compiler Design · Parsing and Syntax Analysis · 1 mark · Multiple choice

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(n^3)$ time to parse a string of length $n$.
Which one of the following options is correct?

  1. $S_1$ is true and $S_2$ is false
  2. $S_1$ is false and $S_2$ is true
  3. $S_1$ is true and $S_2$ is true
  4. $S_1$ is false and $S_2$ is false

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $S_1$ is true and $S_2$ is true

Explanation

SLR(1) grammars are unambiguous, but not every unambiguous grammar is SLR(1). CYK/Earley parse any CFG in $O(n^3)$. Both are true.