[CD Grammar Doubt]

[Mayur Mahrotri]

What's the difference between LR(1) grammar and SLR(1) grammar ?

--
With Regards,
Mayur.

[harshjpathak]

when we say LR(1) grammar  it deliberately means CLR(1) grammar

[venkat rao]

HI mayur,
LR(1) means CLR(1)

[Mayur Mahrotri]

Thanks Sir,

 

Also, i wanted to know, the method to recognise, LR(0) and SLR(1) grammars.

 

Can you also, explain me this :

Someone told me that CLR is the highest class of grammars which can parse any grammar including ambiguous grammars.

 

Is this true ?

 

--
With Regards,
Mayur.

[Varun Shinde]

yes u r true!...the heirarchy of grammars are... highest to lowest..
CLR(1)=LR(1)
LALR(1)
SLR(1)=LR(0)
LL(1)

On Feb 7, 8:54 pm, Mayur Mahrotri <mayurmahro...@gmail.com> wrote:
> Thanks Sir,
>
> Also, i wanted to know, the method to recognise, LR(0) and SLR(1) grammars.
>
> Can you also, explain me this :
> Someone told me that CLR is the highest class of grammars which can parse
> any grammar including ambiguous grammars.
>
> Is this true ?
>

> On 2/5/10, venkat rao <toc.ven...@gmail.com> wrote:
>
>
>
> > HI mayur,
> > LR(1) means CLR(1)
>

[shripad sarade]

CLR(1) LALR(1) SLR(1) LR(0) LL(1)
They do not include Ambiguous grammar.

[Mayur Mahrotri]

LR(0) is not equal SLR(1), for that i am sure.

--
With Regards,
Mayur.

[Varun Shinde]

there in my post i mean to say is that....LR(0) items are required
for SLR(1) grammar...it does not mean that they are equal......
similarly LR(1) items are required for CLR(1) grammar.....
even if a grammar is not LR(0)..it can be SLR(1)......

On Feb 8, 11:06 pm, Mayur Mahrotri <mayurmahro...@gmail.com> wrote:
> LR(0) is not equal SLR(1), for that i am sure.
>

> On Sun, Feb 7, 2010 at 11:21 AM, shripad sarade <shripad.sar...@gmail.com>wrote:
>
>
>
>
>
>
>
> > CLR(1) LALR(1) SLR(1) LR(0) LL(1)
> > They do not include Ambiguous grammar.
>

[Mayur Mahrotri]

How do you check then, whether the grammar is LR(0) and SLR(1). ? I constructed all the LR(0) items, then ?

--
With Regards,
Mayur.

[Varun Shinde]

When u find all the LR(0) items,..i.e in the goto graph u have to chk
do u have any inadequate state,..if that inadequate state lead to a S-
R or R-R conflict then it is not LR(0) and also not SLR(1)..but
sometimes we have inadequate state but it do not lead to any of the
conflict after drawing the ACTION table....in that cas it is not
LR(0)..but it can be SLR(1)..this type of question is solved in our
notebook..chk that out....
that's SIR told that always in this type of question after chking for
LL1 , u should go for CLR(1) first then SLR(1)....
i hope it will help u!!!

On Feb 9, 2:36 pm, Mayur Mahrotri <mayurmahro...@gmail.com> wrote:
> How do you check then, whether the grammar is LR(0) and SLR(1). ? I
> constructed all the LR(0) items, then ?
>

[Mayur Mahrotri]

Yeah, i know this method, but was doubtful about it. Thats why i asked.

On this grounds, can you solve this question and confirm :

Q. The grammar S -> while (E) s | a
                        E -> a
is for nested while statements. This grammar is :
(A) is not LR(1) (B) is not SLR(1) (C) is not LALR(1) (D) is not LR(0)

This was asked in the Gateforum test paper 69. The answer given here is (D) and the explanation is "Without lookahead, we don't know the replacement for x"

When, solving i did not get any inadequate state. Please solve this and let me know.

Thanks for you input, Varun. :)

--
With Regards,
Mayur.

[Mayur Mahrotri]

Sorry for the typo, correct the line :

"Without lookahead, we don't know the replacement for S"

--
With Regards,
Mayur.

[Varun Shinde]

hey this is quite interesting question.....u know "Without lookahead,

we don't know the replacement for S"

what this means i didnt get it.....but i will tell u one thing. i
solved it completely....and it is LR(0)..hence it is SLR(1)...
even as per my approach...doing first..CLR(1)..it is CLR(1)
also.....so u know i have done this as per elimination...
it like from top hierarchy.. if it is CLR(1) then it is LR(0) also and
SLR(1) also..but as LR(0)..is the lowest in hierarchy..so it is not
LR(0)..
frankly speaking i have done it like that....

On Feb 9, 7:56 pm, Mayur Mahrotri <mayurmahro...@gmail.com> wrote:
> Sorry for the typo, correct the line :
>
> "Without lookahead, we don't know the replacement for S"
>

> On Tue, Feb 9, 2010 at 8:24 PM, Mayur Mahrotri <mayurmahro...@gmail.com>wrote:
>
>
>
>
>
> > Yeah, i know this method, but was doubtful about it. Thats why i asked.
>
> > On this grounds, can you solve this question and confirm :
>
> > Q. The grammar S -> while (E) s | a
> >                         E -> a
> > is for nested while statements. This grammar is :
> > (A) is not LR(1) (B) is not SLR(1) (C) is not LALR(1) (D) is not LR(0)
>
> > This was asked in the Gateforum test paper 69. The answer given here is (D)
> > and the explanation is "Without lookahead, we don't know the replacement for
> > x"
>
> > When, solving i did not get any inadequate state. Please solve this and let
> > me know.
>
> > Thanks for you input, Varun. :)
>

[Mayur Mahrotri]

I found one more question in Gateforum Test Series 68.

Q. Consider the grammar

S-> AaAb | BbBa
A-> ε
B-> ε

What is true about the grammar ?
(A) is LL(1) and SLR(1)
(B) is LL(1) but not SLR(1)
(C) is SLR(1) but not LL(1)
(D) is not LL(1) and not SLR(1)

The answer is surprisingly (B) and the explanation give is :

Follow(A) = {a,b}, Follow(B) = {a,b}, Follow(A) intersection Follow(B) = {a,b} ≠ ф, so not SLR(1).

How can we be sure of these questions ? This is completely opposite of what we were taught.

--
With Regards,
Mayur.

[Sagar Joshi]

The grammar is LL(1). Here we have reduce-reduce conflict in LR(0) items. for grammar to be in SLR follow(a) intersection follow(b) = phi

As it is not phi (it is {a,b}) it is not SLR(1).

So what is the problem? I did not understand.

--
-----------------------------------------------------------

I dont need drugs, I get high with Music!

-----------------------------------------------------------

[Mayur Mahrotri]

The problem is that what we know is, LL(1) grammar is the subset of LR grammar. That is, if a grammar is LL(1), it should be SLR,LR,CLR,LALR.. everything. LL(1) comes the lowest in the grammar hierarchy.

But this is not true in this case. And hence the doubt.

--
With Regards,
Mayur.

[Mayur Mahrotri]

And also, if this grammar is not SLR(1), then this means that SLR parser cannot even pass a language which contains only two possible strings {ab,ba}. !!

--
With Regards,
Mayur.

[Sagar Joshi]

first of all ll1 is not a subset of SLR(1)!!! There are some grammars which are slr(1) but not LL(1)

 

I have attached a venn diag of diff grammars given venkat sir.

For SLR(1) grammar with only possible strings will be

S - ab | ba

[Mayur Mahrotri]

Hi Sagar,

What i meant was, the given grammar which is

S->AaAb | BbBa
A->epsilon
B->epsilon, generates only two strings {ab,ba}. How can such a grammar be not parsed by SLR parser?

Also, I am attaching a document, in which it is clearly given that LL(1) is a subset of SLR(1). [Refer page 7].

I am clear about the doubts now. What happens is, the language is clearly SLR(1), because it generates only two strings and is a finite language. But the grammar which represents any language can be written in thousands of ways.

Thus, the representation of the grammar may not be SLR(1), but the language can be.

Thus, the language, represented by LL(1) can all be represented by SLR(1).

Refer this link. It'll almost clear all doubts.

http://stackoverflow.com/questions/475949/how-to-determine-whether-a-grammar-is-ll1-lr0-slr1

--
With Regards,
Mayur.