What to do following a reduce in LR(1) parsing?

Question

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what will the current state be? It seems like it could be both State 0 or State 3 (since state 3 loops back on itself on the lookahead c), i.e the GOTO of C from either state 0 or state 3. I am confused on states like 3 that loop into themselves.

The grammar is this:
$$S' \rightarrow S $$ $$S \rightarrow CC $$ $$S \rightarrow cC $$ $$C \rightarrow d $$

Question 1 : When the machine is at state 3. On encountering d as a lookahead, what is the action, and the new state?

Question 2 : At a more fundamental level, what do you do following a reduce in any kind of LR parsing. You can't stay in that state itself, and have to go somewhere else right? How do you make that choice?

Edit: I made a small mistake in the grammar productions. I had originally included the grammar C -> c which was a mistake, and was removed.

Answer 1

It may help to think in terms of lookahead sets, rather than lookahead symbols. So the item set in state 4 is actually:

$$\left[ C \rightarrow d \cdot, \left\{ c, d \right\} \right]$$

According to the definition of a $LR(1)$ automaton, what you should do is look at the lookahead symbol. If it's $c$ or $d$, then reduce by $C \rightarrow d$, otherwise it's a parse error.

This is correct behaviour, and you would get full marks for this answer. However, it's not how $LR$ parser generators work in practice!

A grammar which is $LR(1)$ but not $LR(0)$ has a $LR(0)$ automaton which is correct. The problem is that it's nondeterministic. And, indeed, there are variants (e.g. $GLR$) which allow for nondeterministic automata.

What that means is that in practical applications, you don't need to consult the lookahead set if you don't need to in order to make a parsing decision.

In your case, state 4 does not need lookahead to disambiguate it. If you didn't bother looking at the lookahead set, and just reduced anyway, the parse error would be caught as soon as you tried to shift the next symbol, because there isn't a transition for it. Try parsing the string d$ to see what I mean.

Real-world grammars tend to produce $LR$ automata with a lot of these states where the only possible action is to reduce by a single production. So real-world parser generators tend to optimise them by not storing their lookahead sets. We call these $LR(0)$ reduce states.

In true $LR(k)$ parsing, you will often find $LR(0)$ reduce states which differ only in their lookahead sets:

$$\begin{eqnarray*} q_1: & \,\, & \left[ A \rightarrow \alpha \cdot, \phi \right]\\ q_2: & & \left[ A \rightarrow \alpha \cdot, \psi \right] \end{eqnarray*}$$

(Exercise: Why can this never happen in a $LALR(k)$ automaton?)

You can merge these states and the resulting automaton will still be correct, and will still be deterministic if the original automaton was deterministic.