I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ?

Say for an example that I have the following grammar:

S -> AB A -> aAb | b B -> d

Then the first state will look like this:

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b, {look ahead}

I now what look aheads are, but I don't know how to compute them. I have googled for answers but there isn't any webpage that explains this in a simple manner.

Thanks in advance


There are two ways that lookaheads 'come into being'. The first is that the start production $S' \rightarrow S$ has lookahead $\$$ in the initial state of the $LR(1)$ automaton. Hence, $S' \rightarrow \bullet S, \$$ is an item in the initial state.

Pendantry note: we therefore accept in the state containing the item $S' \rightarrow S \bullet, \$$ on lookahead $\$$ and we pad any input with $\$$.

The rest of the lookaheads are computed from lookaheads which we have already computed. If we have in some state an item $A \rightarrow \alpha \bullet X \beta, l$ (so $l$ is the lookahead and $X$ is a nonterminal) and another production $B \rightarrow \gamma$, then for every $a \in \mathsf{FIRST}(X \beta l)$ we add in the completion step for that state the item $B \rightarrow \bullet \gamma, a$.

In other words, the lookahead is some terminal that can appear as the first terminal in a string derived from $X \beta l$. As $l$ is a terminal and appears at the end of $X \beta l$, this means that $X \beta l$ does not derive the empty string (so we don't need $\mathsf{FOLLOW}$). Also note that we only ever derive items and therefore new lookaheads from items that already have lookaheads, so there is no problem there.

The precise definition of $\mathsf{FIRST}$ is: $\mathsf{FIRST}(a \alpha) = \{a\}$ if $a$ is a terminal, $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A)$ if $A$ is a nonterminal and $A$ does not derive the empty string, and $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A) \bigcup \mathsf{FIRST}(\alpha)$ if it does. $\mathsf{FIRST}(A)$ is the well-known relation denoting the first terminals in the strings derivable from $A$ (which is also used in $LL(1)$).

| cite | improve this answer | |
  • $\begingroup$ isnt't the X the B here and a belongs to FIRST(betal)? $\endgroup$ – Fyre Nov 4 '13 at 18:51
  • $\begingroup$ The previous answer is not correct: For every item A -> alpha . B beta, l in a state, items B -> . gamma, a are added for each a in FIRST(beta l). I.e, the lookaheads are the terminals that can follow the occurrences of B in the items of a state. $\endgroup$ – Angelo Borsotti Jan 28 '14 at 11:28

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.