4 votes 4 votes 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 ________. Compiler Design compiler-design parsing made-easy-test-series + – Mizuki asked Aug 19, 2018 • edited Mar 4, 2019 by Aditi Singh Mizuki 2.6k views answer comment Share Follow See all 24 Comments See all 24 24 Comments reply MiNiPanda commented Aug 19, 2018 reply Follow Share 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 4 votes 4 votes Mizuki commented Aug 19, 2018 reply Follow Share Thank you very much. I was able to understand my mistake. 1 votes 1 votes iamkoushal21 commented Aug 19, 2018 reply Follow Share 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 votes 2 votes MiNiPanda commented Aug 19, 2018 i edited by Shaik Masthan Aug 29, 2018 reply Follow Share 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, \$ } 5 votes 5 votes Mizuki commented Aug 20, 2018 reply Follow Share Since First(B) contains ∈, we have to place the ∈ generating productions in the Follow(B) as well. 0 votes 0 votes iamkoushal21 commented Aug 20, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Aug 29, 2018 i edited by Shaik Masthan Aug 29, 2018 reply Follow Share @MiNiPanda \${ or \$} is used for latex , if you want to use them as normal text then use \\\$ in your text 0 votes 0 votes Mizuki commented Aug 29, 2018 reply Follow Share Hello Sir @Shaik Masthan, how to mention somebody like you mentioned MiNiPanda? 0 votes 0 votes Shaik Masthan commented Aug 29, 2018 reply Follow Share 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 votes 0 votes Mizuki commented Aug 29, 2018 reply Follow Share Alright Shaik Masthan, thanks! 0 votes 0 votes aditya7755 commented Dec 7, 2018 reply Follow Share The only correct explanation 0 votes 0 votes Gate Fever commented Dec 15, 2018 reply Follow Share 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?? 0 votes 0 votes Shaik Masthan commented Dec 15, 2018 reply Follow Share @Gate Fever is there any productions like A −>ϵ or B −>ϵ in the given grammar ? 1 votes 1 votes Gate Fever commented Dec 15, 2018 reply Follow Share no! but if first of any non terminal has $\epsilon$ then in follow we write that non terminal ->$\epsilon$ 0 votes 0 votes Shaik Masthan commented Dec 15, 2018 reply Follow Share then you are in wrong way... please read the concept one more time ! 1 votes 1 votes Gate Fever commented Dec 15, 2018 reply Follow Share 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 votes 1 votes Shaik Masthan commented Dec 15, 2018 reply Follow Share 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]}$ 3 votes 3 votes Gate Fever commented Dec 15, 2018 reply Follow Share let me see some more examples on this! 0 votes 0 votes Shaik Masthan commented Dec 15, 2018 reply Follow Share actually it is a gate question https://gateoverflow.in/43312/gate2012-53 2 votes 2 votes Gate Fever commented Dec 15, 2018 reply Follow Share 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?? 1 votes 1 votes Gate Fever commented Dec 16, 2018 i edited by Gate Fever Dec 16, 2018 reply Follow Share 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?? 0 votes 0 votes Shaik Masthan commented Dec 16, 2018 reply Follow Share 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) 4 votes 4 votes Gate Fever commented Dec 16, 2018 reply Follow Share thanku very much sir!! i got it yess, first of RHS not LHS, edited my comment! 0 votes 0 votes choudhury031 commented Jul 9, 2019 reply Follow Share @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?? 0 votes 0 votes Please log in or register to add a comment.