Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

Question

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that unlike $LR(1)$ items, which just have an item lookahead (the token that should appear after the completed $LR(1)$ item), the items in an $LR(2)$ parser also need a dot lookahead (the tokens that should appear after the dot in the $LR(2)$ item).

I'm having trouble understanding what this means, how this lookahead is computed, and why this isn't needed in $LR(0)$ or $LR(1)$ items. Can anyone explain what this means?

Answer 1

I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used.

First, let's remark that there are three kinds of items:

1. those in which the dot is just before a non-terminal. They never participate in an ambiguous situation: when a non-terminal has been produced, it is shifted.

2. those in which the dot is at the end. They have the item look-ahead and the dot look-ahead which are equal (what may follow the dot is what may follow the produced non-terminal when the production is reduced as the dot is at the end of the item).

3. those in which the dot is just before a terminal. They have the item look-ahead and the dot look-ahead which are different. The item look-ahead is what may follow the non-terminal when the production is reduced, the dot look-ahead start by the terminal which follow the dot and continue with what can be generated after that terminal.

Now, with a look-ahead of 1 or less, the dot look-ahead is trivial: either it is the item look-ahead or the terminal which is just after the dot and that's what you are using to solve a conflict (or decide that there is no way with the limited look-ahead you have). With a look-ahead of 2 or more, you have to compute the dot look-head or you may not know if you have to shift or to reduce as in the example provided by Grune and Jacobs:

$$\begin{array}{l} S \rightarrow Aa \; | \; Bb \;| \;Cec \;|\; Ded \\ A \rightarrow qE \\ B \rightarrow qE \\ C \rightarrow q \\ D \rightarrow q \\ E \rightarrow e \\ \end{array}$$

which has the state: $$\begin{array}{lcc} &\textrm{item look-ahead}&\textrm{dot look-ahead}\\ A \rightarrow q \cdot E & a\# & ea\\ B \rightarrow q \cdot E & b \# & eb\\ C \rightarrow q \cdot & ec & ec\\ D \rightarrow q \cdot & ed & ed\\ E \rightarrow \cdot e & a \# & ea\\ E \rightarrow \cdot e & b \# & eb\\ \end{array}$$