Lazy and incremental program generation

ABSTRACT

Current program generators usually operate in a greedy manner in the sense that a program must be generated in its entirety before it can be used. If generation time is scarce, or if the input to the generator is subject to modification, it may be better to be more cautious and to generate only those parts of the program that are indispensable for processing the particular data at hand. We call this lazy program generation. Another, closely related strategy is incremental program generation. When its input is modified, an incremental generator will try to make a corresponding modification in its output rather than generate a completely new program. It may be advantageous to use a combination of both strategies in program generators that have to operate in a highly dynamic and/or interactive environment.

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: ~BROWN, P.j. 1976. Throw-away compiling. Softw. Pract. Exp. 6, 3, 423-434.
• 3: J. Craig Cleaveland, Building Application Generators, IEEE Software, v.5 n.4, p.25-33, July 1988 [doi>10.1109/52.17799]
• 4: ~FRITZ$ON, P. 1982. Fine-grained incremental compilation for Pascal-like languages. Rep. ~LiTH-MAT-R-82-15, Software Systems Research Center, Link5ping Univ.
• 5: ~FRITZSON, P. 1983. Symbolic debugging through incremental compilation in an integrated ~environment. J. Syst. Softw. 3, 4, 285-294.
• 6: J. Heering , P. R. H. Hendriks , P. Klint , J. Rekers, The syntax definition formalism SDF—reference manual—, ACM SIGPLAN Notices, v.24 n.11, p.43-75, Nov. 1989 [doi>10.1145/71605.71607]
• 7: Jan Heering , Paul Klint , Jan Rekers, Incremental Generation of Parsers, IEEE Transactions on Software Engineering, v.16 n.12, p.1344-1351, December 1990 [doi>10.1109/32.62443]
• 8: J. Heering , P. Klint , J. Rekers, Incremental generation of lexical scanners, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.4, p.490-520, Oct. 1992 [doi>10.1145/133233.133240]
• 9: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 10: ~HOPPER, G. M. 1981. Keynote address to the ACM History of Programming Languages ~Conference. In History of Programming Languages. Academic Press, New York, 7-20.
• 11: R. N. Horspool, Incremental generation of LR parsers, Computer Languages, v.15 n.4, p.205-223, 1990 [doi>10.1016/0096-0551(90)90021-G]
• 12: R. Nigel Horspool, ILALR: An Incremental Generator of LALR(1) Parsers, Proceedings of the 2nd CCHSC Workshop on Compiler Compilers and High Speed Compilation, p.128-136, October 10-14, 1988
• 13: JOHNSON, S.C. 1975. Yacc--Yet another compiler-compiler. Computing Science Tech. Rep. No. ~32, Bell Laboratories, Murray Hill, N.J.
• 14: KLINT, P. 1991. Lazy scanner generation for modular regular grammars. Rep. CS-R9158, ~Dept. of Software Technology, CWI, Amsterdam.
• 15: K. Koskimies, Lazy recursive descent parsing for modular language implementation, Software—Practice & Experience, v.20 n.9, p.749-772, August 1990
• 16: PAXSON, V. 1989. FLEX. Lexical scanner generator developed at Lawrence Berkeley Labora- ~tory, Berkeley, Calif.
• 17: REKERS, J. 1992. Parser generation for interactive environments. Ph.D. thesis, Programming ~Research Group, Univ. of Amsterdam.
• 18: P. Sestoft , A. V. Zamulin, Annotated bibliography on partial evaluation and mixed computation, New Generation Computing, v.6 n.2-3, p.309-354, March-April 1988
• 19: D. Szafron , R. Ng, LexAGen: an interactive incremental scanner generator, Software—Practice & Experience, v.20 n.5, p.459-483, May 1990 [doi>10.1002/spe.4380200503]
• 20: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 21: WALTERS, H.R. 1991. On equal terms: Implementing algebraic specifications. Ph.D. thesis, ~Programming Research Group, Univ. of Amsterdam, Chapter 3.
• 22: Daniel M. Yellin , Robert E. Strom, INC: a language for incremental computations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.211-236, April 1991 [doi>10.1145/103135.103137]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Parsing; Translator writing systems and compiler generators

General Terms:
Algorithms, Performance

Keywords:
greedy, incremental program generation, lazy, lazy and incremental compilation, lazy and incremental generation of lexical scanners, lazy and incremental generation of parsers, program generator