The following grammar is LL1, SLR, LR(1), LALR?

Posted by Mike on Stack Overflow See other posts from Stack Overflow or by Mike
Published on 2010-04-21T09:50:45Z Indexed on 2010/04/21 9:53 UTC
Read the original article Hit count: 302

Filed under:
|

P -> {D ; C}

D -> d; D| d

C -> c; C | c

a) Is the grammar LL(1)? Explain your answer.

b) Is the grammar SLR(1)? Explain your answer.

c) Is the grammar LR(1)? Explain your answer.

d) Is the grammar LALR? Explain your answer.

As for my answers I actually got no for them all... so I'm thinking I did something wrong

Here is my explanation.

a) It is not LL(1) because it is not left factored.

b) It is not SLR, because of the transition diagram

item 2 ( which is... ) D-> d . ; D

D-> d .

We need to consult the follow set, Follow(D) = ;

Therefore this is not SLR

c) It is not LR(1) because of...

item 1

P-> {D.;C} , $

D-> .d;D , ;

D-> .d , ;

item 2

D-> d.; D , ;

D-> d. , ;

item 3

D-> d; . D , ;

D-> .d;D , ;

D-> .d , ;

Since item 2 goes to item 3 with ;, AND "D-> d."'s (in item 2) look ahead token is also ;. this causes a reduce to shift conflict, therefore this grammar is not LR(1)

d) This grammar is not LALR because it is not LR(1)

Thanks for your help!

© Stack Overflow or respective owner

Related posts about grammar

Related posts about parsers