2 votes 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 asked Dec 12, 2015 retagged Jul 4, 2019 by Cristine khushtak 1.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 8 votes 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 See all 3 3 Comments reply khushtak commented Dec 12, 2015 reply Follow Share 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 votes 0 votes monanshi commented Dec 12, 2015 reply Follow Share 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 votes 2 votes Arjun commented Dec 12, 2015 reply Follow Share 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 votes 4 votes Please log in or register to add a comment.
2 votes 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 See all 3 3 Comments reply Arjun commented Dec 12, 2015 reply Follow Share Any reference for this intersection rule? 0 votes 0 votes Arjun commented Dec 12, 2015 reply Follow Share 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 votes 0 votes srestha commented Dec 12, 2015 reply Follow Share yes corrected :) 0 votes 0 votes Please log in or register to add a comment.