Comparative efficiency of general and residual parsers

ABSTRACT

Some fundamentals of the partial computation concept are concisely reviewed, including its relevance to the relationship between table-driven, general syntactic analyzers and source-language-specific, residual syntactic analyzers. A manual methodology for converting general parsers into generators of residual parsers is explained, using an LL(1) parser as a detailed example. The results of several experiments are reported, comparing the time and space efficiencies of different general parsers with corresponding, automatically generated, residual parsers. The latter parsers are usually several times faster than the former ones.

REFERENCES

• 1: Peter Sestoft , Harald S:Gfndergaard, A bibliography on partial evaluation, ACM SIGPLAN Notices, v.23 n.2, p.19-26, Feb., 1988 [doi>10.1145/43908.43910]
• 2: D. Bjorner , Neil D. Jones , A. P. Ershov, Partial Evaluation and Mixed Computation: Proceedings of the IFIP TC2 Workshop, Gammel Avernaes, Denmark, 18-24 Oct., 1987, Elsevier Science Inc., New York, NY, 1988
• 3: Frank G. Pagan, Converting interpreters into compilers, Software—Practice & Experience, v.18 n.6, p.509-527, June, 1988 [doi>10.1002/spe.4380180603]
• 4: Frank G. Pagan, Partial computation and the construction of language processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 5: William A. Barrett , Rodney M. Bates , David A. Gustafson , John D. Couch, Compiler construction: theory and practice (2nd ed.), SRA School Group, 1986
• 6: Thomas J. Pennello, Very fast LR parsing, ACM SIGPLAN Notices, v.21 n.7, p.145-151, July 1986