World's most popular travel blog for travel bloggers.

Why is particular token missing in LALR lookahead set?

, , No Comments
Problem Detail: 

I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:

S' ::= S S ::= L = R | R L ::= * R | id R ::= L 

The items associated with state 0 given in the Automaton View are as follows:

S ::= ⋅S, EOF S ::= ⋅L = R, EOF S ::= ⋅R, EOF L ::= ⋅* R, {=, EOF} L ::= ⋅id, {=, EOF} R ::= ⋅L, EOF 

Shouldn't the last item's lookahead set be {=, EOF}? This item could be derived from S ::= ⋅R (in which case the lookahead set is {EOF}) or from L ::= ⋅* R (in which case the lookahead set is {=, EOF}).

Asked By : npCompleteNoob
Answered By : rici

In state 0, R ::= ⋅L can only be generated by S ::= ⋅R. In L ::= ⋅* R, the dot precedes *, not R, so no further items are generated by it.

The dragon book uses this grammar as an example of the inadequacy of SLR, and the correct computation of the lookahead in this case is an instance; the SLR algorithm bases lookahead decisions on the FOLLOW set rather than actual lookahead possibilities in the state, which will eventually lead to a shift/reduce conflict on lookahead symbol =.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback