Log In
2 votes
can LR(1) parser parse any context free grammar/language ??

and hence evry regular lamguage can be parsed by LR(1) parsers??
in Compiler Design 1.5k views
If CFG is ambiguous then LR(1) cannnot parse it because it will result into conflicts.
but if CFG is determintic then LR parser can parse..right??
@Akirti right.

Yes LR(1) can parse provided there should be no SR and RR conflicts while making it
what about LR(0) parsers??can they also parse any DCFL??

@Ashwani Kumar 2 , but LR(1) cannot parse Non-deterministic unambiguous grammar, right? 

For a non deterministic CFL, we can have an unambiguous grammar which can parse it, in that case we can have a LR(1) parser for it. But if the non deterministic CFL is inherently ambiguous we do not have any unambiguous grammar for it, in that case it fails to be LR grammar.

Every DCFL has an unambiguous grammar for it. Hence it can never be inherently ambiguous.

1 Answer

3 votes

can LR(1) parser parse any context free grammar/language ??
NO..CFLs are sometime inherently ambiguous..we cant design a LR parser for ambiguous languagaes 

and hence evry regular language can be parsed by LR(1) parsers??
Yes..every regular language can be parsed by a LR parser..because for every regular language there is some unambiguous grammar for sure....moreover we can create a LR parser to parse a DCFl means reglar language can also be parsed..

0 last you said "moreover we can create a LR parser to parse a DCFl means reglar language can also be parsed.."

that means for dcfl,we have a LR parser,but above that you are saying evry dcfl cannot be parsed..

i am confused

and what about LL(1) parser?can it parse any DCFL??
every CFL can't be parsed
every DCFL can be parsed
no LL(1) cant parse any DCFL..we have one to one correspondance of LR parsers with DCFl nt LL(1)
ooh sorry,i missed deterministic part.
and DCFL can be parsed by any LR parser..right?it is not just LR(1)..?pls confirm this.
yes..reason is simple..what kind of grammar we need to make a LR parser?
unambiguous right?
and for every DCFL or regular language we can create such unambiguous we can also create a LR parser too

but CFLs can be inherently ambiguous means not even a single unambiguous grammar LR parsers are nt always possible with CFLs
for CFLs we have one to one correspondance ith CFGs..
@sudsho I think LL(1) can parse every DCFL. Isn't that true??? Yes I under there will not be one to one correspondence. Can you give an example of DCFl not parsed by ll(1)?? will be helpful
what if ur DCFL have left recursion..then how LL(1) will do?
Yes. @susdhso you are right.
@rahul,no LL(1) parsers can tparse any DCFL as

take this B-> a | aS

         S-> b|c

here first(a) and first a(S) are same,hence not LL(1)
All DCFL'S can be parsed by LR(1) parser

and every regular grammar is DCFL , Hence all regular grammars can be parsed by LR(1) grammar
if a non determinitics CFL is not inherently ambiguous can it be parsed by some LR(1) parser??
it cannot be parsed then the ambiguity problem of grammers would be decidable because every unambiguos grammer if can be parsed by LR parsers we can check if grammer is ambiguous or not by finding an LR parser for it hence every unambiguos grammer cannot be parsed by LR  parsers
Can anyone please answer my query below?

Can LR(1) parse a non-deterministic grammar producing DCFL (deterministic context free language)?

I feel the answer is No because let’s consider this trivial Non-deterministic grammar. It is a regular language, hence it is DCFL

S → a/ab

This will cause a shift/reduce conflict

Related questions

3 votes
0 answers
Which of the Parsers from LL(1), LR(0), SLR(1), LALR(1) and CLR(1) can Parse the following grammar ? $\tt E \rightarrow ET | a$ $\tt T \rightarrow TE | b$
asked Nov 1, 2016 in Compiler Design santhoshdevulapally 284 views
2 votes
2 answers
S-> AB|d A->aA|b B->bB|c Is the above grammar both LL(1) and LR(0)?
asked Jan 18, 2018 in Compiler Design Tuhin Dutta 652 views
6 votes
3 answers
Suppose we are given a grammar and asked to find the type of that grammar , what is the algorithm which needs to be followed for each of them? LL(1), OR LR(0) , OR CLR(1) OR LALR(1)
asked Nov 13, 2017 in Compiler Design Parshu gate 4.6k views