Efficient incremental evaluation of aggregate values in attribute grammars

ABSTRACT

Aggregate valued attributes, which store collections of keyed elements, are required in attribute grammars to communicate information from multiple definition sites to multiple use locations. For syntax directed editors and incremental compilers, symbol tables are represented as aggregate values. We present efficient algorithms for incrementally maintaining these aggregate values and give an incremental evaluation algorithm that restricts attribute propagation to attributes dependent only upon information within the aggregate value that has changed.

REFERENCES

• A78: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• BC85: George McArthur Beshers , Roy Harold Campbell, Maintained and constructor attributes, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.34-42, June 25-28, 1985, Seattle, Washington, United States
• DRT81: 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]
• DRZ85: Alan Demers , Anne Rogers , Frank Kenneth Zadeck, Attribute propagation by message passing, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.43-59, June 25-28, 1985, Seattle, Washington, United States
• H85: Susan Beth Horwitz, Generating language-based editors: a relationally-attributed approach, 1985
• H86: Roger Hoover, Dynamically bypassing copy rule chains in attribute grammars, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.14-25, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512646]
• J84: Gregory Francis Johnson, An approach to incremental semantics, 1983
• JF85: Gregory F. Johnson , C. N. Fischer, A meta-language and system for nonlocal incremental attribute evaluation in language-based editors, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-151, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318627]
• K68: Knuth, D. E. Semantics of context-free languages. Mathematical Systems Theory, 2, 2, June 1968, pp. 127-145.
• KM: Krijnen, T. and L. Meertens. Making B-trees work for B. Technical Report, Mathematical Center, Amsterdam.
• L79: Lishing Liu, Essential uses of expressions in set-oriented languages, 1979
• M83: Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
• PK82: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• R84: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• RMT86: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• RT84: 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
• Y83: Yeh, D. On Incremental Evaluation of Ordered Attributed Grammars. BIT 23, 1983, pp. 308-320.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Performance, Theory