Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
2003
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
- A.
Removing left recursion alone
- B.
Factoring the grammar alone
- C.
Removing left recursion and factoring the grammar
- D.
None of these
Attempted by 196 students.
Show answer & explanation
Correct answer: D
Final answer: None of these
Explanation:
There is no general transformation that converts every context-free grammar into an LL(1) grammar. Some grammars are inherently ambiguous or require changing the language to become LL(1).
Common helpful transformations include removing left recursion and left factoring, and eliminating useless symbols or unreachable productions, but these do not guarantee LL(1).
Formal LL(1) conditions to check after transformations:
For each nonterminal, the FIRST sets of every pair of distinct productions must be disjoint (no FIRST/FIRST conflicts).
If a production can derive ε, then its FIRST set must be disjoint from the FOLLOW set of the nonterminal (no FIRST/FOLLOW conflicts).
If these conditions fail, you either need to further rewrite the grammar (which may change the language) or accept that the grammar is not LL(1).
Therefore, neither removing left recursion alone, factoring alone, nor both together suffices for every CFG; the correct conclusion is that none of those guarantees conversion to LL(1).