Menu
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?
936
LR(1) grammars Every SLR(1) grammar is a canonical LR(1) grammar, but the canonical LR(1) parser may have more states than the SLR(1) parser. An LR(1) grammar is not necessarily SLR(1), the grammar given earlier is an example.
To show the given grammar to be not SLR, we only need to examine the following two LR(0) states. S2: S → L . = R • R → L .
If you can construct a parsing table and there are no conflicts, it's SLR(1).
Therefore, given grammar is LR (1). For LALR (1), we combine state 2 and state 3. Here, RR conflict arises. Therefore, given grammar is not LALR (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.
116
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
