Consider the following context-free grammar where the start symbol is S and the set of terminals is {a,b,c,d}.S→AaAb∣BbBaA→cS∣ϵB→dS∣ϵThe following is a partially-filled LL(1) parsing table.
a
b
c
d
$
S
S→AaAb
S→BbBa
(1)
(2)
A
A→ϵ
(3)
A→cS
B
(4)
B→ϵ
B→dS
Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?Note: In the options, "blank" denotes that the corresponding cell is empty.
Correct answer
(A) (1) S arrow AaAb (2) S arrow BbBa (3) A arrow ε (4) B arrow ε
Solution
To determine the entries in the LL(1) parsing table, we first compute the First and Follow sets for the non-terminals.1. Compute First Sets:
First(A)={c,ϵ} (from A→cS∣ϵ)
First(B)={d,ϵ} (from B→dS∣ϵ)
First(S):
For S→AaAb: First(AaAb)=(First(A)∖{ϵ})∪First(aAb)={c}∪{a}={a,c}.
For S→BbBa: First(BbBa)=(First(B)∖{ϵ})∪First(bBa)={d}∪{b}={b,d}.
Thus, First(S)={a,b,c,d}.
2. Compute Follow Sets:
Follow(S) includes $ (start symbol).
From S→AaAb:
The first A is followed by a, so a∈Follow(A).
The second A is followed by b, so b∈Follow(A).
Therefore, Follow(A)={a,b}.
From S→BbBa:
The first B is followed by b, so b∈Follow(B).
The second B is followed by a, so a∈Follow(B).
Therefore, Follow(B)={a,b}.
3. Fill the Parsing Table Cells:
Cell (1) for (S,c): Since c∈First(AaAb), the entry is S→AaAb.
Cell (2) for (S,d): Since d∈First(BbBa), the entry is S→BbBa.
Cell (3) for (A,b): Since b∈Follow(A) and A→ϵ is a production, the entry is A→ϵ.
Cell (4) for (B,a): Since a∈Follow(B) and B→ϵ is a production, the entry is B→ϵ.
Matching these results with the options: (1) S→AaAb (2) S→BbBa (3) A→ϵ (4) B→ϵThis corresponds to Option (A).
