Consider the grammar shown below S → i E t S S' | a S' → e S | ε E → b In the…
2003
Consider the grammar shown below
S → i E t S S' | a
S' → e S | ε
E → b In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are
- A.
{S' → e S} and {S' → e}
- B.
{S' → e S} and {}
- C.
{S' → ε} and {S' → ε}
- D.
{S' → e S, S'→ ε} and {S' → ε}
Attempted by 69 students.
Show answer & explanation
Correct answer: D
Compute First and Follow for S' and use them to fill the parsing table entries.
First sets:
S' → e S gives terminal e, and S' → ε gives ε, so First(S') = {e, ε}.
Follow sets:
S is the start symbol, so $ ∈ Follow(S).
From S → i E t S S': S is followed by S', so add First(S')\{ε} = {e} to Follow(S). Since S' can be ε, Follow(S) and Follow(S') include each other, so both Follow(S) and Follow(S') contain {e, $}.
Therefore Follow(S') = {e, $}.
Fill the predictive parse table entries for S':
For input e: include S' → e S because e ∈ First(e S). Also include S' → ε because ε ∈ First(S') and e ∈ Follow(S'). So M[S', e] = {S' → e S, S' → ε}.
For input $: include S' → ε because $ ∈ Follow(S') and ε ∈ First(S'). So M[S', $] = {S' → ε}.
Final answer: M[S', e] = {S' → e S, S' → ε} and M[S', $] = {S' → ε}.