Remote attribute updating for language-based editors

ABSTRACT

A major drawback to the use of attribute grammars in language-based editors has been that attributes can only depend on neighboring attributes in a program's syntax tree. This paper concerns new attribute-grammar-based methods that, for a suitable class of grammars, overcome this fundamental limitation. The techniques presented allow the updating algorithm to skip over arbitrarily large sections of the tree that more straightforward updating methods visit node by node. These techniques are then extended to deal with aggregate values, so that the attribute updating procedure need only follow dependencies due to a changed component of an aggregate value. Although our methods work only for a restricted class of attribute grammars, satisfying the necessary restrictions should not place an undue burden on the writer of the grammar.

REFERENCES

• 1: 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]
• 2: 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
• 3: 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]
• 4: {Kastens 1980} Kastens, U. Ordered attribute grammars. <i>Acta Inf. 13,</i> 3 (1980), 229--256.
• 5: {Kastens et al. 1982} Kastens, U., Hutt, B., and Zimmermann, E. <i>Lecture Notes in Computer Science,</i> vol. 141: <i>GAG: a Practical Compiler Generator.</i> Springer-Verlag, New York, 1982.
• 6: Gregory F. Johnson , Charles N. Fischer, Non-syntactic attribute flow in language based editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.185-195, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582174]
• 7: 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]
• 8: {Knuth 1968} Knuth, D. E. Semantics of context-free languages. <i>Math. Sys. Theory 2,</i> 2 (June 1968), 127--145. Correction. <i>ibid. 5,</i> 1 (Mar. 1971), 95--96.
• 9: {Medina-Mora &amp; Notkin 1981} Medina-Mora, R. and Notkin, D. S. ALOE users' and implementors' guide. Tech. Rep. CMU-CS-81-145, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., Nov. 1981.
• 10: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• 11: {Reps 1983} Reps, T. Static-semantic analysis in language-based editors. In Digest of Papers of the IEEE Spring CompCon 83, San Francisco, Calif., Mar. 1--3, 1983, pp. 411--414.
• 12: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 13: 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]
• 14: Thomas Reps , Bowen Alpern, Interactive proof checking, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.36-45, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800514]
• 15: 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
• 16: {Reps &amp; Teitelbaum 1985} Reps, T. and Teitelbaum, T. The Synthesizer Generator reference manual. Tech. Rep. 84--619, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., Aug. 1985.
• 17: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 18: {Yeh 1983} Yeh, D. On incremental evaluation of ordered attributed grammars. <i>BIT 23,</i> (1983), 308--320.