Efficient evaluation of circular attribute grammars

ABSTRACT

We present efficient algorithms for exhaustive and incremental evaluation of circular attributes under any conditions that guarantee finite convergence. The algorithms are derived from those for noncircular attribute grammars by partitioning the underlying attribute dependency graph into its strongly connected components and by ordering the evaluations to follow a topological sort of the resulting directed acyclic graph. The algorithms are efficient in the sense that their worst-case running time is proportional to the cost of computing the fixed points of only those strongly connected components containing affected attributes or attributes directly dependent on affected attributes. When the attribute grammar is noncircular or the specific dependency graph under consideration is acyclic, both algorithms reduce to the standard optimal algorithms for noncircular attribute evaluation.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ALBL^S, H. Incremental simple multi-pass attribute evaluation. In Proceedings of the NGI/ SION 1986 Symposium. 1986, pp. 319-342.
• 3: Wayne Allen Babich, High-level data flow analysis using a parse tree representation of the program., 1977
• 4: BABICH, W. A., AND JAZAYERI, M. The method of attributes for data flow analysis. Part I: Exhaustive analysis. Acta Inf. 10, 3 (Oct. 1978), 245-264.
• 5: Rolf Bahlke , Gregor Snelting, The PSG system: from formal language definitions to interactive programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.547-576, Oct. 1986 [doi>10.1145/6465.20890]
• 6: George McArthur Beshers , Roy Harold Campbell, Maintained and constructor attributes, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.34-42, June 25-28, 1985, Seattle, Washington, United States
• 7: 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]
• 8: CHEBOTAR, K.S. Some modifications of Knuth's algorithm for verifying cyclicity of attribute grammars. Program. Comput. Softw. 7, I (Feb. 1981), 58-61.
• 9: 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]
• 10: Alan Demers , Anne Rogers , Frank Kenneth Zadeck, Attribute propagation by message passing, ACM SIGPLAN Notices, v.20 n.7, p.43-59, July 1985
• 11: DERANSART, P., JOURDAN, M., AND LORHO, B. Speeding up circularity tests for attribute grammars. Acta Inf. 21, 4 (Nov. 1984), 375-391.
• 12: Rodney Farrow, LINGUIST-86: Yet another translator writing system based on attribute grammars, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.160-171, June 23-25, 1982, Boston, Massachusetts, United States
• 13: Rodney Farrow, Automatic generation of fixed-point-finding evaluators for circular, but well-defined, attribute grammars, ACM SIGPLAN Notices, v.21 n.7, p.85-98, July 1986
• 14: C. N. Fischer , Gregory F. Johnson , Jon Mauney , Anil Pal , Daniel L. Stock, The Poe language-based editor project, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.21-29, April 1984
• 15: Harald Ganzinger , Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, A truly generative semantics-directed compiler generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.172-184, June 23-25, 1982, Boston, Massachusetts, United States
• 16: 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]
• 17: Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975 [doi>10.1145/361227.361231]
• 18: 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]
• 19: 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]
• 20: Larry G. Jones, Incremental vlsi design systems based on circular attribute grammars (fixed point computation, computer aided design), 1986
• 21: Larry G. Jones , Janos Simon, Hierarchical VLSI design systems based on attribute grammars, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.58-69, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512650]
• 22: JOURDAN, M., AND PARIGOT, D. More on speeding up circularity tests for attribute grammars. INRIA Rapports de Recherche No. 828, 1988 Institut National de Rocherche en Inform, Rocquencourt, France.
• 23: KASTENS, U. Ordered attribute grammars. Acta Inf. 13, 3 (March 1980), 229-256.
• 24: KASTENS, V., HUTT, B., AND ZIMMERMAN, r. GAG.' A Practical Compiler Generator. Lecture Notes in Computer Science, vol. 141. Springer-Verlag, New York, 1982.
• 25: 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]
• 26: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 27: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 28: KNUTH, D. E. Semantics of context-flee languages. Math. Syst. Theory 2, 2 (June 1968), 127-145.
• 29: KNUTH, D.E.Semantics of context-free languages: Correction. Math. Syst. Theory 5, I (Mar. 1971), 95-96.
• 30: LEWIS, P. M., ROSENKRANTZ, n. J., AND STEARNS, R.E. Attributed translations. J. Comput. Syst. Sci. 9, 3 (Dec. 1974), 279-307.
• 31: LORHO, B., AND PAIR, C. Algorithms for checking consistency of attribute grammars. In Proving and Improving Programs. Symposium IRIA. (Arc-et-Senans, France) 1975, 29-54.
• 32: R~,IH.~., K. J., AND SAARINEN, M. Testing attribute grammars for circularity. Acta Inf. 17, 2 (June 1982), 185-192.
• 33: 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]
• 34: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 35: 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
• 36: 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]
• 37: 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]
• 38: SKEDZELESKI, S.K. Definition and use of attribute reevaluation in attributed grammars. Tech. Rep. 340, Dept. of Computer Science, Univ. of Wisconsin, Madison, Wisconsin, 1978.
• 39: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 40: TARJAN, R.E. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 2 (June 1972), 146-160.
• 41: 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]
• 42: W. M. Waite , G. Goos, Compiler Construction, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• 43: J. A. Walz , G. F. Johnson, Incremental evaluation for a general class of circular attribute grammars, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.209-221, June 20-24, 1988, Atlanta, Georgia, United States
• 44: YEH, D. On incremental evaluation of ordered attributed grammars. BIT 23, 3 (1983), 308-320.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Theory