0
$\begingroup$

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 $$

enter image description hereenter image description hereenter image description here

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.

$\endgroup$
1
  • 1
    $\begingroup$ Please edit your question to make it self-contained, so we don't have to visit an external link to understand what you're asking, and so the question remains understandable even if the link stops working. $\endgroup$
    – D.W.
    Oct 25, 2020 at 16:59

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Hi, I decluttered my question a little bit. Could you take a look at it now? I think there is some typo in your sentence 'try parsing the string d'. $\endgroup$ Oct 26, 2020 at 0:51
  • $\begingroup$ Hi, I don't know what non-determinism means in the context of LR(1) grammars. But I think I can easily invent a LR(1) grammar that is not LR(0) that is quite deterministic. $\endgroup$ Oct 26, 2020 at 1:48
  • $\begingroup$ Thanks for that. The dollar sign and LaTeX markup don't mix very well... The key point about nondeterminism is that, for the purpose of this answer, nondeterminism is a property of the automaton, not the grammar. You can invent a grammar where the $LR(1)$ automaton is deterministic but the $LR(0)$ automaton is nondeterministic. $\endgroup$
    – Pseudonym
    Oct 26, 2020 at 2:14
  • $\begingroup$ Hi, on parsing $d\$$, I would think that it first shift to State 4, where on doing a lookahead a finding $ missing with only (c,d) available, it would throw an error. $\endgroup$ Oct 26, 2020 at 2:18
  • $\begingroup$ Yes, it would. But if you ignored the lookahead set in state 4, you would shift to state 4, reduce and pop back to state 0, goto state 2, and then you would detect the parse error since there is no transition for $. You still (correctly) get a parse error, it's just detected later. $\endgroup$
    – Pseudonym
    Oct 26, 2020 at 2:21

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.