World's most popular travel blog for travel bloggers.

# [Solved]: Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

, ,
Problem Detail:

Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators.

Is it the case that the construction of the SLR(1) parser and the LALR(1) always yield the same table?

If not, what happens if the grammar G is SLR(1)?

I'm particularly interested in this question about the following grammar:

\begin{align*} C &\to E \, \text{rel} \, E \mid C \& C \mid ! \, C \mid \text{pred}\, ( \,Es\, ) \\ E &\to \text{num} \mid \text{id} \mid E\, +\, E \mid E\, *\, E \mid - \,E \mid ( \,E \,) \\ Es &\to E \mid E\, ,\, Es \end{align*}

Using a custom SLR and LALR table generator I obtain exactly the same table for the above grammar, with some shift/reduce conflicts that can be resolved by giving precedences in the order &, !, rel, +, *, - and left associativity to &, + and *. I'm in doubt whether my implementation is incorrect or the tables are really the same, and if this is the case whether there is some general rule that applies in certain circumstances.

If a grammar is SLR(1), then:

• The SLR(1) and LALR(1) state machines will have the same states

• The set of shift transitions in the two machines will be identical (as will the goto actions).

• The set of accept transitions in the two machines will be identical.

• The set of reduction actions in the LALR(1) machine will be a subset of the set of reduction actions in the SLR(1) machine.

In other words, it is possible for there to be a reduce action in the SLR(1) machine which is an error (or unspecified) action in the LALR(1) machine. In the case of an input which triggers such a reduce in the SLR(1) machine, that input will still eventually trigger an error before another shift transition is taken.

The difference comes from the fact that the SLR(1) algorithm generates a reduction action for a state with a reducible item for any lookahead in the follow set of the LHS of that item. The LALR(1) algorithm only includes the lookaheads which are feasible in the context of the state.

For example, here's a simple grammar: \begin{align*} S &\to A \, [ \, A\, ] \\ A &\to \epsilon \, \mid \, ( \, A \, ) \end{align*}

The follow set of $A$ is $\{ ) , [ , ] \}$.

Now consider any state in which $A$ follows the dot. For example:

\begin{align*} A &\to ( \, \centerdot A \, ) \\ A &\to \centerdot \\ A &\to \centerdot \, ( \, A \, ) \end{align*}

This state has a shift action on $($ and a reduction action for $A \to$. It's clear that the reduction action should only be performed if the lookahead is $)$; any other lookahead is an error. But since $[$ and $]$ are in the follow set for $A$, the SLR(1) algorithm includes reduction actions for those lookaheads as well. The error will be detected after the subsequent goto action in the state $A \to ( \, A \, \centerdot \, )$. In the LALR(1) table, these two lookaheads will lead directly to an error.

However, there are other entries in the LALR(1) table for this grammar in which the LALR(1) parser will also execute reductions with a lookahead which obviously cannot be shifted. Only in an LR(1) parser are errors detected immediately. (That's not a good reason to use a canonical LR(1) parser).