Section A (2 × 5 = 10 marks)

1. Answer any two. Each question carries 5 marks.
   1. Given the grammar:
      A → Aα | β
      a) Explain why a top-down parser cannot handle this grammar.
      b) Prove with parse tree and derivation how it leads to infinite recursion.
      c) Propose and justify a conversion to an equivalent right-recursive grammar.
   2. Given:
      S → iEtS | iEtSeS | a
      a) Construct leftmost derivations for the string iEtSeSa.
      b) Prove that the grammar is ambiguous.
      c) Can this grammar be converted to LL(1)? Justify your answer.
   3. Given grammar:
      S → Aa | b
A → Ac | Sd | ε
      a) Compute First() and Follow() sets for all non-terminals.
      b) Is the grammar LL(1)?
      c) Justify with the intersection condition:
          If First(α) ∩ First(β) ≠ ∅ or First(α) ∩ Follow(A) ≠ ∅ when ε ∈ First(α), then not LL(1)

Section B (2 × 10 = 20 marks)

2. Answer any two. Each question carries 10 marks.
   1. Given:
      S → SaSb | a
      a) Eliminate left recursion with complete steps.
      b) Compute First and Follow sets.
      c) Construct the LL(1) parsing table.
      d) Simulate parsing for input string "aabb" using stack operations.
   2. Given:
      S → aAB | aBC | aAC | bB | b
A → x | ε
B → y | z
      a) Perform left factoring and simplify the grammar.
      b) Identify whether it's LL(1) using all 3 rules (First-Follow disjointness).
      c) Construct the LL(1) parsing table.
   3. Design an LL(1) predictive parser for the grammar:
      E → E + T | T
T → T * F | F
F → (E) | id
      a) Remove left recursion and convert to right-recursive form.
      b) Compute First and Follow sets.
      c) Construct the LL(1) table.
      d) Simulate parse for "id + id" step-by-step with stack trace.