Direction: For the grammar below, a partial LL (1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2 and E3. ε is the empty string, $ indicates end of input and | separates alternate right hand sides of productions.
S → a A b B | b A a B | ε
A → S
B → S
-
The appropriate entries for E1, E2 and E3 are
-
- E1 : S → aAbB, A → S
E2: S → bAaB, B → S
E3: B → S
- E1 : S → aAbB, S → ε
E2 : S → bAaB, S → ε
E3 : S → ε
- E1 : S → aAbB, S → ε
E2 : S → bAaB, S → ε
E3 : B → S
- E1 : A → S, S → ε
E2 : B → S, S → ε
E3 : B → S
- E1 : S → aAbB, A → S
Correct Option: C
Entry E for [S, a] = {S → aAbB, S → ∈} S → aAbB
First (aAbB) = {a}
S → aAbB
First (bAaB) = {b}
Put (S → ∈) production as per follow (S)
Follow (S) = {a, b, $}
Hence, (S → ∈) will come in [S, a], [S, b] and [S, $]
Entry E2 for [S, b] = {S → bAaB, S → ∈}
Entry E3 for [B, $] = {B → S}
Production {B → S} will come in as per
First (S) = {a, b, ∈}
Hence, put B → S in [B, a] [B, b]
First (S) contains ∈ so consider [S, $]
Put [B → S] in [S, $]
