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

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