Compiler structure engineering with attribute grammars

ABSTRACT

In this paper are discussed the concepts of a compiler structure design system and its prototype implementation.In order to obtain the pass structure based on the properties of the deterministic left to right evaluable attribute grammars we use short path algorithms for directed graphs. An algorithm for assignment of attributes to separate passes is shown. We propose a method for extension of the deterministic left to right evaluable attribute grammars with global data. Futher we describe the approach of a syntax oriented modularization for specifying the compiler structure.Using this research as a base we developed the CSD system (Compiler Structure Design). The CSD system is a compiler engineering tool providing facilities for specification of compilers and for design of their pass, intermediate program and module structure. The main components of the system are also shown and its use for development of a COBOL compiler are discussed.

REFERENCES

• 1: /ALB 81/ Alblas H.: A Characterization of Attribute Evaluation in Passes. Acta Informatica, p. 427-464, 16(1981)4.
• 2: /BKS 79/ Biryukov A.N., Kurotchkin V.M., Serebrjakov V.A.: Globalnije atributij i ich izpolsovanie pri opisanii yazikov programmirovania. Obrabotka simvolnoi informazii, vip. 5, Moskwa, VZ AN SSSR, 1979.
• 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: Cynthia A. Brown , Paul W. Purdom, Jr., A methodology and notation for compiler front end design, Software—Practice & Experience, v.14 n.4, p.335-346, April 1984 [doi>10.1002/spe.4380140405]
• 5: /MIL 88/ Miloucheva I.: Rechnergestuetzter Entwurf der Compilerstruktur mit Attributgrammatiken. Dissertation, Sektion Informatik, Technische Universitaet Dresden, 1988.
• 6: /DJL 86/ Deransart P., Jourdan M., Lorho B.: A Survey on Attribute Grammars. Part I - Review of Existing Systems. INRIA Rapports de Recherche, 1985, no. 417. Part II - Main Results on Attribute Grammars. INRIA Rapports de Recherche, 1986, no. 485. Part III - Classified Bibliography. INRIA Rapports de Recherche, 1986.
• 7: J Engelfriet, Attribute grammars: attribute evaluation methods, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
• 8: /KN 68/ Knuth D.E.: Semantics of Context Free Languages. Mathematical Systems Theory, p. 127-145, 2(1968)2.
• 9: /KOS 84/ Koskimies K.: A Specification Language for One-pass Translation using Attribute Grammars. Software Practice and Experience, p. 119-129, 13(1983)2.
• 10: 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]
• 11: Kai Koskimies , Kari-Jouko Räihä , Matti Sarjakoski, Compiler construction using attribute grammars, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.153-159, June 23-25, 1982, Boston, Massachusetts, United States
• 12: /LJO 87/ Loeper H., Jaeckel H.-J., Otter W.: Compiler and Interpreter fuer hoehere Programmiersprachen. Akademic-Verlag Berlin, 1987.
• 13: /RIE 85/ Riedewald G: Compiler-Compiler auf der Grundlage attributierter Grammatiken. Problemseminar "Compiler-Generatoren", 1984, Binz, AdW, IIR, 1(1985)7.
• 14: /RU 80/ Raeiha K.-J., Ukkonen E.: Minimizing the Number of Evaluation Passes for Attribute Grammars. SIAM Jour. on Computing, p. 772-786, 10(1981)4.
• 15: David A. Watt, Rule splitting and attribute-directed parsing, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.363-392, January 14-18, 1980

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: Syntax
      D.3.2 Language Classifications

          Nouns: COBOL

General Terms:
Design, Languages