6
$\begingroup$

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.

$\endgroup$

1 Answer 1

8
$\begingroup$

If a grammar is SLR(1), then: [Note 1]

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

Notes

  1. I take the view that if conflicting transitions are generated, then the construction algorithm fails and no parser is produced. That's the way the algorithms are described in Aho, Sethi & Ullman, for example (the so-called "Dragon Book"). If you take the equally valid view that a parser is always produced, but is not necessarily deterministic, then the following statements would be true for all grammars.
$\endgroup$
4
  • $\begingroup$ One thing I feel is missing from your answer is that an LALR(1) table (regardless of whether it has conflicts) always has the same size as an SLR(1) table - the number of states is always the same, the lookahead info has just been improved at no cost of extra states. $\endgroup$
    – orlp
    Jan 24, 2019 at 4:02
  • $\begingroup$ @orlp: the answer does say that the two machines have the same states. In my mind, if the grammar is not SLR(1), there is no SLR(1) machine because the construction algorithm will fail. You seem to be saying that I shouldn't make the results contingent on the existence of an SLR(1) machine, because the algorithm could produce something like a non-deterministic machine. In any case, the OP is explicitly restricted to SLR(1) grammars, so there is no compelling reason to resolve this difference. $\endgroup$
    – rici
    Jan 24, 2019 at 4:34
  • $\begingroup$ It says that the machines have the same states if the grammar is SLR(1). That made me assume when I first read this answer that for a grammar that is LALR(1) but not SLR(1) there would be additional states. Perhaps a way to phrase this equivalence is that the LALR(1) state diagram (where items in item sets have been enhanced with lookahead) always has the same number of states as the LR(0) state diagram. Those diagrams always exist, although they can be non-deterministic if turned into parsing machines. I'm interested in them for Earley parsing, which can handle the nondeterminism. $\endgroup$
    – orlp
    Jan 24, 2019 at 4:42
  • $\begingroup$ @orlp: I added a note. I hope it makes you happy. :-) But I don't think it has any relevance to the question as originally asked almost four years ago. $\endgroup$
    – rici
    Jan 24, 2019 at 5:42

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.