1 votes 1 votes $L=\{x^n:n \in N\} \cup\{x^ny^n|n \in N\}$ This language does not have LL(k) parser while being deterministic context free.Why? Compiler Design compiler-design context-free-language ll-parser descriptive + – Ayush Upadhyaya asked Mar 3, 2019 retagged Jun 21, 2022 by Lakshman Bhaiya Ayush Upadhyaya 714 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Shaik Masthan commented Mar 3, 2019 reply Follow Share is this DCFL ? 0 votes 0 votes Arjun commented Mar 3, 2019 reply Follow Share yes. If we assume end delimiter is there. i.e., all strings end with a delimiter like '$'. 0 votes 0 votes Shaik Masthan commented Mar 3, 2019 reply Follow Share If we assume end delimiter is there then it is DCFL, in that case it should have LL(k) for some k right sir ? then there is no meaning in this question ! 0 votes 0 votes Arjun commented Mar 3, 2019 reply Follow Share No. DCFL is guaranteed to have only LR(1) not necessarily LL(k) 2 votes 2 votes Shaik Masthan commented Mar 3, 2019 reply Follow Share if it is LL(k) for some k, then it is LR(m) for some m. but converse not true ! Forgot that basic point, thanks sir !! 0 votes 0 votes Ayush Upadhyaya commented Mar 3, 2019 reply Follow Share @Arjun sir and @Shaik Masthan-I am trying to build a proof point out if anywhere I go wrong. The grammar can be $S->A|B\\A->xA|x\\B->xBy|xy$ For string let's say $w_1=x^3$ we need to use production $S->A$ and for string $w_2=x^3y^3$ we need to use the production $S->B$ So here we are in a dilemma which one to use. Similarly, for a given string of length say $n$, we are not sure how much of lookahead we need for each string so that production to be used at each step can be uniquely determined. So, the given language does not have an LL(K) parser for any fixed k. Am I going in the correct direction? 1 votes 1 votes Arjun commented Mar 3, 2019 reply Follow Share yes, intuitively that is correct 👍 Similar to why LR(k) is more powerful than LL(k). 0 votes 0 votes Shaik Masthan commented Mar 3, 2019 reply Follow Share sir, can you show in formal way, why it doesn't have any LL(k) parser? 0 votes 0 votes Arjun commented Mar 3, 2019 reply Follow Share I don't know a formal way. But the above reason by @Ayush Upadhyaya is sufficient. https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Till DCFL there exist a LR(K) parser. abhishekmehta4u answered Mar 3, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.