LR(1) - Items, Look Ahead

Problem Detail: 

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

Asked By : mrjasmin

Answered By : Alex ten Brink

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6771