Roger Hoover
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.
- A78.Allen, J. R. Anatomy of LISP. McGraw-Hill, New York, NY, 1978. Google Scholar
Digital Library
- BC85.Beshers, G., and R. Campbell. Maintained and Constructor Attributes. Proc. ACM SIGPLAN 85 Symposium on Language Issues in Programming Environments, Seattle, WA, June, 1985, pp. 34-42. Google ScholarDigital Library
- DRT81.Demers, A., T. Reps, and T. Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. Proc. of the 8th ACM Symposium on Principles of Programming Languages, Jan, 1981, pp. 105-116. Google ScholarDigital Library
- DRZ85.Demers, A., A. Rogers, and F. K. Zadeck. Attribute propagation by message passing. Proc. ACM SIGPLAN 85 Symposium on Language Issues in Programming Environments, Seattle, WA, June, 1985, pp. 43-59. Google ScholarDigital Library
- H85.Horwitz, S. Generating Language- Based Editors: A Relationally- Attributed Approach. TR 85-696 (Ph.D. Thesis), Cornell University, August 1985. Google ScholarDigital Library
- H86.Hoover, R. Dynamically bypassing copy rule chains in attribute grammars. Proc. of the 13th ACM Symposium on Principles of Programming Languages, St. Petersburg, FL, Jan 13-15, 1986, pp. 14-25. Google ScholarDigital Library
- J84.Johnson, G. F. An approach to incremental semantics. TR 547 (Ph.D. Thesis), University of Wisconsin, Madison, July 1984. Google ScholarDigital Library
- JF85.Johnson, G. F., and C. N. Fischer. A meta-language and system for nonlocal incremental attribute evaluation in language-based editors. Proc. of the 12th ACM Symposium on Principles of Programming Languages, New Orleans, LA, Jan 14-16, 1985, pp. 141- 15l. Google ScholarDigital Library
- K68.Knuth, D. E. Semantics of context-free languages. Mathematical Systems Theory, 2, 2, June 1968, pp. 127-145.Google ScholarCross Ref
- KM.Krijnen, T. and L. Meertens. Making B-trees work for B. Technical Report, Mathematical Center, Amsterdam.Google Scholar
- L79.Liu, L. Essential uses of expressions in set-oriented expressions. Ph,D. Thesis, Cornell University, May 1979. Google ScholarDigital Library
- M83.Myers, E. W. Efficient Applicative Data Types. Proc. of the l Oth ACM Symposium on Principles of Programming Languages, Jan, 1983, pp. 66-75. Google ScholarDigital Library
- PK82.Paige, R. and S. Koenig~ Finite differencing of computable expressions. ACM Trans. on Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp. 402-454. Google ScholarDigital Library
- R84.Reps, T. Generating Language-based Environments. M.I.T. Press, Cambridge, MA, 1984. Google ScholarDigital Library
- RMT86.Reps, T., C. Marceau, T. Teitelbaum~ Remote attribute updating for language-based editors. Proc. of the 13th ACM Symposium on Principles of Programming Languages, St. Petersburg, FL, Jan 13-15, 1986, pp. 1- 13. Google ScholarDigital Library
- RT84.Reps, T. and T. Teitelbaum. The Synthesizer Generator. Proc. of the ACM SIGSOFT/S{GPLAN Software Engineering Symposium on Practical Software Development Environments, Pittsburgh, PA, April 1984. Google ScholarDigital Library
- Y83.Yeh, D. On Incremental Evaluation of Ordered Attributed Grammars. BIT 23, 1983, pp. 308-320.Google ScholarCross Ref
Index Terms
- Efficient incremental evaluation of aggregate values in attribute grammars
Recommendations
Efficient incremental evaluation of aggregate values in attribute grammars
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 ...
Incremental attribute evaluation through recursive procedures
Incremental semantic analysis in a programming environment based on Attribute Grammars is performed by an Incremental Attribute Evaluator (IAE). Current IAEs are either table-driven or make extensive use of graph structures to schedule reevaluation of ...
Comments