Is this grammar LALR(1)?

Question

I have the following grammar:

S -> aSb
S -> c

It can be used for LR(1) parsers are there is no conflict. However, when I combine states with same LR(0) items and different lookaheads, I get a parsing table for LALR(1) that does not contain any known conflict (shift-shift, shift-reduce, reduce-reduce), but I get a conflict in the GOTO part of the ACTION-GOTO table. That is, in one cell for a non-terminal, I get 2 possible states. Have never seen any examples for the same, so wanted to confirm.

Tried searching the dragon book, online references; no examples encountered.

Answer 1

You have certainly made a mistake in the state merging process.

Here is the canonical LR(1) automaton for your example grammar, with equivalent states (LR(0) cores) marked with colours:

I'm not going to spell out the step-by-step merging process, but hopefully you can do it in an order such as 7=9, 4=8, 2=5 and 3=6 to get the resultant LALR(1) automaton (with colour provenance retained):

It is very easy to make mistakes when going through this fairly tedious process of state merging. It's often easier - on paper - to do the state merging during construction, rather than after-the-fact.

---

For educational purposes, I must note that this isn't a very convenient way of attaining LALR(1). I'm not going to go into all of the details, but you can easily (in this case) upgrade the LR(0) automaton to become LALR(1) by using the ideas from DeRemer and Pennello's famous paper Efficient Computation of LALR(1) Look-Ahead Sets.

In particular, when a grammar has no nullable symbols, the entire relations based approach requires no intermediary computations (where much of this algorithm's complexity lies) - consequently, reduce items' lookaheads are precisely the terminals which can be directly read via their corresponding "lookback" transitions.

You can identify lookback links by mentally looking at the paths that spell out a reduce item's production body:

Those green lines indicate the "lookback" relation for each reduce item (you can search backwards from each state, via the symbols that spell out the production body, to find these transitions). The terminals that immediately follow the related non-terminal transitions are in the lookahead set of the corresponding reduce item.

This approach is often far more efficient on paper if you know nothing is nullable.