Question

Which of the following statements is/are true?

• A. LL(1) parser uses backtracking
• B. For a grammar to be LL(1), it must be left-recursive
• C. For a grammar to be LL(1), it must be left-factored
• D. The LL(1) parsers are more powerful than the SLR parsers

Hint:

LL(1) parsing never backtracks and cannot handle left recursion, but it does require left factoring to resolve common prefixes; LL(1) is a subset of SLR(1), not more powerful.

Answer 1

The Correct Option is C

Step 1: Evaluate the claim that LL(1) parsers use backtracking. LL(1) parsers are predictive, top-down parsers that decide which production to apply using only 1 lookahead symbol, with no backtracking at all. So this claim is false.

Step 2: Evaluate the claim that a grammar must be left-recursive to be LL(1). This is the opposite of the truth: a left-recursive grammar can never be LL(1), because the predictive parser would loop forever trying to expand the left-recursive non-terminal without consuming input. Left recursion must be removed before a grammar can be LL(1). So this claim is false.

Step 3: Evaluate the claim that a grammar must be left-factored to be LL(1). When two productions of the same non-terminal share a common prefix, the parser cannot decide which one to pick using 1 lookahead symbol, causing a table conflict. Left factoring removes this common prefix so the parser can choose correctly. Hence left factoring is a necessary condition for LL(1), so this claim is true.

Step 4: Evaluate the claim that LL(1) parsers are more powerful than SLR parsers. This is false: the class of LL(1) grammars is a strict subset of the class of SLR(1) grammars, every LL(1) grammar is SLR(1) but not vice versa, so SLR parsers are strictly more powerful, not the other way round.

Step 5: Only the left-factoring statement is true, so the answer is option C.

\[ \boxed{\text{Option C is correct}} \]