GATE CS 2026 Set 1 Q18 — Parsing (LL, LR)

To determine the correct statement, let us analyze each option:

• Option A: $\text{LL(1)}$ parser uses backtracking
  Incorrect. $\text{LL(1)}$ is a predictive, non-backtracking top-down parser. It uses a parsing table and a single lookahead token to make deterministic parsing decisions without backtracking.
• Option B: For a grammar to be $\text{LL(1)}$, it must be left-recursive
  Incorrect. If a grammar is left-recursive (e.g., $A \to A\alpha \mid \beta$), the parser will enter an infinite loop. Thus, an $\text{LL(1)}$ grammar must never be left-recursive.
• Option C: For a grammar to be $\text{LL(1)}$, it must be left-factored
  Correct. Left-factoring is the process of removing common prefixes from the right-hand sides of productions for the same non-terminal (e.g., $A \to \alpha\beta \mid \alpha\gamma$). If a grammar is not left-factored, the parser cannot decide which production to choose with a single lookahead token. Hence, a grammar must be left-factored to be $\text{LL(1)}$.
• Option D: The $\text{LL(1)}$ parsers are more powerful than the SLR parsers
  Incorrect. $\text{SLR(1)}$ (and more generally, bottom-up shift-reduce parsers) are strictly more powerful than $\text{LL(1)}$ parsers. Every $\text{LL(1)}$ grammar is also an $\text{LR(1)}$ grammar, and the class of $\text{LL(1)}$ languages is a proper subset of $\text{SLR(1)}$ languages.

Therefore, only statement C is true.