Incremental generation of lexical scanners

ABSTRACT

It is common practice to specify textual patterns by means of a set of regular expressions and to transform this set into a finite automaton to be used for the scanning of input strings. In many applications, the cost of this preprocessing phase can be amortized over many uses of the constructed automaton. In this paper new techniques for lazy and incremental scanner generation are presented. The lazy technique postpones the construction of parts of the automaton until they are really needed during the scanning of input. The incremental technique allows modifications to the original set of regular expressions to be made and reuses major parts of the previous automaton. This is interesting in applications such as environments for the interactive development of language definitions in which modifications to the definition of lexical syntax and the uses of the generated scanners alternate frequently.

REFERENCES

• 1: AHO, A. V. Pattern matching in strings. In Formal Language Theory, R. V. Book, Ed., Academic Press, New York, 1980, 325 347.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: BERRY, G., AND SETHI, R. From regular expressions to deterministic automata. Rep. 649, INRIA, Rocquencourt, 1987.
• 4: CHAILLOUX, J., DEVIN, M., DUPONT, F., HULLOT, J. M., SERPETTE, B., AND VUILLEMIN, J. Le_Llsp Version 15.2--Le Manuel de r~f~rence. INRIA, Rocquencourt, 1986.
• 5: VAN DIJK, M. H. H., AND KOORN, J. W.C. Generic syntax-directed editor. In The CENTAUR User~ Guide--Version 0.9, 1989.
• 6: GROSCH, J. Efficient generation of table-driven scanners. Compiler Generation Rep. No. 2, GMD Forschungsstelle an der Universit~t Karlsruhe, May 1987.
• 7: V P Heuring, The automatic generation of Fast Lexical Analysers, Software—Practice & Experience, v.16 n.9, p.801-808, Sept. 1986
• 8: 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]
• 9: HEERIN~, J., AND KLINT, P. A syntax definition formalism. In ESPRIT'86: Results and Achievements, North-Holland, 1987, 619-630. See also Chapter 6 of Algebraic Specification, J. A. Bergstra, J. Heering, and P. Klint, Eds., Frontier Series, ACM Press~ Addison-Wesley, 1989.
• 10: HEERING, J., KAHN, G., KLINT, P., AND LANG, B. Generation of interactive programming environments. In ESPRIT'85, Status Report of Continuing Work, Part I, North-Holland, 1986, 467 477.
• 11: J. Heering , P. Klint , J. Rekers, Lazy and incremental program generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.1010-1023, May 1994 [doi>10.1145/177492.177750]
• 12: J. Heering , P. Klint , J. Rekers, Incremental generation of parsers, ACM SIGPLAN Notices, v.24 n.7, p.179-191, July 1989
• 13: 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]
• 14: P. Klint, A mete-environment for generating programming environments, Algebraic methods II: theory, tools and applications, Springer-Verlag New York, Inc., New York, NY, 1991
• 15: KLINT, P. Lazy scanner generation for modular regular grammars. Rep. g158, Centre for Mathematics and Computer Science, 1991.
• 16: LESK, M.E. LEX--a lexical scanner generator. Rep. CSTR 39, Bell Laboratories, Murray Hill, N.J., 1975.
• 17: McNAuo~TON, R., AND YAMADA, PI. Regular expressions and state graphs for automata. IRE Trans. Electron. Comput. EC-9 (1960), 38-47.
• 18: PAXSON, V. Flex. Lexical scanner generator developed at Lawrence Berkeley Laboratory, USA, 1989.
• 19: REKERS, J. Modular parser generation. Rep. CS~R8933, Centre for Mathematics and Computer Science, 1989.
• 20: W. M. Waite, The cost of lexical analysis, Software—Practice & Experience, v.16 n.5, p.473-488, May 1986 [doi>10.1002/spe.4380160508]
• 21: WALrERS, H. R. On equal terres: Implementing algebraic specifications. Ph.D. Thesis, Programming Research Group, Univ. of Amsterdam, 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

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

General Terms:
Algorithms, Languages, Performance

Keywords:
finite automaton, lazy and incremental generation of lexical scanners, program generator, subset construction