# Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true.

Given a grammar $$G$$,

1. If the LALR parser has reduce-reduce conflict for $$G$$, then the SLR parser also has reduce-reduce conflict for $$G$$.
2. If the SLR parser has reduce-reduce conflict for $$G$$, then the LALR parser also has reduce-reduce conflict.
3. The LALR parser has reduce-reduce conflict for $$G$$ if and only if SLR also has reduce-reduce conflict for $$G$$.

Since SLR $$\subset$$ LALR, I think point 1 is true. Is this wrong?

Further more, based on a few examples that I have come across it seems like points 2 & 3 are also true. Is this correct. If so, could you please point me to the proof. If not could you please give me a counter example?

Note: I'm assuming that when you wrote $$SLR$$ and $$LALR$$ that you actually meant $$SLR(1)$$ and $$LALR(1)$$.

It is certainly the case that if a grammar shows a conflict in an $$LALR(1)$$ automaton, that conflict will also be present in the $$SLR(1)$$ automaton, because the two automata have the same states and the $$LALR(1)$$ lookaheads for any production are a subset of the $$SLR(1)$$ lookaheads.

The remaining two proposals are false, as can be demonstrated by the same counter-example.

The classic example of an $$LALR(1)$$ grammar which is not $$SLR(1)$$ (taken directly from the Dragon book) is the abstraction of a grammar which attempts to discriminate between "lvalue" and "rvalue" syntaxes. (Roughly speaking, an "lvalue" is something which can be assigned to, so-named because it can appear on the left-hand side of an assignment operator; an "rvalue" is a value which cannot be assigned to, which means that it can only appear on the right-hand side.

It's usually convenient to include the production $$R\to L$$, which says that "lvalues" can also appear on the right-hand side of the assignment operator. But it is precisely this fact which leads to the conflict:

\begin{align}S &\to L = R\\ S &\to R\\ L &\to * R\\ L &\to id\\ R &\to L\\ \end{align} As the Dragon book points out, that grammar leads to an $$SLR(1)$$ conflict in the state reached from $$\text{GOTO}(I_0, L)$$. That state ($$I_2$$ in the Dragon book exposition) contains the items $$S\to L\;\cdot = R$$ and $$R\to L\;\cdot$$. Since $$=$$ is in $$\text{FOLLOW}(R)$$, the state has a shift-reduce conflict. In the $$LALR(1)$$ automaton, that conflict is resolved.

Since that's a shift-reduce conflict, it doesn't address your question, which concerns reduce-reduce conflicts. But it's easy to modify the grammar slightly in order to turn the shift-reduce conflict into a reduce-reduce conflict. All that's necessary is to introduce a new intermediate non-terminal:

\begin{align}S &\to L' = R\\ S &\to R\\ L' &\to L\\ L &\to * R\\ L &\to id\\ R &\to L\\ \end{align}

That changes the itemset for state $$I_2$$ to include the items $$\{L'\to L\;\cdot, R\to L\;\cdot\}$$, which is now an $$SLR(1)$$ reduce-reduce conflict, for the same reason that the previous example had a shift-reduce conflict. Also for the same reason, the $$LALR(1)$$ algorithm resolves that conflict using more precisely-computed lookahead sets.

That disproves your statement 2; since the "if and only if" in statement 3 requires both statement 1 and statement 2 to be true, it also disproves statement 3.