GATE 2026 CS (CS1) – Question 28

Compiler Design · Parsing and Syntax Analysis · 1 mark · Multiple select

Which of the following statements is/are true?

Show answer and explanation

Correct answer: (C) For a grammar to be LL(1), it must be left-factored

Explanation

(A) is false: LL(1) is a deterministic predictive top-down parser that uses a 1-token lookahead to uniquely choose the production without backtracking.
(B) is false: Left-recursive grammars can NEVER be LL(1) because left-recursion causes infinite loops in top-down parsing and multiple entries in the LL(1) parsing table.
(C) is true: An LL(1) grammar cannot have common prefixes in alternate productions for the same non-terminal; left factoring must be applied so the lookahead token can deterministically distinguish between alternatives.
(D) is false: Bottom-up parsers like SLR(1) are strictly more powerful than LL(1) parsers (the class of LL(1) grammars is a strict subset of LR(1) and largely contained within SLR(1)).

Therefore, option (C) is the only true statement.