For the grammar below, a partial LL(1) parsing table is also presented along…

Solution:

Compute FIRST sets.

1. FIRST(S) = {a, b, ε} because S → a A b B, S → b A a B, and S → ε.

2. FIRST(B) = FIRST(S) = {a, b, ε} because B → S.

3. FIRST(A): from A → S B include FIRST(S) \{ε} = {a, b}. Since S can produce ε, also include FIRST(B) which contains ε, so FIRST(A) = {a, b, ε}.

Compute FOLLOW sets.

1. Start: FOLLOW(S) contains $ because S is the start symbol.

2. From S → a A b B and S → b A a B, A is followed by b or a, so add {a, b} to FOLLOW(A). Thus FOLLOW(A) ⊇ {a, b}.

3. From A → S B: for S before B, add FIRST(B) \{ε} = {a, b} to FOLLOW(S). Because FIRST(B) contains ε, also add FOLLOW(A) to FOLLOW(S).

4. From B → S: S is at the end, so add FOLLOW(B) to FOLLOW(S).

5. From S → ... B (B at the end of S-productions), add FOLLOW(S) to FOLLOW(B).

Solve these inclusions:

• FOLLOW(A) = {a, b} (no other symbols follow A in the grammar).

• FOLLOW(S) must include $ and {a, b} (from the relations), so FOLLOW(S) = {a, b, $}.

• FOLLOW(B) includes FOLLOW(S) and FOLLOW(A), giving FOLLOW(B) = {a, b, $}.

Final answer:

• FIRST(A) = {a, b, ε} = FIRST(B)

• FOLLOW(A) = {a, b}

• FOLLOW(B) = {a, b, $}