If CFG is ambiguous then LR(1) cannnot parse it because it will result into conflicts.

The Gateway to Computer Science Excellence

+1 vote

can LR(1) parser parse any context free grammar/language ??

and hence evry regular lamguage can be parsed by LR(1) parsers??

and hence evry regular lamguage can be parsed by LR(1) parsers??

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

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

+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

@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??

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

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

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

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

+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)

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

and every regular grammar is DCFL , Hence all regular grammars can be parsed by LR(1) grammar

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,291 answers

198,212 comments

104,903 users