Composable attribute grammars: support for modularity in translator design and implementation

ABSTRACT

This paper introduces Composable Attribute Grammars (CAGs), a formalism that extends classical attribute grammars to allow for the modular composition of translation specifications and of translators. CAGs bring to complex translator writing systems the same benefits of modularity found in modern programming languages, including comprehensibility, reusability, and incremental meta-compilation. A CAG is built from several smaller component AGs, each of which solves a particular subproblem, such as name analysis or register allocation. A component AG is based upon a simplified phrase-structure that reflects the properties of its subproblem rather than the phrase-structure of the source language. Different component phrase-structures for various subproblems are combined by mapping them into a phrase-structure for the source language. Both input and output attributes can be associated with the terminal symbols of a component AG. Output attributes enable the results of solving a subproblem to be distributed back to anywhere that originally contributed part of the subproblem, e.g. transparently distributing the results of global name analysis back to every symbolic reference in the source program. After introducing CAGs by way of an example, we provide a formal definition of CAGs and their semantics. We describe a subclass of CAGs and their semantics. We describe a subclass of CAGs, called separable CAGs, that have favorable implementation properties. We discuss the novel aspects of CAGs, compare them to other proposals for inserting modularity into attribute grammars, and relate our experience using CAGs in the Linguist translator-writing system.

REFERENCES

• 1: H. Alblas. Incremental simple multi-pass attribute evaluation. In Proceedings of the NGI/SION 1986 Symposium, pages 319-342, 1986.
• 2: H.-J. Boehm and W. Zwanenpoel. Parallel attribute grammar evaluation. Technical Report TR-87-55, Rice University, Houston, TX, June 1987.
• 3: B. Courcelle, Attribute grammars : definitions, analysis of dependencies, proof methods, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
• 4: The Linguist translator-writing system User's Manual, Version 6.3, Declarative Systems, Inc. Palo Alto, CA, February 1991.
• 5: Pierre Deransart , Martin Jourdan , Bernard Lorho, Attribute grammars: definitions, systems and bibliography, Springer-Verlag New York, Inc., New York, NY, 1988
• 6: G. D. P. Dueck , G. V. Cormack, Modular attribute grammars, The Computer Journal, v.33 n.2, p.164-172, April 1990 [doi>10.1093/comjnl/33.2.164]
• 7: C. Farnum. Prototyping optimizing compilers. PhD thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA, December 1990.
• 8: Rodney Farrow, LINGUIST-86: Yet another translator writing system based on attribute grammars, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.160-171, June 23-25, 1982, Boston, Massachusetts, United States
• 9: Rodney Farrow, Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.85-98, June 25-27, 1986, Palo Alto, California, United States
• 10: R. Farrow , A. G. Stanculescu, A VHDL compiler based on attribute grammar methodology, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.120-130, June 19-23, 1989, Portland, Oregon, United States
• 11: N. M. Garter. Parallel incremental compilation. Technical Report 349, University of Rochester, June 1990.
• 12: Harald Ganzinger , Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, A truly generative semantics-directed compiler generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.172-184, June 23-25, 1982, Boston, Massachusetts, United States
• 13: R. Giegerich, Composition and evaluation of attribute coupled grammars, Acta Informatica, v.25 n.4, p.355-423, May 1988 [doi>10.1007/BF02737108]
• 14: Larry G. Jones, Efficient evaluation of circular attribute grammars, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.429-462, July 1990 [doi>10.1145/78969.78971]
• 15: Richard K. Jullig , Frank DeRemer, Regular right-part attribute grammars, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.171-178, June 17-22, 1984, Montreal, Canada
• 16: U. Kastens. Ordered attribute grammars. Acta Informatica, 13(3):229-256, 1980.
• 17: U. Kastens, B. Hutt, and E. Zimmerman. GAG: A practical compiler generator. Number 141 in Lecture Notes in Computer Science. Springer-Verlag, 1982.
• 18: 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]
• 19: E. A. Klein. Attribute evaluation in parallel, in Proceedings of the Workshop of Parallel Compilation, page 8, Kingston, Ontario, May 6-8 1990.
• 20: D. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127-145, February 1968. Correction, 5 (1), 95-96, March 1971.
• 21: Ole Lehrmann Madsen, On defining semantics by means of extended attribute grammars, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.259-299, January 14-18, 1980
• 22: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 23: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator reference manual (3rd ed.), Springer-Verlag New York, Inc., New York, NY, 1989
• 24: M. Tieman. Removing redundancy in attribute grammars. Technical Report ACA-239-87, MCC, July 1987.
• 25: H. H. Vogt , S. D. Swierstra , M. F. Kuiper, Higher order attribute grammars, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.131-145, June 19-23, 1989, Portland, Oregon, United States
• 26: D. A. Watt and O. L. Madsen. Extended attribute grammars. Computer Journal, 26(2):142-153, May 1983.
• 27: IEEE Standard VHDL Reference Manual. IEEE Std 1076-1087. The Institute of Electrical and Electronic Engineers, Inc. New York, NY, March 31, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

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

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

General Terms:
Design, Languages