2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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 succeed the dot is what may succeed 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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.