parser

Question

Does every DCFL has corresponding LR parser?

Answer 1

Yes LR(k) is generalisation and extension of LL(k) [top down parsers]..

And yes there is one to one correspondence between LR(k) grammar and DCFL class of languages..

In fact , for every DCFL , we have at least one of LR(1) or LR(0) grammar -- does not mean that any grammar for a DCFL is LR(1)

But if a DCFL is having prefix property ( meaning that no string of a given language is a prefix of other string of the same language ) , then that DCFL is guaranteed to have LR(0) grammar..

But all DCFLs need not have LL grammar..

Reference : Peter Linz chapter on deterministic context free languages and grammars (Chapter 7)

Comments

Every Regular Grammar can be converted to Right linear Grammar .

 

1) But is Every Right linear Grammar is LL(1) ==> NO

Ex A -> aA | abA | d

It is regular but not LL(1)

 

2) But is Every Left linear Grammar is LL(1) ==> NO

Obviously it will have left recursion .

 

3) Is Every LL(1) is Regular Grammar ==> NO

A- > aAb | bB

B-> d

LL(1) but not regular.

---

@jatin khachane 1

is "every regular language in  LL(1)" then we say yes becoz for every language we can write right recursive grammar ; hence in LL(1) ; but your ist point says that right recursive grammar is not in LL(1).

am i right??

---

@arjun sir Do we have any kind of diagram which can show us which grammar is accepted by which type of parsers

Answer 2

Answer is No. 

Bcoz every every Regular language is also a deterministic CFL not the other way round.

Now regula language is based on regular grammar which can be both left linear and right linear.

When a grammar is both Left recursive and right recusive, it is called ambiguous grammar.

Now the only bottom up parser which can accept ambiguous grammar is Operator precedence parser. 

LR parsers cannot accept accept ambiguous grammars.

Comments

But there exists an unambiguous grammar for DCFL class of languages right..Inherent ambiguity begins from CFL class of languages..

---

@Amitabh...

If a grammar has more than one left most derivation or more than one right most derivation then it will be embiguous.

If a grammar has one lest most derivation and one right most derivation the it will not be ambiguous.

And I thnk here we are only taking about LR parsers....

Operator precedence parser anyways accpets ambiguous grammar.

---

a regular grammar simultaneously  cant be left and right linear . it is either left or right linear but not both at same time. so it cant be ambigous.