|
5.2.5 LR-Family: LR(1) Table GenerationAn 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
LALR(1) parsers parse fewer languages than do LR(1) parsers. Send questions and comments to: Karen Lemone |