Gate Genral Questions

Question

Consider the following Grammar :

S` -  > S#

S  -  >  ABC

A  -  >  a | bbD

B -  >  a | ε

C  - >  b | ε

D - > c | ε  

(i) Construct first and Follow sets for the grammar.

(ii)Design a LL(1) parsing using table for this grammar.Also parse 'bbcab' string using the parsing table.

Answer 1

First(S')={a,b}                         Follow(S')={$}

First(S)={a,b}                          Follow(S)={#}

First(A)={a,b}                          Follow(A)={a,b,#}

First(B)={a,∈}                          Follow(B)={b,#}

First(C)={b,∈}                          Follow(C)={#}

First(D)={c,∈}                          Follow(D)={a,b,#}

	a	b	c	#	$
S'	S` -  > S#	S` -  > S#
S	S  -  >  ABC	S  -  >  ABC
A	A  -  >  a	A  -  >  bbD
B	B -  >  a	B -  >  ∈		B -  >  ∈
C		C  - >  b |		C  - >  ε
D	D - >  ε	D - >  ε	D - > c	D - >  ε

S'->S 

 ->ABC

 ->bbDBC

->bbcBC

 ->bbcaC

 ->bbcab

Comments

@LeenSharma Sir , why follow of A,B,C and D not contain $ ???

Answer 2

first(S')={a,b}          follow(S')={$}
first(S)={a,b}          follow(S)={#}

first (A) ={a,b}        follow(A)={a,b,#}
first(B)={a,ε}           follow(B)={b,#}

first(C)={b,ε}          follow(C)={#}
first(D)={c,ε}         follow(D)={a,b,#}

	a	b	c	#	$
S'	S'->S#	S'->S#
S	S->ABC	S->ABC
A	A->a	A->bbD
B	B->a	B->ε		B->ε
C		C->b		C->ε
D	D->ε	D->ε	D->c	D->ε

So the grammer is LL(1) grammer

S'->S 

  ->ABC

  ->bbDBC

 ->bbcBC

 ->bbcaC

 ->bbcab

Comments

 shivanisrivarshini Boss

Aww sowwie i dint look properly.Yeah the answer is fine now thank you :) 

---

alokthebranded are u testing knowledge of the gateoverflow users or you are  asking your assignment questions. please ask your doubts only. 

---

Respected ,

its juz that i was having little querry/doubt while solving.ty to everyone .

Jaimatadii:)