1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 =.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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