The Gateway to Computer Science Excellence
+1 vote
987 views
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 by Boss (12.2k points) | 987 views
0
If CFG is ambiguous then LR(1) cannnot parse it because it will result into conflicts.
0
but if CFG is determintic then LR parser can parse..right??
0
@Akirti right.
0
@Akriti

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

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

+1
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..

by Boss (19.8k points)
0
@sudsho..in 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??
0
every CFL can't be parsed
every DCFL can be parsed
0
no LL(1) cant parse any DCFL..we have one to one correspondance of LR parsers with DCFl nt LL(1)
0
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.
thankyou
0
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 grammar..so we can also create a LR parser too

but CFLs can be inherently ambiguous means not even a single unambiguous grammar existing...so LR parsers are nt always possible with CFLs
for CFLs we have one to one correspondance ith CFGs..
0
@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
0
what if ur DCFL have left recursion..then how LL(1) will do?
+1
Yes. @susdhso you are right.
+1
@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)
+2
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
+1
if a non determinitics CFL is not inherently ambiguous can it be parsed by some LR(1) parser??
0
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
0
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,212 comments
104,903 users