LR(1) – Items, 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)$).