0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.