The grammar \(S \rightarrow (S) \mid SS \mid \epsilon\) is not suitable for…
2018
The grammar \(S \rightarrow (S) \mid SS \mid \epsilon\) is not suitable for predictive parsing because the grammar is
- A.
Right recursive
- B.
Left recursive
- C.
Ambiguous
- D.
An operator grammar
Attempted by 232 students.
Show answer & explanation
Correct answer: C
Answer: The grammar is ambiguous.
Explanation:
Show ambiguity with a concrete string (for example "()"):
Derivation 1: S ⇒ (S) ⇒ (ε) ⇒ "()"
Derivation 2: S ⇒ SS ⇒ (S)S ⇒ (ε)S ⇒ "()"
These are two distinct leftmost derivations that produce the same terminal string, so the grammar is ambiguous.
Consequence for predictive parsing:
Predictive (LL(1)) parsers require an unambiguous grammar with no left recursion and with disjoint FIRST/FOLLOW predictions. Because this grammar is ambiguous, it cannot be directly parsed by a predictive parser.
Note: the production S → SS also introduces left-recursive structure, which is another reason a naive top-down predictive parser would fail; both ambiguity and left recursion make this grammar unsuitable for predictive parsing without transformation.
A video solution is available for this question — log in and enroll to watch it.