Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

migrated from cstheory.stackexchange.com Nov 19 '12 at 19:22

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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
isnt't the X the B here and a belongs to FIRST(betal)? –  Fyre Nov 4 '13 at 18:51
    
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. –  Angelo Borsotti Jan 28 at 11:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.