Dynamically bypassing copy rule chains in attribute grammars

ABSTRACT

Attribute grammars require copy rules to transfer values between attribute instances distant in an attributed parse tree. We introduce copy bypass attribute propagation that dynamically replaces copy rules with nonlocal dependencies, resulting in faster incremental evaluation. A evaluation strategy is used that approximates a topological ordering of attribute instances. The result is an efficient incremental evaluator that allows multiple subtree replacement on any noncircular attribute grammar.

REFERENCES

• 1: 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
• 2: {J84} Johnson, Gregory F. An approach to incremental semantics. TR 547, University of Wisconsin, Madison, July 1984.
• 3: 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]
• 4: {K80} Kastens, U. Ordered attribute grammars. <i>Acta Inf.</i> 13, 3, 1980, pp. 229--256.
• 5: Brian W. Kernighan , P. J. Plauger, Software Tools in Pascal, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 6: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 7: 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]
• 8: 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
• 9: 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]
• 10: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 11: {Y83} Yeh, Dashing, On Incremental Evaluation of Ordered Attributed Grammars. <i>BIT 23,</i> 1983, 308--320.