HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
itemversuswithlookaheadsdotfor

Problem

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?

Solution

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:

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

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

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

Context

StackExchange Computer Science Q#48866, answer score: 4

Revisions (0)

No revisions yet.