# LR(1) - Items, Look Ahead

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}


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.

-

## migrated from cstheory.stackexchange.comNov 19 '12 at 19:22

This question came from our site for theoretical computer scientists and researchers in related fields.

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