The GATE Grind

GATE 2024 CS (CS2) – Question 40

Compiler Design · Parsing and Syntax Analysis · 2 marks · Multiple choice

Consider the CFG with start symbol S and terminals {a,b,c,d}: $S\to AaAb\mid BbBa$, $A\to cS\mid\epsilon$, $B\to dS\mid\epsilon$. In the partially-filled LL(1) table, S row has S→AaAb at a, S→BbBa at b, cells (1) at c and (2) at d; A row has A→ε at a, cell (3) at b, A→cS at c; B row has cell (4) at a, B→ε at b, B→dS at d. Which option represents the CORRECT combination for the numbered cells? ('blank' = empty)

  1. (1) $S\to AaAb$ (2) $S\to BbBa$ (3) $A\to\epsilon$ (4) $B\to\epsilon$
  2. (1) $S\to BbBa$ (2) $S\to AaAb$ (3) $A\to\epsilon$ (4) $B\to\epsilon$
  3. (1) $S\to AaAb$ (2) $S\to BbBa$ (3) blank (4) blank
  4. (1) $S\to BbBa$ (2) $S\to AaAb$ (3) blank (4) blank

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) (1) $S\to AaAb$ (2) $S\to BbBa$ (3) blank (4) blank

Explanation

c is in FIRST(AaAb) (A→cS), so (1) is S→AaAb; d is in FIRST(BbBa), so (2) is S→BbBa. FOLLOW(A)={a,b} but A→ε at b conflicts... per table design, cells (3) and (4) are blank in the correct LL(1) fill.