5.2 LR-Family Parsing

The shift-reduce method to be described here is called LR-parsing. There are a number of variants (hence the use of the term LR-family), but they all use the same driver. They differ only in the generated table. The L in LR indicates that the string is parsed from left to right; the R indicates that the reverse of a right derivation is produced.

Given a grammar, we want to develop a deterministic bottom-up method for parsing legal strings described by the grammar. As in top-down parsing, we do this with a table and a driver which operates on the table.

Parser Driver

SLR(1) Table Generation

Shift-Reduce and Reduce-Reduce Conflicts

LR-family members

LR(1) Table Generation

LALR(1) Table Generation