For the grammar below, a partial LL(1) parsing table is also presented along…
2012
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. \(\varepsilon\) is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.
S \(\to\) a A b B | b A a B | \(\varepsilon\)
A \(\to\) S
B \(\to\) S
The appropriate entries for E1, E2, and E3 are
- A.
E1: S
\(\to\)aAbB, A\(\to\)SE2: S
\(\to\)bAaB, B\(\to\)SE3: B
\(\to\)S - B.
E1: S
\(\to\)aAbB, S\(\to\)\(\varepsilon\)E2: S
\(\to\)bAaB, S\(\to\)\(\varepsilon\)E3: S
\(\to\)\(\varepsilon\) - C.
E1: S
\(\to\)aAbB, S\(\to\)\(\varepsilon\)E2: S
\(\to\)bAaB, S\(\to\)\(\varepsilon\)E3: B
\(\to\)S - D.
E1: A
\(\to\)S, S\(\to\)\(\varepsilon\)E2: B
\(\to\)S, S\(\to\)\(\varepsilon\)E3: B
\(\to\)S
Attempted by 133 students.
Show answer & explanation
Correct answer: C
Step 1 — FIRST sets:
FIRST(S) = {a, b, ε}
FIRST(A) = FIRST(S) = {a, b, ε}
FIRST(B) = FIRST(S) = {a, b, ε}
Step 2 — FOLLOW sets:
FOLLOW(S) = {a, b, $}
FOLLOW(A) = {a, b}
FOLLOW(B) = {a, b, $}
Step 3 — Fill the LL(1) parsing table:
Cell for nonterminal S and terminal a: place S -> a A b B (because this production starts with a). Also, because S can derive ε and a is in FOLLOW(S), place S -> ε in this cell as well.
Cell for nonterminal S and terminal b: place S -> b A a B (because this production starts with b). Also, because S can derive ε and b is in FOLLOW(S), place S -> ε in this cell as well.
Cell for nonterminal S and terminal $: place S -> ε (since ε is in FIRST(S), put S -> ε in every FOLLOW(S) terminal cell, including $).
Cells for nonterminal A and terminals a and b: place A -> S B (because FIRST(S) contains a and b and S can start with those).
Cells for nonterminal B and terminals a, b, and $: place B -> S. B -> S covers a and b because FIRST(S) has a and b, and it also occupies $ because S can derive ε and $ is in FOLLOW(B). (Thus E3 = B -> S.)
Conclusion: The filled entries are therefore:
E1 (S under a): S -> a A b B and S -> ε
E2 (S under b): S -> b A a B and S -> ε
E3 (B under $): B -> S
Note: Because the S row cells for a and b contain two productions each, the parsing table has conflicts and the grammar is not LL(1).
A video solution is available for this question — log in and enroll to watch it.