Register

LR(k) and CFL

629 views
0 votes
0 votes
I am quite confused in this . I have seen in many answers related to LR(k), that DCFL have one to one correspondence with LR(k) grammars. Means if a language is DCFL then it would definitely have a LR(k) grammar and if there is an LR(k) grammar then the language corresponding to that would be a DCFL. THIS statement conclude that LR(k) grammars cannot parse any ncfl.

So, how for some unambiguous ncfl there exists an LR(k) grammar??? Please someone can provide a correct argument regarding this.
User Avatar

1 Answer

1 votes
1 votes

@Ankita87077

So, how for some unambiguous ncfl there exists an LR(k) grammar ..

Yes, bcoz languages defined by LR(k) grammars are called deterministic context free languages , which inturn implies that, there exists a DPDA for every LR(k) grammar...

class of languages parsed by LR(k) = DCFL's.

now no NCFL is DCFL, so NCFL's can't be parsed by LR(k).

LL(k) is even more restrictive than LR(k)...

 

1. https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars 

 

2. https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/090%20Top-Down%20Parsing.pdf 

 

3. https://gateoverflow.in/105785/ll-k-grammars 

 

4. https://gateoverflow.in/184982/ll-k 

 

5. https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars 

 

6. https://gateoverflow.in/177532/%23doubt

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
0 answers
1
radha gogia asked Dec 6, 2015
2,890 views
what is the relation between CFG , LL(K) ,LR(K) and regular grammars ?
I am unable to get the basic difference between these and which one are actually parsed by a top down parser and a bottom up parser ?
I am unable to get the basic difference between these and which one are actually parsed by a top down parser and a bottom up parser ?
User Avatar
0 votes
0 votes
0 answers
2
srestha asked Dec 26, 2017
190 views
Find LL(k) and LR(k)
Among NCFL, CSL and Recursive languages anyone is LL(k) or LR(k) Give some reason
Among NCFL, CSL and Recursive languagesanyone is LL(k) or LR(k)Give some reason
User Avatar
0 votes
0 votes
0 answers
3
rahul sharma 5 asked Nov 12, 2017
1,122 views
Compiler : LL(k) and LR(k) grammer
Can LL(k) and LR(k) gammer has null and unit productions?
Can LL(k) and LR(k) gammer has null and unit productions?
User Avatar
1 votes
1 votes
1 answer
4
AnilGoudar asked Sep 18, 2017
440 views
DCFL, LR(k), 2DFA
Let L1 be a language from DCFL, L2 be from LR(k) grammar, and L3 be a language accepted by 2DFA. Choose the correct statement, 1) There is no algorithm to decide if L1⋂L2 is empty. 2) L1 = L2. 3) L2 = L3. 4) A problem of L1 = L3 is undecidable.
Let L1 be a language from DCFL, L2 be from LR(k) grammar, and L3 be a language accepted by 2DFA.Choose the correct statement,1) There is no algorithm to decide if L1⋂L2...
User Avatar
Link Copied!