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?

Wray

If you are going to make a career in the computer business, you need to learn to read when you don't know something. Read Wikipedia on LR languages carefully, and work this out. If it takes some time to stare at it and understand, so be it; this is typical. en.wikipedia.org/wiki/LR_parser – Hamrick

In a gruff sort of way, yes :-} – Hamrick

The grammar you have is LL(1) with no empty string productions, so it is SLR(1) – Brammer

Answer 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.

Nodal

$ isn't in fo(A) for that grammar, but the S/R conflict is still there without it. – Annatto

Answer 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!

Coreen

Just note that every grammar SLR (1) is LR (1) grammar but not all LR (1) is SLR (1) – Idonah

If you are looking for an example you can use this grammar: 1) S –> XX 2) X –> aX 3) X –> b – Idonah

@templatetypedef, What if it would have been bda. [ $ ] in state 8. Would there be a reduce reduce conflict ? Because we have only one follow symbol which is common. – Swaziland

@Swaziland Yep, you'd have a reduce/reduce conflict on the $ symbol. Remember that a group of lookaheads functions as "reduce on any of these symbols," so any conflict between two lookahead sets is a problem. – Coreen

@Coreen Sir, it would be great if you could answer this question cs.stackexchange.com/questions/80601/slr-vs-clr-parser – Swaziland

Answer 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).

Annatto

Answer 4

1)The given grammar is LL(1) in top down parsing, and LALR(1) in bottom up parsing.

2)while you are creating the parsing table, and the parsing table has No multiple entries, then the grammar tends to attend LALR(1).

3)If your parsing table has multiple entries(i mean the conflict occurrence), then the grammar is said to be SLR(1).

4)A grammar is said to be LR(1) since it's parsing table or ACTION/GOTO table has no conflict, and we all know that during a conflict occurrence in LR(1) we merge the data and we get the LALR.

LR(0) OR SLR OR SLR(1) are same

LR(1) OR CLR are same

LALR OR LALR(1) are same

the (1) parameter defines the inner build efficiency type of the syntax analyzer.

thank you.

Comply