GATE CS 2003 Q16 — Parsing (LL, LR)

The correct option is D.

To understand why, we must consider the limitations of LL(1) grammars and the nature of arbitrary Context-Free Grammars (CFGs):

1. Inherent Ambiguity: Some Context-Free Languages (CFLs) are inherently ambiguous (e.g., $L = \{a^i b^j c^k \mid i=j \text{ or } j=k\}$). Since any LL(1) grammar must be unambiguous, it is impossible to convert a CFG representing an inherently ambiguous language into an LL(1) grammar by any means.
2. Language Class Limitations: The class of LL(1) languages is a strict subset of deterministic Context-Free Languages (DCFLs), which in turn is a strict subset of all Context-Free Languages (CFLs). Therefore, an arbitrary CFG may generate a language that is simply not LL(1)-parsable.
3. Heuristic Nature of Transformations: Eliminating left-recursion and performing left-factoring are useful heuristic techniques to resolve specific conflicts in a grammar, but they do not guarantee that the resulting grammar will satisfy the LL(1) conditions (i.e., having disjoint $\text{FIRST}$ and $\text{FOLLOW}$ sets for alternative productions).

Thus, no combination of these local transformations suffices to convert an arbitrary CFG into an LL(1) grammar.