2 2 votes check whether the following grammer is ll(1) grammar or not and also find the table entry of [A,a]. S ->A, A->aB/Ab, B->bBC/d, C->d Why is this not a LL(1) grammar? Compiler Design compiler-design ll-parser + – khushtak 1.8k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 8 8 votes It is not LL(1). For a grammar to be LL(1), it should be unambiguous, should be deterministic and should not have left recursion. The production A->Ab is left recursive. Therefore, it is not a LL(1) grammar. monanshi answered Dec 12, 2015 • selected Dec 12, 2015 by Pooja Palod monanshi comment Share Follow See all 3 Comments 3 3 Comments reply khushtak commented Dec 12, 2015 reply Follow flag Yaa... You are right but why cant we remove this left recursion? And i also read that first(bBC) ^follow(B) =null this should be null and here terminal b is common... 0 0 replyShare monanshi commented Dec 12, 2015 reply Follow flag Yes, you can remove left recursion. Don't grab any formula. Just see, there should not be 2 productions under the same entry in the table. If you find more than 1, then the grammar is not LL(1). 2 2 replyShare Arjun commented Dec 12, 2015 reply Follow flag We can remove left recursion- but that produces a different grammar. Having left recursion is sufficient to say the given grammar is not LL(1). Now, if we can have an equivalent LL(1) grammar (predictive parser) for it is a different question. 4 4 replyShare Please log in or register to add a comment.
2 2 votes No it will not be LL(1) Because First (S) ={a} First(A)={a}⋂{a} ={a} !=NULL First(B)={b}⋂{d}=∅ First(C)={d} for First(A) it will be not LL(1), because for LL(1) there First(A) should be NULL srestha answered Dec 12, 2015 • edited Dec 12, 2015 by srestha srestha comment Share Follow See all 3 Comments 3 3 Comments reply Arjun commented Dec 12, 2015 reply Follow flag Any reference for this intersection rule? 0 0 replyShare Arjun commented Dec 12, 2015 reply Follow flag http://www.csd.uwo.ca/~moreno/CS447/Lectures/Syntax.html/node14.html This is the correct rule. In the given question B and C are coming one after another. There is no point in taking intersection of their FIRST sets. We take intersection of FIRST sets when B and C are choices of a production like B | C. 0 0 replyShare srestha commented Dec 12, 2015 reply Follow flag yes corrected :) 0 0 replyShare Please log in or register to add a comment.
