Composing tree attributions

ABSTRACT

Using the simple tree attributions described in this paper, attribute values can themselves be trees, enabling attribution to be used for tree transformations. Unlike higher-order attribute grammars, simple tree attributions have the property of descriptional composition, which allows a complex transformation to be built up from simpler ones, yet be executed efficiently. In contrast to other formalisms that admit descriptional composition, notably composable attribute grammars, simple tree attributions have the expressive power to handle remote references and recursive syntactic (tree-generating) functions, providing significantly more general forms of attribution and transformation.

REFERENCES

• 1: Robert A Ballance, Syntactic and Semantic Checking in, University of California at Berkeley, Berkeley, CA, 1989
• 2: BALLANCE, R. A., AND GRAHAM, S. L. Incremental consistency maintenance for interactive applications. In Proc. of the Eighth International Conference on Logic Programming, K. Furukawa, Ed. The MIT Press, Cambridge, Massachusetts and London, England, 1991, pp. 895-9O9.
• 3: BOYLAND, J., FARNUM, C., AND GRAHAM, S. L. Attributed transformational code generation for dynamic compilers, in Code Generation- Concepts, Tools, Techniques. Workshops in Computer Science, R. Giegerich and S. L. Graham, Eds. Springer-Verlag, Berlin, Heidelberg, New York, 1992, pp. 227-254.
• 4: COURCELLE, B., AND FRANCHI-ZANNETTACCI, P. Attribute grammars and recursive program schemes. Theoretical Computer Science 17 (1982), 163-191,235-257.
• 5: Charles Farnum, Pattern-based tree attribution, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.211-222, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143209]
• 6: R. Farrow , T. J. Marlowe , D. M. Yellin, Composable attribute grammars: support for modularity in translator design and implementation, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.223-234, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143210]
• 7: G File, Classical and incremental evaluators for attribute grammars, Proceedings of the 11th colloquium on trees in algebra and programming, p.112-126, July 1986, Nice, France
• 8: Harald Ganzinger , Robert Giegerich, Attribute coupled grammars, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.157-170, June 17-22, 1984, Montreal, Canada
• 9: R. Giegerich, Composition and evaluation of attribute coupled grammars, Acta Informatica, v.25 n.4, p.355-423, May 1988 [doi>10.1007/BF02737108]
• 10: G. Kahn, Natural semantics, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.22-39, February 1987, Passau, Germany
• 11: 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]
• 12: KNUTH, D. E. Semantics of context free languages. Math Systems Theory P, 2 (June 1968), 127-145. Errata Math Systems Theory 5(1):95-96(1971).
• 13: S. Doaitse Swierstra , Harald Vogt, Higher Order Attribute Grammars, Proceedings on Attribute Grammars, Applications and Systems, p.256-296, June 04-13, 1991
• 14: H. H. Vogt , S. D. Swierstra , M. F. Kuiper, Higher order attribute grammars, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.131-145, June 19-23, 1989, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Theory