GATE CSE 2026 | Set 1 | Question: 18

Question

Which of the following statements is/are true?

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

Answer 1

$\boxed{\text{Answer: C}}$

Watch detailed discussion on this question

---

• A. $\text{LL(1)}$ parser uses backtracking. $\ \textcolor{red}{\boxed{\text{False}}}$

No, $\text{LL(1)}$ parser is a predictive parser. When expanding a nonterminal, $\text{LL(1)}$ parser predict the production to use by looking at the next token of the input. The decision is forced. So, $\text{LL(1)}$ parser is not using backtracking.

---

• A. For a grammar to be $\text{LL(1)}$, it must be left-recursive. $\ \textcolor{red}{\boxed{\text{False}}}$

No. In fact for a grammar to be $\text{LL(1)}$, it must not be left-recursive. Since left-recursive grammar can never be $\text{LL(1)}$. Proof1 Proof2

---

• A. For a grammar to be $\text{LL(1)}$, it must be left-factored. $\ \textcolor{blue}{\boxed{\text{True}}}$

Yes, because non-left-factored grammar can never be $\text{LL(1)}$. Proof

---

• A. The $\text{LL(1)}$ parsers are more powerful than the SLR parsers. $\ \textcolor{red}{\boxed{\text{False}}}$

No, there are some grammars which $\text{SLR}$ parser can parse but can't be parsed by $\text{LL(1)}$ parser. That is, some $\text{SLR}$ grammar is not $\text{LL(1)}$.

Consider the following grammar which is $\text{SLR}$ but not $\text{LL(1)}:$

$$S \rightarrow S A \text { | } A$$

$$S \rightarrow a$$

Actually, there is no relationship between $\text{LL(1)}$ parsers and $\text{SLR}$ parsers. That is, neither $\text{LL(1)}$ parsers are more powerful than the $\text{SLR}$ parsers nor $\text{SLR}$ parsers are more powerful than the $\text{LL(1)}$ parsers.

---

Goodread:

Source: https://people.cs.vt.edu/prsardar/classes/cs3304-Spr19/lectures/CS3304-10-LanguageSyntax-3.pdf

Source: https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/090%20Top-Down%20Parsing.pdf

Source: https://web.stanford.edu/class/cs143/lectures/lecture07.pdf

Source: Modern Compiler Implementation in C by Andrew Appel

Source: Ullman (Dragon Book)

Comments

for option 1 reference https://www.geeksforgeeks.org/compiler-design/introduction-of-parsing-ambiguity-and-parsers-set-1/

Answer 2

ANS (C) 

LL(1) parsers are predictive parsers.

• LL = Left to right scan, Leftmost derivation.
   
• (1) = Uses 1 lookahead symbol.

 

Since the parser already knows which production to choose using the parsing table and one lookahead token, 

there is no need to backtrack.

 

Also, 

LL(1) must not have left recursion 

LL(1) is not more powerful than SR(1) or SLR

LL(1) must not have FIRST-FIRST conflict

LL(1) must not have FIRST-FOLLOW conflict

LL(1) must not be ambiguous