On Parsing and Compiling Arithmetic Expressions on Vector Computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Parsing and Compiling Arithmetic Expressions on Vector Computers

Full text

Pdf (1.39 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 2 , Issue 2 (April 1980) table of contents

Pages: 203 - 224

Year of Publication: 1980

ISSN:0164-0925

Author

Charles N. Fischer

Department of Computer Sciences, University of Wisconsin-Madison, 1210 W. Dayton St., Madison, WI

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 25, Citation Count: 4

Additional Information:

abstract references cited by index terms 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/357094.357099 What is a DOI?

ABSTRACT

The problem of parsing and compiling arithmetic expressions on vector computers is considered. Methods are developed which allow encodings of one or more arithmetic expressions to be transformed directly into encodings of their corresponding derivation trees. The algorithm which performs this transformation is compact, efficient, and able to make extensive use of concurrent vector operations. Routines which concurrently transverse encoded derivation trees in a top-down or bottom-up manner are presented. These routines can be used to structure efficient, compact, and highly concurrent algorithms which complete the process of compiling arithmetic expressions.

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	A description of the advanced scientific computer system. Texas Instruments Inc., Austin, Tex., April 1973.
	2	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	3	BAER, J., AND ELLIS, C. Model, design, and evaluation of a compiler for a parallel processing environment. IEEE Trans. Sofiw. Eng. SE-3, 6 (Nov. 1977), 394-405.
	4	BASKETT, F., AND KELLER, T. An evaluation of the Cray-1 computer. Presented at the Symp. High Speed Computer and Algorithm Organization, Champaign, Ill., April 13-15, 1977.
	5	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	6	Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
	7	Description of Cray-l. Cray Research Corp., Chippewa Falls, Wis. 1975.
	8	Michael K. Donegan , Stuart W. Kartzke, Lexical analysis and parsing techniques for a vector machine, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.138-145, March 18-19, 1975, New York, New York
	9	Charles Nicholas Fischer, On parsing context free languages in parallel environments., 1975
	10	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	11	KNUTI{, D. An empirical study of FORTRAN programs. Softw. Pract. Exper. I (1971), 105-133.
	12	Howard E. Krohn, A parallel approach to code generation for Fortran like compilers, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.146-152, March 18-19, 1975, New York, New York
	13	KvcK, D., ANO MARUYAMA, K. Time bounds on the parallel evaluation of arithmetic expressions. SIAM J. Comput. 4, 2 (June 1975), 147-162.
	14	Neil Lincoln, Parallel programming techniques for compilers, ACM SIGPLAN Notices, v.5 n.10, October 1970 [doi>10.1145/987475.987478]
	15	M. Dennis Mickunas , Richard M. Schell, Parallel Compilation In A Multiprocessor Environment (Extended Abstract), Proceedings of the 1978 annual conference, p.241-246, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804105]
	16	David E. Muller , Franco P. Preparata, Restructuring of Arithmetic Expressions For Parallel Evaluation, Journal of the ACM (JACM), v.23 n.3, p.534-543, July 1976 [doi>10.1145/321958.321973]
	17	C. V. Ramamoorthy , H. F. Li, Pipeline Architecture, ACM Computing Surveys (CSUR), v.9 n.1, p.61-102, March 1977 [doi>10.1145/356683.356687]
	18	RICHARDS, M. BCPL: A tool for compiler writing and systems programming. Proc. AFIPS 1969 SJCC, vol. 34, AFIPS Press, Arlington, Va., pp. 557-566.
	19	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 [doi>10.1145/321607.321620]
	20	STAR-100 Computer System. Publ. 6025600, Control Data Corp., Arden Hills, Minn., 1973.
	21	Mary Zosel, A parallel approach to compilation, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.59-70, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512933]

CITED BY 4

	Eliezer Dekel , Sartaj Sahni, Parallel Generation of Postfix and Tree Forms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.300-317, July 1983
	N. H. Madhavji , I. R. Wilson, Cray Pascal, ACM SIGPLAN Notices, v.17 n.6, p.1-14, June 1982
	Chandra R. Asthagiri , Jerry L. Potter, Parallel Compilation on Associative Computers, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.315-318, August 24-26, 1994
	Henk Alblas , Rieks op den Akker , Paul Oude Luttighuis , Klaas Sikkel, A bibliography on parallel parsing, ACM SIGPLAN Notices, v.29 n.1, p.54-65, Jan. 1994