Automatic generation of near-optimal linear-time translators for non-circular attribute grammars

ABSTRACT

Attribute grammars are an extension of context-free grammars devised by Knuth as a formalism for specifying the semantics of a context-free language along with the syntax of the language. The syntactic phase of the translation process has been extensively studied and many techniques are available for automatically generating efficient parsers for context-free grammars. Attribute grammars offer the prospect of similarly automating the implementation of the semantic phase. In this paper we present a general method of constructing, for any non-circular attribute grammar, a deterministic translator which will perform the semantic evaluation of each syntax tree of the grammar in time linear with the size of the tree. Each tree is traversed in a manner particularly suited to the shape of the tree, yielding a near optimal evaluation order for that tree. Basically, the translator consists of a finite set of "Local Control Automata", one for each production; these are ordinary finite-state acyclic automata augmented with some special features, which are used to regulate the evaluation process of each syntax tree. With each node in the tree there will be associated the Local Control Automaton of the production applying at the node. At any given time during the translation process all Local Control Automata are inactive, except for the one associated with the currently processed node, which is responsible for directing the next steps taken by the translator until control is finally passed to a neighbour node, reactivating its Local Control Automaton. The Local Control Automata of neighbour nodes communicate with each other.The construction of the translator is custom tailored to each individual attribute grammar. The dependencies among the attributes occurring in the semantic rules are analysed to produce a near-optimal evaluation strategy for that grammar. This strategy ensures that during the evaluation process, each time the translator enters some subtree of the syntax tree, at least one new attribute evaluation will occur at each node visited. It is this property which distinguishes the method presented here from previously known methods of generating translators for unrestricted attribute grammars, and which causes the translators to be near-optimal.

REFERENCES

• 1: {A&U1} Aho, A. V. and Ullman J. D. "Properties of Syntax Directed Translations". J. Computer Systems Sci., No. 3, pp. 319-364, (1965).
• 2: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 3: {A&U3} Aho, A. V. and Ullman, J. D. "Translations on a Context Free Grammar". Inform. Contr. 19,5, pp. 439-475, (1971).
• 4: 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]
• 5: {C&H} Cohen, R. and Harr, E. "Automatic Generation of Near-Optimal Linear-Time Translators for Non-Circular Attribute Grammars", Technical Report #120, Dept. of Computer Science, Technion, Israel, March 1978.
• 6: {D} Dreisbach, T. A. A Declarative Semantic Definition of PL360. UCLA-7289, Computer Science Dept. UCLA (1972).
• 7: {F} Fang, I. FOLDS, a Declarative Formal Language Definition System. STAN-72-329, Computer Science Dept., Stanford University (1972).
• 8: Susan L. Gerhart, Correctness-preserving program transformations, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.54-66, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512983]
• 9: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 10: {J2} Jazayeri, M. Live Variable Analysis, attribute Grammars, and Program Optimization: Draft, Dept. of Comp. Sci., University of N. Carolina, Chapel Hill, N. C. (1975).
• 11: 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]
• 12: {K1} Knuth, D. E. "Semantics of Context Free Languages". Math. Systems Theory J., No. 2, pp. 127-145 (1968).
• 13: {K2} Knuth, D. E. "Semantics of Context Free Languages: Correction". Math. Systems Theory J., No. 5, p. 95 (1971).
• 14: {K3} Knuth, D. E. "Examples of Formal Semantics", Symp. on Semantics of Algorithm Lanuages. Lecture notes in Mathematics, Vo. 188, Springer-Verlag, New York (1971).
• 15: 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]
• 16: {L&R&S} Lewis, P. M., Rosenkranz, D. J. and Stearns, R. E. "Attributed Translations". J. of Comp. and System Sciences, vol. 9, No. 3, pp. 279-307 (1974).
• 17: Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
• 18: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 19: D. Neel , M. Amirchahy, Removal of invariant statements from nested-loops in a single effective compiler pass, ACM SIGPLAN Notices, v.10 n.3, p.87-96, March 1975
• 20: {P} Petrick, S. R. Semantic Interpretation in the REQUEST System. IBM Res. Report, RC-4457 (1973).
• 21: Scott Kipling Warren, The coroutine model of attribute grammar evaluation., 1976
• 22: Harry B. Hunt, III , Thomas G. Szymanski , Jeffrey D. Ullman, On the complexity of LR(k) testing, Communications of the ACM, v.18 n.12, p.707-716, Dec. 1975 [doi>10.1145/361227.361232]