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

摘要

A new version of LR(k) parsing is introduced here. The basic idea is to define the LR(k) parser in a table-driven fashion. These tables are derived from sets of items. By modifying the algorithm for generating sets of items by adding additional items, the choice of which depends on characteristics of the underlying grammar, it is shown that one still gets an “LR-like” parser. Here, the parameterized algorithm is given and the way in which the table-driven parser works is analyzed. Notions of consistency need to be examined and it must be shown that one does indeed get a working parser. In a sequel to this paper, the technique introduced here is used to construct very small parsers which could not have been obtained by any other currently known technique. The improvements in size are very striking and can even be exponential.