5.0 Introduction

5.1 Metalanguage

5.2 LR-Family Parsing

5.3 Error Handling

5.4 Compaction of Tables

5.5 Yacc

5.6 Summary

Web References

Exercises

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.

Send questions and comments to: Karen Lemone