Home › Previous year questions › GATE 2021 CS (CS1) › Question 15GATE 2021 CS (CS1) – 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?
$S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true $S_1$ is true and $S_2$ is true $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.
More Parsing and Syntax Analysis questions GATE 2021 CS (CS1) Q41 – Consider the following context-free grammar where the set of terminals is a, b, c, d, f. S… GATE 2020 CS Q34 – Consider the following grammar. S aSB d B b The number of reduction steps taken by a… GATE 2019 CS Q13 – Which one of the following kinds of derivation is used by LR parsers? GATE 2019 CS Q29 – Consider the grammar given below: S → Aa A → BD B → b ε D → d ε Let a, b, d, and 36 be… GATE 2019 CS Q53 – Consider the augmented grammar given below: S' → S S → ⟨L⟩ id L → L,S S Let I… GATE 2018 CS Q48 – Consider the following parse tree for the expression a\#b36c36d\#e\#f, involving two… All Parsing and Syntax Analysis questions →