Which of the following suffices to convert an arbitrary CFG to an LL(1)…
2014
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar ?
- A.
Removing left recursion alone
- B.
Removing the grammar alone
- C.
Removing left recursion and factoring the grammar
- D.
None of the above
Attempted by 155 students.
Show answer & explanation
Correct answer: D
Answer: None of the above.
Why: LL(1) has specific conditions that must hold for every nonterminal.
For any nonterminal, the FIRST sets of its different productions must be pairwise disjoint (no FIRST/FIRST conflicts).
If a production can derive ε, then its FIRST set must be disjoint from the FOLLOW set of that nonterminal (no FIRST/FOLLOW conflicts).
Why the listed transformations are insufficient:
Removing left recursion helps for top-down parsing but does not resolve FIRST/FIRST or FIRST/FOLLOW conflicts that prevent LL(1).
Left-factoring (factoring) can eliminate common prefixes and reduce conflicts but may still leave FIRST/FOLLOW overlaps or be impossible without changing the language.
Some grammars are inherently ambiguous or require more than one token of lookahead; such grammars cannot be converted to LL(1) by standard local transformations.
Practical approach to attempt LL(1) conversion:
Remove left recursion where possible.
Left-factor productions to remove common prefixes.
Compute FIRST and FOLLOW sets and check for conflicts. If conflicts remain, consider grammar redesign or using a more powerful parser.
Conclusion: No single one of the transformations listed guarantees conversion of an arbitrary CFG to LL(1); therefore the correct choice is that none of the listed options alone suffices.
A video solution is available for this question — log in and enroll to watch it.