Consider the following statements. S1: Every SLR(1) grammar is unambiguous but…
2021
Consider the following statements.
S1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S2: 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?
- A.
S1 is true and S2 is false
- B.
S1 is false and S2 is true
- C.
S1 is true and S2 is true
- D.
S1 is false and S2 is false
Attempted by 191 students.
Show answer & explanation
Correct answer: C
Answer: S1 is true and S2 is true.
Why S1 is true:
SLR(1) grammars are parsed by a deterministic table-driven method that does not allow shift/reduce or reduce/reduce conflicts, so an SLR(1) grammar is unambiguous.
However, some unambiguous grammars are not SLR(1) because SLR(1) uses FOLLOW sets (a coarser context) to decide reductions and can create conflicts that stronger methods like LR(1) avoid.
Why S2 is true:
There are general parsing algorithms for arbitrary context-free grammars that run in O(n^3) worst-case time. Examples:
CYK algorithm: requires grammar in Chomsky Normal Form and runs in O(n^3).
Earley parser: worst-case O(n^3) but can be faster on many grammars.
Hence both statements are true.
A video solution is available for this question — log in and enroll to watch it.