Incremental evaluation for attribute grammars with application to syntax-directed editors

ABSTRACT

A syntax-directed editor is a tool for structured program development. Such an editor can enforce syntactic correctness incrementally by restricting editing operations to legitimate modifications of the program's context-free derivation tree. However, not all language features can be described by the context-free formalism. To build editors that enforce non-context-free correctness, a more powerful specification technique is needed. In this paper we discuss the advantages of attribute grammars as a specification technique for a syntax-directed editing system. We also present an efficient algorithm for incrementally evaluating attributes as a program tree is derived.

REFERENCES

• 1: Babich, W. A. and Jazayeri, M. The method of attributes for data flow analysis. part I: exhaustive analysis, part II: demand analysis. Acta Informatica 10, 3 (0ctober 1978), 245-272.
• 2: 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]
• 3: 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]
• 4: Donzeau-Gouge, V., Huet, G., Kahn, G., Lang B., and Levy, J. J. A structure-oriented program editor. Technical Report, IRIA-LABORIA, France 1975.
• 5: Donzeau-Gouge, V., Huet, G., Kahn, G., and Lang B. Programming environments based on structured editors: the MENTOR experience. Technical Report, INRIA, France, May 1980.
• 6: Fang, I. FOLDS, a declarative formal language definition system. Tech. Report No. STAN-CS-72-329, Computer Science Dept., Stanford University, December 1972.
• 7: Rodney Wayne Farrow, Attributed grammar models for data flow analysis., 1977
• 8: Wilfred James Hansen, Creation of hierarchic text with a computer display, 1971
• 9: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 10: 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]
• 11: 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]
• 12: Knuth, D. E. Semantics of context free languages. Math. Systems Theory J. 2, 2 (1968), 127-145.
• 13: Lewis, P. M., Rozenkranz, D. J., and Stearns, R. E. Attributed translations. J. of Comp. and Systems Sciences 9, 3 (December 1974), 279-307.
• 14: 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.
• 15: Reps, T. The Synthesizer Editor Generator. In preparation.
• 16: Skedzeleski, S. K. Definition and use of attribute reevaluation in attributed grammars. Technical Report 340, Computer Sciences Department, University of Wisconsin-Madison, October 1978.
• 17: Tim Teitelbaum, The Cornell Program Synthesizer: A Microcomputer Implementation of PL/CS, Cornell University, Ithaca, NY, 1979
• 18: Teitelbaum, T. The Cornell Program Synthesizer: a tutorial introduction. Tech. Report No. TR79-381, Dept. Computer Science, Cornell University, July 1979, Revised June 1980.
• 19: Teitelbaum, T. and Reps, T. The Cornell Program Synthesizer: a syntax-directed programming environment. Tech. Report No. TR80-421, Dept. Computer Science, Cornell University, May 1980.
• 20: Warren, S. K. The efficient evaluation of attribute grammars. M. A. Thesis, Rice University, Houston, Texas, April 1975.
• 21: Scott Kipling Warren, The coroutine model of attribute grammar evaluation., 1976
• 22: Wegman, M. N. Parsing for structural editors. Conference Record of the Twenty-first annual Symposium on Foundations of Computer Science, October 1980, 320-327.