Optimal-time incremental semantic analysis for syntax-directed editors

ABSTRACT

Attribute grammars permit the specification of static semantics in an applicative and modular fashion, and thus are a good basis for syntax-directed editors. Such editors represent programs as attributed trees, which are modified by operations such as subtree pruning and grafting. After each modification, a subset of attributes, AFFECTED, requires new values. Membership in AFFECTED is not known a priori; this paper presents an algorithm that identifies attributes in AFFECTED and computes their new values. The algorithm is time-optimal, its cost is proportional to the size of AFFECTED.

REFERENCES

• 1: Rina Cohen , Eli Harry, Automatic generation of near-optimal linear-time translators for non-circular attribute grammars, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.121-134, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567764]
• 2: 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]
• 3: {DHK} Donzeau-Gouge, V., Huet, G., Kahn, G., Lang B., and Levy, J.J. A structure-oriented program editor. Technical Report, IRIA-LABORIA, France 1975.
• 4: Wilfred James Hansen, Creation of hierarchic text with a computer display, 1971
• 5: Ken Kennedy , Jayashree Ramanathan, A Deterministic Attribute Grammar Evaluator Based on Dynamic Scheduling, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.142-160, July 1979 [doi>10.1145/357062.357072]
• 6: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 7: {Knu 68b} Knuth, D.E. Semantics of context-free languages. Mathematical Systems Theory 2, 2 (1968), 127--145.
• 8: {Knu 71} Knuth, D.E. Semantics of context-free languages: correction. Mathematical Systems Theory 5, 1 (1971), 95--96.
• 9: {LRS} Lewis, P.M., Rosenkrantz, D.J., and Stearns, R.E. Attributed translations. Journal of Computer and Systems Sciences 9, 3 (December 1974), 279--307.
• 10: {MeF} Medina-Mora, R. and Feiler, P. An incremental programming environment. IEEE Transactions on Software Engineering SE-7, 5 (September 1981) 472--482.
• 11: {MiW} Mikelsons, M. and Wegman, M.N. PDE1L: The PL1L program development environment principles of operation. Research report RC8513, IBM Watson Research Center, Yorktown Heights, November 1980.
• 12: {Rep} Reps, T. The Synthesizer Editor Generator: Reference Manual. September 1981.
• 13: Barry K. Rosen, Linear cost is sometimes quadratic, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.117-124, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567545]
• 14: Tim Teitelbaum , Thomas Reps, The Cornell program synthesizer: a syntax-directed programming environment, Communications of the ACM, v.24 n.9, p.563-573, Sept. 1981 [doi>10.1145/358746.358755]