The Gateway to Computer Science Excellence
+1 vote
249 views

 

Consider the following grammar which is not LL(1) because LL(1) table contain multiple entry for same production.
The number of entries have multiple productions in LL(1) table are ________.

in Compiler Design by Active (1.3k points)
edited by | 249 views
+3

S->aAbB/bAaB/∈      First(S)={a,b,∈}         

                               Follow(S)={$,Follow(A),Follow(B)}

                               ={$,a,b}

A->S                               First(A)=First(S)={a,b,∈}  Follow(A)={a,b}

B->S                                First(B)=First(S)={a,b,∈}  Follow(B)={Follow(S)}={$,a,b}

 

  a b $
S S->aAbB, S->∈ S->bAaB, S->∈ S->∈
A A->S A->S  
B B->S B->S B->S

Ans: 2 mutiple entries

+1
Thank you very much. I was able to understand my mistake.
0
I didn't get why B->S is in $ terminal too. and what is difference between A production and this one if placed. Production should be in FIRST(S). Please explain. Thanks!
+2
See the follow of A and B. They are different and that is what makes the difference..

From S->aAbB we get Follow(A) ={b} Follow(B)=Follow(S)

From S->bAaB  we get Follow(A)={a} and Follow(B)=Follow(S)

So, Follow(A)={a,b} , Follow(B) =Follow(S)

From A->S we get Follow(S)=Follow(A)

From B->S we get Follow(S)=Follow(B)

S is the starting terminal so Follow(S)={ Follow(A) +  Follow(B) + \$} =

{\$, a,b + Follow(B)}

We have seen Follow(B)=Follow(S) so place it there

Follow(S) = {\$,a,b, Follow(S)}  = {a,b, \$}

Now we can get Follow(B) = {a,b, \$ }
0
Since First(B) contains ∈, we have to place the ∈ generating productions in the Follow(B) as well.
0
Whenever we put productions in LL1 table, we figure out,  FIRST(RHS) of production. So FIRST(S) contains Epsilon so we have to put this too in FOLLOW(LHS) i.e. FOLLOW(B). Thanks for clarification!
0

@MiNiPanda

\${ or \$}    is used for latex , if you want to use them as normal text then use \\\$ in your text

0
Hello Sir @Shaik Masthan, how to mention somebody like you mentioned MiNiPanda?
0
just drag their username into the text box... But note that,it is not create any new notification to them until they previously respond on the discussion ( i mean if i add some other persons except four members whose are join in this discussion, they never get the notification )
0

Alright Shaik Masthan, thanks!

0
The only correct explanation
0

why this is wrong??

  a b $
S S->aAbB, S->∈ S->bAaB, S->∈ S->∈
A

A->S

$A->\epsilon$

A->S

$A->\epsilon$

 
B

B->S

$B->\epsilon$

B->S

$B->\epsilon$

$B->\epsilon$

6 cells have multiple entry??

+1

@Gate Fever

is there any productions like

A −>ϵ   or   B −>ϵ

in the given grammar ?

0
no!

but if first of any non terminal  has $\epsilon$ then in follow we write that non terminal ->$\epsilon$
+1
then you are in wrong way... please read the concept one more time !
0

LL(1) parsing definition :-

for each production A-> $\alpha$

1)for each terminal a in first($\alpha$) ;add A->$\alpha$ in M[A,a]

2)if $\alpha$ is nullable ,then for each terminal a in follow(A) , add A->$\epsilon$ in M[A,a]

that is also what I was doing in this example!

pls @Shaik Masthan sir,tell me where am i going wrong?

+1

LL(1) parsing definition :-

for each production $\color{green}{A-> α}$

1) for each terminal a in first(αα) ;add A->α in M[A,a]

2) if α is nullable , then for each terminal a in follow(A) , $\color{red}{add\; A->ϵ \;in\; M[A,a]}$

it is  $\color{green}{add\; A->α \;in\; M[A,a]}$

0
let me see some more examples on this!
+1

actually it is a gate question https://gateoverflow.in/43312/gate2012-53

0
i was having doubt in this question when i was solving prev year qn too!

one more thing

either u say add A->$\alpha$ or i say A->$\epsilon$ , i think both means same because $\alpha$ itself is nullable!!

so even if u are saying add A->$\alpha$ if $\alpha$ here is nullable, then it means A->$\epsilon$ only, isn't it??
0

okay,okay now I got my mistake @Shaik Masthan sir pls check this now,

if A->$\alpha$

if first($\alpha$) has $\epsilon$ then if A has production like A->$\epsilon$ then in all the terminals in follow(A) we put A->$\epsilon$

and if A dont have null production then in terminals in follow(A) we put A->$\alpha$

am i right now??

+3

a small correction needed !

let take A -> α | ϵ

if A -> α also lead to empty string, then you have to keep both A -> α and A -> ϵ productions in Follow(A).

 

in simple terms,

First separate the productions like 

A --> α | β    ===========>  A -> α   and A --> β

then take each production, apply first of RHS but not LHS.

keep A -> α  in First(α) , if  First(α) contains ϵ, then keep A -> α  in Follow(A)

0
thanku very much sir!!

i got it

yess, first of RHS not LHS, edited my comment!
0

@Shaik Masthan sir, 

Here B -> S

first(s) = { a, b, € }

So for each terminal t (excluding €) we will put B -> S

IE: M[B, a] = B -> S 

And M[B, b] = B -> S

Now as first(s) contains €, so will put B -> S for each terminal t in follow(B).

Follow(B) = { a, b, $ }

So M[B, $] also contains B -> S

Is it correct?? 

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
193,840 comments
94,030 users