Translation of attribute grammars into procedures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Translation of attribute grammars into procedures

Full text

Pdf (1.22 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 6 , Issue 3 (July 1984) table of contents

Pages: 345 - 369

Year of Publication: 1984

ISSN:0164-0925

Author

Takuya Katayama

Tokyo Institute of Technology, Tokyo, Japan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 30, Citation Count: 16

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/579.586 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ASBROCK, B. Attribut-Implementierung und -Optimierung f/Jr Attribute Grammatiken. Diplomarbeit, Fakult/it ftir Informatik, Universit/it Karlsruhe, Karlsruhe, West Germany, July 1979.
	2	BAmCH, W.A., AND JAZAYERI, M. The method of attributes for data flow analysis, parts I and II. Acta Inf. 10 (1978), 245-272.
	3	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]
	4	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]
	5	Harald Ganzinger , Knut Ripken , Reinhard Wilhelm, MUG1 - an incremental compiler-compiler, Proceedings of the annual conference, p.415-418, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805629]
	6	Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
	7	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]
	8	JAZAYERI, M., AND POZEFSKY, D. Algorithms for efficient evaluation of multi-pass attribute grammars without a parse tree. Tech. Rep. TR77-001, Department of Computer Science, Univ. of North Carolina, Chapel Hill, N.C., May 1974.
	9	KASTENS, U. Ordered attribute grammars. Acta Inf. 13 (1980), 229-256.
	10	KASTENS, U., AND ZIMMERMANN, E. GAG-A generator based on attributed grammar. Bericht Nr. 14/80, Institute fiir Informatik II, Universitfit Karlsruhe, Karlsruhe, West Germany.
	11	Takuya Katayama, HFP: A hierarchical and functional programming based on attribute grammar, Proceedings of the 5th international conference on Software engineering, p.343-352, March 09-12, 1981, San Diego, California, United States
	12	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]
	13	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]
	14	KNUTH, D.E. Examples o{ Formal Semantics. Lecture Notes in Mathematics, vol. 188. Springer- Verlag, New York, 1971.
	15	KNUTH, D.E. Semantics of context-free languages. Math. Syst. Theory J.2 (1968), 127-145.
	16	KNUTH, D.E. Semantics of context-free languages: Correction. Math. Syst. Theory J.5 (1971), 95.
	17	LEWIS, P.M., ROSENKRANTZ, D.J., AND STEARNS, R.E. Attributed translations. J. Comput. Syst. Sck 9 (1974), 279-307.
	18	MADSEN, O.L. On defining semantics by means of extended attribute grammars. Rep. DAIMI PB-109, Computer Science Department, Aarhus Univ., Aarhus, Denmark, Jan. 1980.
	19	POZEFSK~, D. Building efficient pass-oriented attribute grammar evaluators. Tech. Rep. TR 79-006, Dept. of Computer Science, Univ. of North Carolina, Chapel Hill, N.C., 1979.
	20	RAinS, K.J., SAARINEN, M., $OiSALON-$OiNINEN, E., AND TIENARI, M. The compiler writing system HLP. Rep. A-1978-2, Dept. of Computer Science, Univ. of Helsinki, Helsinki, Finland, Mar. 1978.
	21	Mikko Saarinen, On Constructing Efficient Evaluators for Attribute Grammars, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.382-397, July 17-21, 1978

CITED BY 16

	P. Bottoni , M. F. Costabile , P. Mussio, Specification and dialogue control of visual interaction through visual rewriting systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.6, p.1077-1136, Nov. 1999
	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
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Michael Sonnenschein, Graph translation schemes to generate compiler parts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.473-490, Oct. 1987
	Alan Carle , Lori Pollock, On the optimality of change propagation for incremental evaluation of hierarchical attribute grammars, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.1, p.16-29, Jan. 1996
	W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States
	Yanhong A. Liu , Tim Teitelbaum, Caching intermediate results for program improvement, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.190-201, June 21-23, 1995, La Jolla, California, United States
	Thomas Reps, Scan grammars: parallel attribute evaluation via data-parallelism, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.367-376, June 30-July 02, 1993, Velen, Germany
	A. Klaiber , M. Gokhale, Parallel Evaluation of Attribute Grammars, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.206-220, March 1992
	Takuya Katayama , Hisashi Sasaki, Global storage allocation in attribute evaluation, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.26-37, January 01, 1986, St. Petersburg Beach, Florida
	Ram Mandayam , Ranga Vemuri, Performance specification using attributed grammars, Proceedings of the 30th international conference on Design automation, p.661-667, June 14-18, 1993, Dallas, Texas, United States
	Yasser Kotb , Katsuhiko Gondow , Takuya Katayama, Optimizing the Execution Time for Checking the Consistency of XML Documents, Journal of Intelligent Information Systems, v.22 n.3, p.257-279, May 2004
	Jean Berstel , Stefano Crespi Reghizzi , Gilles Roussel , Pierluigi San Pietro, A scalable formal method for design and automatic checking of user interfaces, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.2, p.124-167, April 2005
	Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998
	Marjan Mernik , Nikolaj Korbar , Viljem Žumer, LISA: a tool for automatic language implementation, ACM SIGPLAN Notices, v.30 n.4, p.71-79, April 1995
	Eva Magnusson , Görel Hedin, Circular reference attributed grammars — their evaluation and applications, Science of Computer Programming, v.68 n.1, p.21-37, August, 2007

INDEX TERMS

Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Translator writing systems and compiler generators

F. Theory of Computation
F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
F.4.3 Formal Languages
Subjects: Operations on languages

General Terms:
Algorithms, Languages, Theory

REVIEW

"Jan Messerschmidt : Reviewer"

When considering the evaluation of attributes in an attribute grammar, two approaches are possible. The first one, known as the Kennedy and Warren approach [1], uses automata attached to every node in the abstract syntax tree. These automata con more...

Collaborative Colleagues:

Takuya Katayama: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player