A truly generative semantics-directed compiler generator

ABSTRACT

This paper describes semantic processing in the compiler generating system MUG2. MUG2 accepts high-level descriptions of the semantics of a programming language including full runtime semantics, data flow analysis, and optimizing transformations. This distinguishes MUG2 from systems such as YACC [Joh75], HLP [HLP78], PQCC [PQC79], or its own former version [GRW77] with respect to expressive power and convenience. In this respect, MUG2 comes close to semantics-directed systems such as [Mos76], [JoS80], [Set81], [Pau82]. In contrast to these, MUG2 is not a universal translator system where program independent semantic properties have to be evaluated at compilation time. The description concepts of MUG2 allow a far reaching separation of language vs. program dependent semantics, thus constituting a truly generative approach to semantics-directed compiler generation.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: Babich, W.A., Jazayeri, M.: The method of attributes for data flow analyis, part I: Exhaustive analysis. Acta informatica 10 (1978) 245-264.
• 3: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 4: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 5: Rina Cohen , Eli Harry, Automatic generation of near-optimal linear-time translators for non-circular attribute grammars, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.121-134, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567764]
• 6: Chirica, L.M., Martin, D.F.: An algebraic formulation of Knuthian semantics. 17th IEEE Symp. on FOCS, 1977, 127-136.
• 7: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 8: Joost Engelfriet , Gilberto Filé, Passes, Sweeps and Visits, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.193-207, July 13-17, 1981
• 9: Harald Ganzinger, Transforming denotational semantics into practical attribute grammars, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.1-69, January 14-18, 1980
• 10: Giegerich, R.: Introduction to the compiler generation system MUG2. Report TUM-INFO-7913, Techn. Univ. München, 1979.
• 11: Robert Giegerich, Automatic generation of machine specific code optimizers, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.75-81, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582162]
• 12: Ingrid Glasner , Ulrich Möncke , Reinhard Wilhelm, OPTRAN, a Language for the Specification of Program Transformations, Programmiersprachen und Programmentwicklung, 6. Fachtagung des Fachausschusses Programmiersprachen der GI, p.125-142, March 11-12, 1980
• 13: Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, Invariance of Approximate Semantics with Respect to Program Transformations, GI - 11. Jahrestagung in Verbindung mit Third Conference of the European Co-operation in Informatics (ECI), p.1-10, October 20-23, 1981
• 14: Ganzinger, H., Ripken, K., Wilhelm, R.: Automatic generation of optimizing multipass compilers. In: Gilchrist, B. (ed.): Information Processing 77, North-Holland Publ. Co., Amsterdam, New York, Oxford, 1977, 535-540.
• 15: Hecht, M.S., Ullman, J.D.: A simple algorithm for global data flow analysis programs. SIAM J. Comp. 4 (1975), 519-532.
• 16: Räihä, K.-J., Saarinen, M., Soisalon-Soininen, E. Tienari,M.: The compiler writing system HLP (Helsinki Language Processor). Dep't. of Comp. Science, Helsinki Univ., Report A-1978-2, 1978.
• 17: Mehdi Jazayeri , Kenneth G. Walter, Alternating semantic evaluator, Proceedings of the 1975 annual conference, p.230-234, January 1975 [doi>10.1145/800181.810328]
• 18: Mehdi Jazayeri , Diane Pozefsky, Space-Efficient Storage Management in an Attribute Grammar Evaluator, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.388-404, Oct. 1981 [doi>10.1145/357146.357148]
• 19: Jochum G.: Automatische Konstruktion und einheitliche Darstellung von Attributaus-wertungsalgorithmen. TUM-18113, Techn. Univ. München, June 1981.
• 20: Johnson, S.C.: YACC: yet another compiler compiler. Techn. Rep. CSTR32, Bell Labs, Murray Hill, 1975.
• 21: Neil D. Jones , David A. Schmidt, Compiler generation from denotational semantics, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.70-93, January 14-18, 1980
• 22: Jochum, G., Willmertinger, W.: A tool for developing text processing systems: translator writing systems. Report TUM-18103, Techn. Univ. München, 1981.
• 23: Kam, J.B., Ullman, J.D.: Monotone data flow analysis frameworks. Acta Informatica 7 (1977), 305-317.
• 24: Ken Kennedy , Scott K. Warren, Automatic generation of efficient evaluators for attribute grammars, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.32-49, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811538]
• 25: Hans Hermann Kron, Tree templates and subtree transformational grammars., 1975
• 26: Knuth, D.E.: Semantics of context-free languages. Math. Systems Theory 2, (1968), 127-145.
• 27: Leverett, B.W., Cattell, R.G.G., Hobbs, S.O., Newcomer, J.M., Reiner, A.H., Schatz, B.R., Wulf, W.A.: An overview of the production quality compiler-compiler project. Dept. of Comp. Science, Carnegie-Mellon University, CMU-CS-79-105, 1979.
• 28: P. M. Lewis , D. J. Rosenkrantz , R. E. Stearns, Attributed translations(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.160-171, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804047]
• 29: Möncke, U.: Doctorial dissertation, Univ. Saarbrücken, forthcoming.
• 30: Mosses, P.: Compiler generation using denotational semantics. Proc. Symp. on Math. Found. of Comp. Sci., Lecture Notes in Comp. Sci., 45 (1976), 436-441.
• 31: Mosses, P.: SIS - Semantics implementation system. Reference Manual and user guide. Report DAIMI MD-30, Univ. Aarhus, 1979.
• 32: Lawrence Paulson, A semantics-directed compiler generator, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.224-233, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582178]
• 33: Pozefsky, D.P.: Building efficient pass-oriented attribute grammar evaluators. Univ. North Carolina at Chapel Hill, UNC TR 79-006, 1979.
• 34: Kari-Jouko Räihä, Dynamic allocation of space for attribute instances in multi-pass evaluators of attribute grammars, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.26-38, August 06-10, 1979, Denver, Colorado, United States
• 35: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• 36: Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
• 37: Ravi Sethi, Circular Expressions: Elimination of Static Environments, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.378-392, July 13-17, 1981
• 38: Robert E Tarjan, Iterative algorithms for global flow analysis, Stanford University, Stanford, CA, 1976
• 39: Wilhelm, R.: Computation and use of data flow information in optimizing compilers. Acta Informatica 12 (1979), 209-225.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Languages