GATE CSE 2021 Set 1 Q15: SLR(1) grammars, ambiguity and cubic-time CFG parsing

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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: Deterministic parsers never accept ambiguous grammars; general CFG parsing (CYK, Earley) runs in cubic time.

First step: Recall that some unambiguous grammars are LALR(1) or LR(1) but not SLR(1), and CYK parses any CFG in $O(n^3)$ .

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key