article

Open access

On Parsing and Compiling Arithmetic Expressions on Vector Computers

Editor: Susan L. Graham Author:

Charles N. FischerAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 2, Issue 2

Pages 203 - 224

https://doi.org/10.1145/357094.357099

Published: 01 April 1980 Publication History

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

[1]

A description of the advanced scientific computer system. Texas Instruments Inc., Austin, Tex., April 1973.

[2]

AHO, A., AND ULLMAN, J. The Theory of Parsing, Translation, and Compiling, vol. 1. Prentice- Hall, Englewood Cliffs, N.J., 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]

BRES?, R. The parallel evaluation of general arithmetic expressio~s. J. ACM 21, 2 (April 1974), 201-206.

[6]

DEnNiS, J., ANO MISV~qAS, D. A preliminary architecture for a basic data-flow processor. In Proc. 2nd Annu. Syrup. Computer Architecture, Jan. 1975, pp. 126-132.

[7]

Description of Cray-l. Cray Research Corp., Chippewa Falls, Wis. 1975.

[8]

DO~EGAN, M., AND tCa?ZKE, S. Lexical analysis and parsing techniques for a vector machine. In Proc. Conf. Programming Languages and Compilers for Parallel and Vector Machines, SIGPLAN Notices 10, 3 (March 1975), 138-145.

[9]

FISCHER, C. On parsing context free languages in parallel environments. Ph.D. dissertation, Comput. Sci. Dep., Cornell Univ., Ithaca, N. Y., 1975.

[10]

HoPcRop'r, J., AND ULLMAN, g. Formal Languages and Their Relation to Automata. Addison- Wesley, Reading, Mass., 1969.

[11]

KNUTI{, D. An empirical study of FORTRAN programs. Softw. Pract. Exper. I (1971), 105-133.

[12]

KROHN, H. A parallel approach to code generation for FORTRAN-hke compilers. In Proc. Conf. Programming Languages and Compilers for Parallel and Vector Machines, SIGPLAN Notices 10, 3 (March 1975), 146-149.

[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]

LINCOLN, N. Parallel programming techniques for compilers. SIGPLAN Notices 5, 10 (Nov. 1970).

[15]

MICKUNAS, M., AND SCHELL, R. Parallel compilation in a multiprocessor environment. In Proc. ACM 1978 Annu. Conf., Dec. 1978, pp. 241-246.

[16]

MULLER, D., AND PREPARATA, F. Restructuring of arithmetic expressions for parallel evaluation. J. ACM 23, 3 (July 1976), 534-543.

[17]

RAMAMOORTIg~, C., AND LI, H. Pipeline architecture. Cornput. Surv. 9, 1 (March 1977), 61-102.

[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]

SETm, R., AND ULLMAN, J. The generation of optimal code for arithmetic expressions. J. ACM 17, 4 (Oct. 1970), 715-728.

[20]

STAR-100 Computer System. Publ. 6025600, Control Data Corp., Arden Hills, Minn., 1973.

[21]

ZOSEL, M. A parallel approach to compilation, in Proc. ACM Syrup. Principles of Programming Languages, Boston, Mass., Oct. 1978; pp. 59-70.ss

Cited By

Dekel ENtafos SPeng S(2005)Parallel tree techniques and code optimizationVLSI Algorithms and Architectures10.1007/3-540-16766-8_18(205-216)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_18
Asthagiri CPotter J(1994)Parallel Compilation on Associative ComputersProceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques10.5555/647042.713816(315-318)Online publication date: 24-Aug-1994
https://dl.acm.org/doi/10.5555/647042.713816
Alblas Hop den Akker RLuttighuis PSikkel K(1994)A bibliography on parallel parsingACM SIGPLAN Notices10.1145/181577.18158629:1(54-65)Online publication date: 1-Jan-1994
https://dl.acm.org/doi/10.1145/181577.181586
Show More Cited By

Index Terms

On Parsing and Compiling Arithmetic Expressions on Vector Computers
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Parsers
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Parsing

Recommendations

LLLR parsing
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

The idea of an LLLR parsing is presented. An LLLR(k) parser can be constructed for any LR(k) grammar but it produces the left parse of the input string in linear time (in respect to the length of the derivation) without backtracking. If used as a basis ...
Parsing minimalist languages
Parsing and compiling using Prolog

This paper presents the material needed for exposing the reader to the advantages of using Prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 2, Issue 2

April 1980

126 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/357094

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1980 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1980

Published in TOPLAS Volume 2, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
431
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)4

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dekel ENtafos SPeng S(2005)Parallel tree techniques and code optimizationVLSI Algorithms and Architectures10.1007/3-540-16766-8_18(205-216)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_18
Asthagiri CPotter J(1994)Parallel Compilation on Associative ComputersProceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques10.5555/647042.713816(315-318)Online publication date: 24-Aug-1994
https://dl.acm.org/doi/10.5555/647042.713816
Alblas Hop den Akker RLuttighuis PSikkel K(1994)A bibliography on parallel parsingACM SIGPLAN Notices10.1145/181577.18158629:1(54-65)Online publication date: 1-Jan-1994
https://dl.acm.org/doi/10.1145/181577.181586
Langlois L(1991)Systolic parsing of context-free languagesInternational Journal of Parallel Programming10.1007/BF0137936219:4(333-355)Online publication date: 1-Aug-1991
https://dl.acm.org/doi/10.1007/BF01379362
Srikant YShankar P(1987)A new parallel algorithm for parsing arithmetic infix expressionsParallel Computing10.1016/0167-8191(87)90028-74:3(291-304)Online publication date: Jun-1987
https://doi.org/10.1016/0167-8191(87)90028-7
Baccelli FMussi P(1986)An Asynchronous Parallel Interpreter for Arithmetic Expressions and Its EvaluationIEEE Transactions on Computers10.1109/TC.1986.167674835:3(245-256)Online publication date: 1-Mar-1986
https://dl.acm.org/doi/10.1109/TC.1986.1676748
Li KSchwetman H(1985)Vector C: A vector processing languageJournal of Parallel and Distributed Computing10.1016/0743-7315(85)90032-22:2(132-169)Online publication date: May-1985
https://doi.org/10.1016/0743-7315(85)90032-2
Partsch H(1984)Transformational Derivation of Parsing Algorithms Executable on Parallel ArchitecturesProgrammiersprachen und Programmentwicklung10.1007/978-3-642-69393-9_3(41-57)Online publication date: 1984
https://doi.org/10.1007/978-3-642-69393-9_3
Dekel ESahni S(1983)Parallel Generation of Postfix and Tree FormsACM Transactions on Programming Languages and Systems10.1145/2166.3572115:3(300-317)Online publication date: 1-Jul-1983
https://dl.acm.org/doi/10.1145/2166.357211
Madhavji NWilson I(1982)Cray PascalACM SIGPLAN Notices10.1145/872726.80697517:6(1-14)Online publication date: 1-Jun-1982
https://dl.acm.org/doi/10.1145/872726.806975
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents