LR-regular grammars—an extension of LR(k) grammars

摘要

LR-regular grammars are defined similarly to Knuth's LR(k) grammars, with the following exception: arbitrarily long look-ahead is allowed before making a parsing decision during the bottom-up syntactical analysis; however, this look-ahead is restricted in that the essential “look-ahead information” can be represented by a finite number of regular sets, thus can be computed by a finite state machine. LR-regular grammars can be parsed deterministically in linear time by a rather simple two-scan algorithm. Efficient parsers are constructed for given LR-regular grammars. The family of LR-regular languages is studied; it properly includes the family of deterministic CF languages and has similar properties. Necessary and sufficient conditions for a grammar to be LR-regular are derived and then utilized for developing parser generation techniques for arbitrary grammars.