5.2.5 LR-Family: LR(1) Table Generation

An LR(1) item is and LR(0) item plus a set of lookahead characters.

E E · + T, { $,+ }

indicates that we have seen an E, and are expecting a "+T", which may then be followed by the end of string (indicated by $) or by a "+" (as in a+a+a).

The algorithm is the same as for creating LR(0) items except the closure step which now needs to be modified to include the lookahead character:

Closure:

IF A x · X y, L is in the state, where L is the set of lookaheads, THEN add X · z, FIRST (y/) for each / in L to the state for every X z.

We build the first two states here and leave the remaining (21) to the reader:

State 0: E' * E, { $ } indicates that the string is followed by $.

Applying the closure rule to this gives us initially E · E + T, { $ } as the next item here since FIRST ( $)= {$}. Now, the closure operation must be applied to this and FIRST (+ T $ )= {+}, so the next item is E · E + T, { +, $}. The entire states 0 and 1 are:

        State 0                              State 1 

        E' · E, {$}                            E' E · , {$}
        E  · E + T, { +, $}                    E  E · + T, {+, $ }
        E  · T, { +, $}
        T  · T * F, {$ +, * }
        T  · F, { $, +, *}
        F  · Id, { $,  +, * }
        F  · (E), { $, +, * }

LALR(1) parsers parse fewer languages than do LR(1) parsers.