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 ?

  1. A.

    Removing left recursion alone

  2. B.

    Removing the grammar alone

  3. C.

    Removing left recursion and factoring the grammar

  4. 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:

  1. Remove left recursion where possible.

  2. Left-factor productions to remove common prefixes.

  3. 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.

Explore the full course: Mppsc Assistant Professor