⬇️ Top-down Parsing (LL(1))
Why it matters: Building and reading an LL(1) table, and removing left recursion, are frequent.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.
1Recursive descent and backtracking
2Left recursion and left factoring
3The LL(1) table and the LL(1) condition
4Predictive (stack) parsing
Formulas
LL(1) condition
for A → α | β: FIRST(α) ∩ FIRST(β) = ∅; and if ε ∈ FIRST(α) then FIRST(β) ∩ FOLLOW(A) = ∅
Immediate left recursion removal
A → Aα | β ⇒ A → βA′, A′ → αA′ | ε
Left factoring
A → αβ | αγ ⇒ A → αA′, A′ → β | γ
Parser steps (LL(1))
one step per derivation step plus one per matched terminal, so about |derivation| + |tokens|
Not LL(1) if
ambiguous, left-recursive, or not left-factored (commonly)
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Is the grammar LL(1)? / table entries
Compute FIRST/FOLLOW and look for a cell with two productions; count the filled cells.
★★★
Remove left recursion / left factor
Transform a grammar and identify the resulting productions.
★★★
Trace predictive parser
Stack contents after some steps, or number of steps to parse a string.
★★★
Properties of top-down parsers
True/false statements about left recursion, backtracking, LL(1) vs ambiguity.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
5 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
5 questions · 0 correct of 0 attempted · marks 0 / 10
Year:
GATE 2025 CS2 · Q51MSQ2 marks
Consider two grammars G1 and G2
G1: S → if E then S | if E then S else S | a E → b
G2: S → if E then S | M M → if E then M else S | c E → b. (if, then, else, a, b, c are terminals.)Which of the following option(s) is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q38MCQ2 marks
Consider the following grammar G with S as the start symbol, with three incomplete productions (1), (2), (3):
S → d a T | (1) T → a S | b T | (2) R → (3) | εThe set of terminals is {a, b, c, d, f}. FIRST(S) = {c, d, f}, FIRST(T) = {a, b, ε}, FIRST(R) = {c, ε}. FOLLOW(S) = FOLLOW(T) = {c, f, $}, FOLLOW(R) = {f}. Which option CORRECTLY fills in the incomplete productions?
GATE 2024 CS2 · Q40MCQ2 marks
Consider the context-free grammar with start symbol S and terminals {a, b, c, d}:
S → A a A b | B b B a A → c S | ε B → d S | εA partially filled LL(1) parsing table has: M[S,a] = S → AaAb, M[S,b] = S → BbBa, cell (1) = M[S,c], cell (2) = M[S,d]; M[A,a] = A → ε, cell (3) = M[A,b], M[A,c] = A → cS; cell (4) = M[B,a], M[B,b] = B → ε, M[B,d] = B → dS. Which option represents the CORRECT combination for the numbered cells?
GATE 2021 Set 1 · Q31MCQ2 marks
Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}:
S → d a T | R f T → a S | b a T | ε R → c a T R | εThe following is a partially-filled LL(1) parsing table (columns a, b, c, d, f, $): M[S,d] = S → daT; M[T,a] = T → aS; M[T,b] = T → baT; M[T,f] = T → ε; M[R,c] = R → caTR; M[R,f] = R → ε; cell ① = M[S,c], cell ② = M[S,f], cell ③ = M[T,c], cell ④ = M[T,$]. Which one of the following choices represents the correct combination for the numbered cells (blank denotes that the cell is empty)?
GATE 2012 Code A · Q53MCQ2 marks
(Same grammar and partial LL(1) table as the previous question.) The appropriate entries for E1, E2 and E3 are
Common traps
For a nullable α you must use FOLLOW(A), not just FIRST(α).
Left recursion can also be indirect (A → B…, B → A…).
LL(1) grammars are never ambiguous, but removing left recursion does not remove ambiguity.