Top-down parsing

ACompressed recap

🧾

Top-down parsers build the tree from the start symbol and trace a leftmost derivation. Recursive descent uses one procedure per nonterminal; with ambiguous choices it backtracks. Predictive parsing avoids backtracking using FIRST (tokens that can begin a string; may include ε) and FOLLOW (tokens that can come after a nonterminal; $ for the start symbol; never ε). The LL(1) table puts A → α under FIRST(α), and under FOLLOW(A) when α is nullable; a grammar is LL(1) when no cell holds two productions.

BMerged rule card

2.3.1 Recursive-descent parsing and backtracking

• Top-down parsing: root to leaves, leftmost derivation.
• Recursive descent: one procedure per nonterminal; terminals matched with match().
• Backtracking: on failure restore input position and try the next alternative; exponential worst case.
• Predictive parsing: lookahead token selects the production; needs no left recursion, left factoring, disjoint starts.
• Left recursion → infinite recursion.

2.3.2 FIRST and FOLLOW sets

• FIRST(a) = {a}; X → ε adds ε; X → Y₁…Yₖ: add FIRST(Yᵢ)−ε while Y₁…Yᵢ₋₁ are nullable; all nullable ⇒ add ε.
• FOLLOW: $ ∈ FOLLOW(S); A → αBβ: FIRST(β)−ε ⊆ FOLLOW(B); β nullable or absent: FOLLOW(A) ⊆ FOLLOW(B).
• FOLLOW never contains ε; FIRST may.
• Compute nullable first; iterate to a stable result.

2.3.3 LL(1) table construction; the LL(1) test and conflicts; stack trace of parsing a string

• M[A, a] ∋ A → α for a ∈ FIRST(α); if ε ∈ FIRST(α), for every b ∈ FOLLOW(A) (incl. $).
• LL(1) ⇔ no cell has two productions.
• Never LL(1): left-recursive, ambiguous, not left-factored.
• Parser: stack $ S; terminal on top → match; nonterminal → replace by right side reversed; $ $ → accept.
• Outputs form the leftmost derivation; empty cell = error (panic mode: skip to FOLLOW).

CInterleaved GATE-style questions

Q1NAT1 markFOLLOW

For S → A a A b | B b B a, A → ε, B → ε, how many elements does FOLLOW(A) have?

Numerical answer: ________

Q2MCQ1 markLL(1)

For S → A a A b | B b B a, A → ε, B → ε, the grammar is:

• (A) LL(1)
• (B) not LL(1) because A and B are both nullable
• (C) ambiguous
• (D) left recursive

Q3MCQ2 marksFIRST

For S → A B C, A → a | ε, B → b | ε, C → c | ε, FIRST(S) is:

• (A) { a, b, c }
• (B) { a, b, c, ε }
• (C) { a }
• (D) { a, ε }

Q4MSQ1 markFacts

Which are true?

• (A) A recursive-descent parser traces a leftmost derivation.
• (B) FOLLOW of the start symbol contains $.
• (C) Every LL(1) grammar is unambiguous.
• (D) Left factoring is enough to make any grammar LL(1).

Q5NAT2 marksTable

How many non-empty cells does the LL(1) table of E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → ( E ) | id have?

Numerical answer: ________

Q6MCQ1 markConflict

In the left-factored dangling-else grammar, the LL(1) conflict is in the cell:

• (A) M[S′, e]
• (B) M[S, i]
• (C) M[E, b]
• (D) M[S′, $]

Q7MCQ1 markBacktracking

A backtracking recursive-descent parser:

• (A) cannot cope with left recursion
• (B) needs an LL(1) table
• (C) builds a rightmost derivation
• (D) never fails on valid input

Q8NAT2 marksFOLLOW

For S → a A B | b A, A → c A | ε, B → d | ε, what is |FOLLOW(A)| + |FOLLOW(B)|?

Numerical answer: ________

Q9MSQ2 marksTrace

During LL(1) parsing of id + id * id with the expression table, which productions are output?

• (A) T′ → ε (at least once)
• (B) E′ → + T E′
• (C) F → ( E )
• (D) T′ → * F T′