Characteristic parsing: A framework for producing compact deterministic parsers, II

摘要

This paper applies the theory of characteristic parsing to obtain very small parsers in three special cases. The first application is for strict deterministic grammars. A characteristic parser is constructed and its properties are exhibited. It is as fast as an LR parser. It accepts every string in the language and rejects every string not in the language although it rejects later than a canonical LR parser. The parser is shown to be exponentially smaller than an LR parser (or SLR or LALR parser) on a sample family of grammars. General size bounds are obtained. A similar analysis is carried through for SLR and LALR grammars.