Question

Q5: (20 points) Consider the following grammars T → int | float L → L,id I id a) Perform the pairwise disjointness test for grammar (I).

Answer 1

Answer a:

Pairwise disjointness test for grammar (I):

For S->AbB | bAc, Disjointness of First(S) : First(AbB) First(bAc) = $\phi$ . S->AbB | bAc is disjoint.

"a: Pairwise disjointness test for grammar (I): For S- > AbB

For A->Ab | aBB, Disjointness of First(A) : First(Ab) First(aBB) = {a} $\neq$ $\phi$ . A->Ab | aBB is not disjoint.

"a: Pairwise disjointness test for grammar (I): For S- > AbB

For B->Ac | cBb | c, Disjointness of First(B) : First(Ac)
"a: Pairwise disjointness test for grammar (I): For S- > AbB
First(cBb)
"a: Pairwise disjointness test for grammar (I): For S- > AbB
First(c) = {c} $\neq$ $\phi$ . B->Ac | cBb | c is not disjoint.

Answer b:

No, grammar (I) is not LL(1) because grammar productions are not disjoint.

To be specific, in A->Ab | aBB, First(Ab) $\cap$ First(aBB) = {a} $\neq$ $\phi$ and in B->Ac | cBb | c, First(Ac)
"a: Pairwise disjointness test for grammar (I): For S- > AbB
First(cBb)
"a: Pairwise disjointness test for grammar (I): For S- > AbB
First(c) = {c} $\neq$ $\phi$ and hence compiler cannot decide which production Ab or aBB should parse.

Answer 3:

By creating DFA with LR(0) items of grammar (II), it is clear that grammar has no conflict states.

In below picture, the content of stack is shown while parsing through Bottom up parsers like LR(0).

Below is brief idea, how string is reduced to starting symbol S, via its grammar productions.

Although grammar (II) is left recursive but since in LR(0) there is no lookahead while constructing the DFA using grammar. So, whether it is left recursive or right recursive, no grammar would cause any problem.