How is this grammar LR(1) but not SLR(1)?

Konstantinos Georgiadis picture Konstantinos Georgiadis · May 8, 2012 · Viewed 14.7k times · Source

I have the following grammar, which I'm told is LR(1) but not SLR(1):

S ::= a A | b A c | d c | b d a

A ::= d

I don't understand why this is. How would you prove this?

Answer

Toby Hutton picture Toby Hutton · Apr 23, 2013

I don't have enough reputation to comment on the above answer, and I'm a bit late to this question, but...

I've seen this grammar as an example elsewhere and the OP actually made a typo. It should be:

S ::= A a | b A c | d c | b d a

A ::= d

i.e., the very first clause of S is 'A a', not 'a A'.

In this case the FOLLOWS set for A is { $, a, c} and there is an SLR conflict in state 8.