On LLP(k) parsers

摘要

A general framework for constructing very small deterministic parsers using a mixed top-down-bottom-up parsing strategy is presented. It is proved that the method leads indeed to valid parsers halting for each input string. Conditions ensuring the determinism of the parser are studied, and bounds on its size are established. It is shown that the new method is capable of producing parsers with far fewer states than currently used parsing techniques can achieve.