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

Question

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?

Solution 1

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.

Solution 2

One way to figure this out would be to try to construct LR(1) and SLR(1) parsers for the grammar. If we find any shift/reduce or reduce/reduce conflicts in the course of doing so, we can show that the grammar must not belong to one of those classes of languages.

Let's start off with the SLR(1) parser. First, we need to compute the LR(0) configurating sets for the grammar. These are seen here:

(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda

(2)
S -> a.A
A -> .d

(3)
S -> aA.

(4)
A -> d.

(5)
S -> b.Ac
S -> b.da
A -> .d

(6)
S -> bA.c

(7)
S -> bAc.

(8)
S -> bd.a
A -> d.

(9)
S -> bda.

(10)
S -> d.c

(11)
S -> dc.

Next, we need to get the FOLLOW sets for all the nonterminals. This is shown here:

FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }

Given this, we can go back and upgrade the LR(0) configurating sets into SLR(1) configurating sets:

(1)
S -> .aA    [ $ ]
S -> .bAc   [ $ ]
S -> .dc    [ $ ]
S -> .bda   [ $ ]

(2)
S -> a.A    [ $ ]
A -> .d     [ $, c ]

(3)
S -> aA.    [ $ ]

(4)
A -> d.     [ $, c ]

(5)
S -> b.Ac   [ $ ]
S -> b.da   [ $ ]
A -> .d     [ $, c ]

(6)
S -> bA.c   [ $ ]

(7)
S -> bAc.   [ $ ]

(8)
S -> bd.a   [ $ ]
A -> d.     [ $, c ]

(9)
S -> bda.   [ $ ]

(10)
S -> d.c    [ $ ]

(11)
S -> dc.    [ $ ]

Interestingly enough, there are no conflicts here! The only possible shift/reduce conflict is in state (8), but there is no conflict here because the shift action is on a and the reduce is on $. Consequently, this grammar actually is SLR(1). Since any SLR(1) grammar is also LR(1), this means that the grammar is both SLR(1) and LR(1).

Hope this helps!

Solution 3

I thought about writing a web-app to determine first- and follow-sets for CFGs and also LR(0), SLR(1) and LR(1) tables. This would have allowed you to try it out easily.

But luckily I googled first and found that such a tool already exists (I didn't necessarily expect this to be the case). You can find the tool here:

http://smlweb.cpsc.ucalgary.ca/

It expects the input in the following format:

S -> a A | b A c | d c | b d a.
A -> d.

Using this tool, I have verified what others have already stated: the grammar in question is SLR(1). (I give -1 to the question for this).

After the modification suggested by Toby Hutton, it isn't SLR(1) anymore, but still LR(1).