On arithmetic expressions and trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On arithmetic expressions and trees

Full text

Pdf (534 KB)

Source

Communications of the ACM archive
Volume 12 , Issue 2 (February 1969) table of contents

Pages: 81 - 84

Year of Publication: 1969

ISSN:0001-0782

Author

R. R. Redziejowski

IBM Nordic Lab., Lidingö, Sweden

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 36, Citation Count: 18

Additional Information:

abstract references cited by index terms

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/362848.362859 What is a DOI?

ABSTRACT

A description is given of how a tree representing the evaluation of an arithmetic expression can be drawn in such a way that the number of accumulators needed for the computation can be represented in a straightforward manner. This representation reduces the choice of the best order of computation to a specific problem under the theory of graphs. An algorithm to solve this problem is presented.

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.

Ikuo Nakata, On compiling algorithms for arithmetic expressions, Communications of the ACM, v.10 n.8, p.492-494, Aug. 1967 [doi>10.1145/363534.363549]

CITED BY 18

	A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California
	Bhaskaram Prabhala , Ravi Sethi, Efficient Computation of Expressions with Common Subexpressions, Journal of the ACM (JACM), v.27 n.1, p.146-163, Jan. 1980
	A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976
	E. G. Coffman, Jr. , Ravi Sethi, Instruction Sets for Evaluating Arithmetic Expressions, Journal of the ACM (JACM), v.30 n.3, p.457-478, July 1983
	Bhaskaram Prabhala , Ravi Sethi, Efficient computation of expressions with common subexpressions, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.222-230, January 23-25, 1978, Tucson, Arizona
	Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970
	A. V. Aho , S. C. Johnson, Optimal code generation for expression trees, Proceedings of seventh annual ACM symposium on Theory of computing, p.207-217, May 05-07, 1975, Albuquerque, New Mexico, United States
	John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976
	Paul B. Schneck, A survey of compiler optimization techniques, Proceedings of the annual conference, p.106-113, August 27-29, 1973, Atlanta, Georgia, United States
	J. L. Bruno , T. Lassagne, The Generation of Optimal Code for Stack Machines, Journal of the ACM (JACM), v.22 n.3, p.382-396, July 1975
	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
	Ravi Sethi, Complete register allocation problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.182-195, April 30-May 02, 1973, Austin, Texas, United States
	Waleed M. Meleis , Edward S. Davidson, Dual-issue scheduling with spills for binary trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.678-686, January 17-19, 1999, Baltimore, Maryland, United States
	D. Bernstein , J. M. Jaffe , M. Rodeh, Scheduling arithmetic and load operations in parallel with no spilling, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.263-273, January 21-23, 1987, Munich, West Germany
	Robert W. Witty, The switching reverse polise algorithm, ACM SIGPLAN Notices, v.12 n.9, p.114-123, September 1977
	Jerry L. Apperson, Optimal evaluation order for expressions with redundant subexpressions, ACM SIGPLAN Notices, v.8 n.6, June 1973
	G. Chroust, Scope conserving expression evaluation: a class of storage optimal evaluation strategies for arithmetic expressions, ACM SIGPLAN Notices, v.12 n.12, p.68-72, December 1977
	Alfred V. Aho , Ravi Sethi , J. D. Ullman, A formal approach to code optimization, ACM SIGPLAN Notices, v.5 n.7, p.86-100, July 1970