Perform the pairwise disjointness test for the following grammar rules.
1. S ? aSb | bAA
2. A ? B{aB} | a
3. B ? aB | a
The Correct Answer and Explanation is:
To perform the pairwise disjointness test on grammar rules, we check whether each alternative in a rule has disjoint (non-overlapping) FIRST sets. This ensures that a predictive parser (like an LL(1) parser) can decide which production to use by looking at only the next input symbol.
1. Rule: S → aSb | bAA
Alternatives:
- aSb
- bAA
FIRST(aSb) = {a}
FIRST(bAA) = {b}
✅ Disjoint: {a} ∩ {b} = ∅ → PASS
2. Rule: A → B aB | a
Let’s analyze each part.
First, we need FIRST(B) to compute FIRST(B aB).
3. Rule: B → aB | a
All productions of B start with ‘a’, so:
FIRST(B) = {a}
Now go back to Rule 2:
- FIRST(B aB) = FIRST(B) = {a}
- SECOND alternative is just ‘a’ → FIRST(a) = {a}
So, FIRST(B aB) = {a}
FIRST(a) = {a}
❌ Not disjoint: {a} ∩ {a} ≠ ∅ → FAIL
3. Rule: B → aB | a
Alternatives:
- aB
- a
FIRST(aB) = {a}
FIRST(a) = {a}
❌ Not disjoint: {a} ∩ {a} ≠ ∅ → FAIL
✅ Summary of Pairwise Dis
The pairwise disjointness test is a method used to check if a grammar is suitable for predictive parsing (typically LL(1)). A grammar passes this test if, for each non-terminal with multiple production alternatives, the parser can unambiguously choose the correct production based solely on the next input symbol. This requires the FIRST sets of each alternative to be disjoint (non-overlapping).
For Rule 1: S → aSb | bAA, the FIRST sets are {a} and {b}, respectively. Since there’s no overlap, the parser can distinguish which production to choose when it sees either ‘a’ or ‘b’. Hence, Rule 1 passes the disjointness test.
In Rule 2: A → B aB | a, we first evaluate Rule 3 (B → aB | a) to get FIRST(B). Both alternatives of B begin with ‘a’, so FIRST(B) = {a}. Therefore, both B aB and a in Rule 2 start with ‘a’, resulting in overlapping FIRST sets. This ambiguity makes it impossible for a parser to choose the correct production without further lookahead, so Rule 2 fails the test.
Rule 3 (B → aB | a) also has both alternatives starting with ‘a’, resulting in identical FIRST sets. Hence, it also fails the pairwise disjointness test.
This test is critical in compiler design, especially for constructing efficient LL(1) parsers that require unambiguous decisions based on a single input token.
