The ergo attribute system

ABSTRACT

The Ergo Attribute System was designed to satisfy the requirements for attributes in a language-generic program derivation environment. It consists of three components: (1) an abstract data type of attributes that guarantees attribute consistency, (2) a Common Lisp implementation which combines demand-driven and incremental attribute evaluation in a novel way while allowing for attribute persistence over many generations of a program, and (3) an attribute-grammar compiler producing code based on this abstract data type from a high-level specification. Our experience with three major applications (one being the attribute-grammar compiler itself) confirms that the overhead in storing and accessing attributes incurred by our implementation scheme is more than offset by the gains from the demand-driven, incremental, and persistent nature of attribution.

REFERENCES

• 1: 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]
• 2: Scott R. Dietren, Mary Ann Pike, Anne M. Rogers, and William L. Scherlis. User's Guide to the Ergo Syntaz Facility. Ergo Report In preparation, Carnegie Mellon University, Pittsburgh, 1988.
• 3: Rodney Farrow, Experience with an attribute grammar-based compiler, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.95-107, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582164]
• 4: 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
• 5: Mehdi Jazayeri , Kenneth G. Walter, Alternating semantic evaluator, Proceedings of the 1975 annual conference, p.230-234, January 1975 [doi>10.1145/800181.810328]
• 6: Martin Jourdan, Strongly non-circular attribute grammars and their recursive evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.81-93, June 17-22, 1984, Montreal, Canada
• 7: Uwe Kastens. Ordered attribute grammars. Acta Informatica, 13:229-256, 1980.
• 8: Uwe Kastens, Brigitte Hutt, and Erich Zimmermann. GAG: A Practical Compiler Generator. Volume 141 of Lecture Notes in Computer Science, Springer-Verlag, 1982.
• 9: 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]
• 10: Kai Koskimies, A specification language for one-pass semantic analysis, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.179-189, June 17-22, 1984, Montreal, Canada
• 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: Peter Lee, Frank Pfenning, John Reynolds, Gene Rollins, and Dana Scott. Research on Semantically Based Program-Design Environments: The Ergo Project in 1988. Technical Report CMU- CS-88-118, Carnegie Mellon University, Pittsburgh, March 1988.
• 13: Peter Lee , Frank Pfenning , Gene Rollins , William Scherlis, The ergo support system: an integrated set of tools for prototyping integrated environments, Proceedings of the third ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.25-34, November 28-30, 1988, Boston, Massachusetts, United States
• 14: Robert L. Nord. A Framework for Program Flow Analysis. Ergo Report 87-038, Carnegie Mellon University, Pittsburgh, November 1987.
• 15: F. Pfenning , C. Elliot, Higher-order abstract syntax, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.199-208, June 20-24, 1988, Atlanta, Georgia, United States
• 16: William Pugh, An improved replacement strategy for function caching, Proceedings of the 1988 ACM conference on LISP and functional programming, p.269-276, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62719]
• 17: Kari-Jourko Raiha. Bibliography on attribute grammars. SIGPLAN Notices, 15(3):35-44, 1980.
• 18: Thomas Reps , Tim Teitelbaum, The synthesizer generator, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.42-48, April 1984
• 19: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 20: William L. Scherlis, Abstract datatypes, specialization, and program reuse, An international workshop on Advanced programming environments, p.433-453, January 1986, Trondheim, Norway
• 21: Reinhard Wilhelm. Global Flow Analysis and Optimization in the MUG2 Compiler Generating System, pages 132-159. Prentice Hall, 1981.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

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

          Nouns: LISP
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

General Terms:
Languages