Question

24. State if the following grammar rules as a group passes the pairwise disjointness test and tell why or why not? (4 pts)

Answer 1

The Pairwise disjoint test is used to check whether a grammar is LL grammar or not. The test is used to determine whether the RHS can be chosen using single token. If the grammar fails the pairwise disjoint test then the grammar cannot be used to create a top-down parser with one lookahead. For checking whether a grammar rule follows the pairwise disjointness test we need to find the FIRST for each production and if the answers are disjoint then the production passes the test.

a) For A -> aB|eAb|cBb

FIRST(aB) = a

FIRST(eAb) = e

FIRST(cBb) = c

This answers don't intersect and hence passes the test.

b) For B->dB|c

FIRST(dB) = d

FIRST(c) = c

This answers don't intersect and hence passes the test.