Extending lookahead for LR parsers

摘要

A practical method is presented for extending the lookahead of LR parsers, by the addition of “reduce-arcs.” Applied to an LR(0) parser, this gives a machine which is close in size to the corresponding LALR(1) machine, but is capable of making use of unbounded lookahead. The class of grammars parsable by this method is a subset of the LR-regular grammars which is shown to be properly included in the LALR(k) grammars, if limited to k symbols of lookahead, but also includes non-LR grammars if no such limit is imposed. Application is foreseen to error recovery in LALR(1) parsers, as well as the handling of occasional non-LALR(1) situations in normal parsing.