Inessential Error Entries and Their Use in LR Parser Optimization

Abstract

The use of "default reductions" in implementing LR parsers is considered in conjunction with the desire to decrease the number of states of the parser by making use of "don't-care" (also called "inessential" ) error entries.Default reductions are those which are performed independently of the lookahead string when other operations do not apply, and their use can lead to substantial savings in space and time.Don't-care error entries of an LR parser are those which are never consulted, and thus they can be arbitrarily replaced by nonerror entries in order to make a state compatible with another one.Determining don't-care error entries is most important in avoiding the growth of the size of the parser when eliminating reductions by single productions, that is, productions for which the right-hand side is a single symbol.The use of default reductions diminishes don't-care error entries.This effect is analyzed by giving a necessary and sufficient condition for an error entry to be don't-care when default reductions are used.As an application, elimination of reductions by single productions in conjunction with the use of default reductions is considered.