Consider the following grammar \(πΊ\): \(πβπ΄β£π΅ \\ π΄βπβ£π \\ π΅βπβ£π\)β¦
2018
Consider the following grammarΒ \(πΊ\):
\(πβπ΄β£π΅ \\ π΄βπβ£π \\ π΅βπβ£π\)
whereΒ \(\{π,π΄,π΅\}\)Β is the set of non-terminals,Β \(\{π,π,π\}\)Β is the set of terminals.
Which of the following statement(s) is/are correct?
\(π_1\):Β \(πΏπ
(1)\)Β can parse all strings that are generated using grammarΒ \(πΊ\).
\(π_2\):Β \(πΏπΏ(1)\)Β can parse all strings that are generated using grammarΒ \(πΊ\).
Choose the correct answer from the code given below:
- A.
OnlyΒ
\(π_1\) - B.
OnlyΒ
\(π_2\) - C.
BothΒ
\(π_1\)Β andΒ\(π_2\) - D.
NeitherΒ
\(π_1\)Β norΒ\(π_2\)
Attempted by 79 students.
Show answer & explanation
Correct answer: D
Answer: Neither statement is correct.
Grammar: S -> A | B ; A -> a | c ; B -> b | c
Why LL(1) fails: FIRST(A) = {a, c} and FIRST(B) = {b, c}. These sets overlap on c, so when the parser sees lookahead c it cannot decide whether to expand A or B. Therefore the grammar is not LL(1).
Why LR(1) fails: the grammar is ambiguous because the terminal string "c" has two different parse trees (S -> A -> c and S -> B -> c). Ambiguous grammars cannot be parsed deterministically by LR(1); attempting to build an LR(1) parser yields a reduce/reduce conflict for the completed reductions A -> c and B -> c with the same lookahead (end of input).
Conclusion: Neither an LL(1) parser nor an LR(1) parser can parse all strings generated by this grammar. Strings "a" and "b" are unambiguous, but "c" is ambiguous.
A video solution is available for this question β log in and enroll to watch it.