Partial evaluation of general parsers

ABSTRACT

Applications of partial evaluation have so far mainly focused on generation of compilers from interpreters for programming languages. We partially evaluate a simple general LR(k) parsing algorithm. To obtain good results, we rewrite the algorithm using a number of binding-time improvements. The final LR(1) parser has been specialized using Similix, a partial evaluator for a higher order subset of Scheme [3]. The obtained specialized parsers are efficient and compact. Partial evaluation is responsible for the (equivalent of) the sets-of-items construction, and the construction of parsing tables. This paper is an extended abstract of [14].

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: D. Bjcrner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. IFIP TC2, North-Holland, 1988. Workshop proceedings, October 1987, G1. Avernms, Denmark.
• 3: Anders Bondorf, Automatic autoprojection of higher order recursive equations, Science of Computer Programming, v.17 n.1-3, p.3-34, Dec. 1991
• 4: A. Bondorf. Similix Manual, system version 4.0. DIKU, University of Copenhagen, Denmark, Sept. 1991.
• 5: Anders Bondorf , Olivier Danvy, Automatic autoprojection of recursive equations with global variable and abstract data types, Science of Computer Programming, v.16 n.2, p.151-195, Sept. 1991 [doi>10.1016/0167-6423(91)90002-F]
• 6: C. Consel , O. Danvy, From interpreting to compiling binding times, Proceedings of the third European symposium on programming on ESOP '90, p.88-105, May 1990, Copenhagen, Denmark
• 7: H. Dybkjeer. Parsers and partial evaluation: an experiment. Student Report 85-7-15, DIKU, University of Copenhagen, Denmark, July 1985.
• 8: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 9: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 10: J. JCrgensen. Generating a pattern matching compiler by partial evaluation. In P. C. van Rijsbergen, editor, Glasgow Workshop on Functional Programming, Ullapool, pages 177-195, Glasgow University, July 1990. Springer-Verlag.
• 11: Jesper Jørgensen, Generating a compiler for a lazy language by partial evaluation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.258-268, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143220]
• 12: D. E. Knuth. On the translation of languages from left to right. Information and Control, 8:607 - 639, 1965.
• 13: C. Mossin. Similix binding time debugger manual, system version 4.0. Included in Similix distribution, Sept. 1991.
• 14: C. Mossin. Partial evaluation of general parsers. Student Report 92-8-1, DIKU, University of Copenhagen, Denmark, Aug. 1992.
• 15: C. Queinnec and J.-M. Geffroy. Partial evaluation applied to pattern matching with intelligent backtrack. In Workshop on Static Analysis, pages 109 - 117, 1992.
• 16: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages