CS606 Assignment#3 Solution & Discussion Due Date:29-11-2011

[Sajidsd]

Question Statement:                                                                         [10] Consider the following grammar:             S à 1AB/ε             A à 1AC/0C             B à 0S             C à 1 And test that weather grammar is LL (1) or not.  Hint: Calculate First and Follow.              Note: Your answer must follow the below given specifications. Marks will be deducted if you do not follow these instructions.  Font style: “Times New Roman”  Font color: “Black”  Font size: “12”  Bold for heading only.  Font in Italic is not allowed at all. You should consult recommended books to clarify your concepts. It’s better for you to submit the assignment well before the deadline.

   Do not put any query at MDB about this assignment, if you have any query then  email at [e-mail]

[+ M.Tariq Malik]

Please Discuss here all about this assignment .thanks

[shaheen]

sir please koi idea solution jaldi se upload kren. aj last date he. please............................

[fari]

i want the idea solution of cs606 3rd assignment.......

[shaheen]

please some one share the solution

[ms]

please allah waloo help karo

[Sajidsd]

Samajh say bahir hai ye subject aur references bhi bh=ohat difficult hain...Concepts clear hi nahi hotay....

[Sajidsd]

Plzzz listen abhi 3rd Assignment hui nahi aurrrr LMS payee aap sab kay liayee assignment No 4 ka gift bhi pash kar dia gia hai.........................

[Iftikhar hassan]

Reffer the link below for refference.

www.cs.virginia.edu/~cs415/reading/FirstFollowLL.pdf

[Rana Muhammad Usman]

To check if a grammar is LL(1), one option is to construct the LL(1) parsing table and check for any conflicts. These conflicts can be

• FIRST/FIRST conflicts, where two different productions would have to be predicted for a nonterminal/terminal pair.
• FIRST/FOLLOW conflicts, where two different productions are predicted, one representing that some production should be taken and expands out to a nonzero number of symbols, and one representing that a production should be used indicating that some nonterminal should be ultimately expanded out to the empty string.
• FOLLOW/FOLLOW conflicts, where two productions indicating that a nonterminal should ultimately be expanded to the empty string conflict with one another.

Let's try this on your grammar by building the FIRST and FOLLOW sets for each of the nonterminals. Here, we get that

FIRST(X) = {a, b, z}

FIRST(Y) = {b, epsilon}

FIRST(Z) = {epsilon} 

We also have that the FOLLOW sets are

FOLLOW(X) = {$}

FOLLOW(Y) = {z}

FOLLOW(Z) = {z}

From this, we can build the following LL(1) parsing table:

    a    b    z   $

X   a    Yz   Yz  

Y        bZ   eps

Z             eps

Since we can build this parsing table with no conflicts, the grammar is LL(1).

To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following:

(1)

X' -> .X

X -> .Yz

X -> .a

Y -> .

Y -> .bZ

(2)

X' -> X.

(3)

X -> Y.z

(4)

X -> Yz.

(5)

X -> a.

(6)

Y -> b.Z

Z -> .

(7)

Y -> bZ.

From this, we can see that the grammar is not LR(0) because there are shift/reduce conflicts in states (1) and (6). Specifically, because we have the reduce items Z → . and Y → ., we can't tell whether to reduce the empty string to these symbols or to shift some other symbol. More generally, no grammar with ε-productions is LR(0).

However, this grammar might be SLR(1). To see this, we augment each reduction with the lookahead set for the particular nonterminals. This gives back this set of SLR(1) configurating sets:

(1)

X' -> .X

X -> .Yz [$]

X -> .a  [$]

Y -> .   [z]

Y -> .bZ [z]

(2)

X' -> X.

(3)

X -> Y.z [$]

(4)

X -> Yz. [$]

(5)

X -> a.  [$]

(6)

Y -> b.Z [z]

Z -> .   [z]

(7)

Y -> bZ. [z]

Now, we don't have any more shift-reduce conflicts. The conflict in state (1) has been eliminated because we only reduce when the lookahead is z, which doesn't conflict with any of the other items. Similarly, the conflict in (6) is gone for the same reason.