article

On parsing arithmetic expressions in a multiprocessing environment

Authors:

François Baccelli,

Thierry FleuryAuthors Info & Claims

Acta Informatica, Volume 17, Issue 3

Pages 287 - 310

https://doi.org/10.1007/BF00264355

Published: 01 August 1982 Publication History

Abstract

Some decomposition of the parsing of the sentences of context-free grammars into sequences of independant sub-tasks is proposed. An example of grammar is presented, for which this decomposition provides an efficient parser for a multiprocessing environment. The average speed-up resulting from the parallelization of the parser of an arithmetic infix grammar is evaluated by means of probabilistic models and real world measurements.

References

[1]

Baer, J.L., Ellis, C.S.: Model, design, and evaluation of a compiler for a parallel processing environment. IEEE soft. Eng. 3, N¿ 6 (1977)

Crossref

Google Scholar

[2]

Banatre, J.P., Routeau, J.P., Trilling, L.: An event driven compiling technique. In: Communications of the ACM, Vol. 22, N¿ 1 (1979)

Crossref

Google Scholar

[3]

Fisher, C.N.: On parsing and compiling arithmetic expressions on vector computers. ACM Trans. Program. Lang. and Syst. 2, 203---224 (1980)

Digital Library

Google Scholar

[4]

Gonzales, R.C., Thomason, M.G.: Syntactic pattern recognition. Addison Wesley 1978

Google Scholar

[5]

Good, I.J.: The number of individuals in the cascade process. Proc. Camb. Phil. Soc. 45, 360---363 (1949)

Crossref

Google Scholar

[6]

Gries, D.: Compiler construction for digital computers. John Wiley & Sons, New York 1971

Crossref

Google Scholar

[7]

Harris, T.E.: The theory of branching processes. Springer, Berlin 1963

Google Scholar

[8]

Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Addison-Wesley 1969

Crossref

Google Scholar

[9]

Mickunas, M., Schell, E.: Parallel compilation in a multiprocessor environment. In: Proc. ACM Annu. Conf. 1978, pp. 241---246

Crossref

Google Scholar

Cited By

View all

Ge CLi YEilebrecht EChandramouli BKossmann DBoncz PManegold SAilamaki ADeshpande AKraska T(2019)Speculative Distributed CSV Data Parsing for Big Data AnalyticsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319898(883-899)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319898
Zhao ZShen X(2015)On-the-Fly Principled Speculation for FSM ParallelizationACM SIGARCH Computer Architecture News10.1145/2786763.269436943:1(619-630)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694369
Zhao ZShen X(2015)On-the-Fly Principled Speculation for FSM ParallelizationACM SIGPLAN Notices10.1145/2775054.269436950:4(619-630)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2775054.2694369
Show More Cited By

On parsing arithmetic expressions in a multiprocessing environment
1. Theory of computation
  1. Formal languages and automata theory

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 expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Acta Informatica Volume 17, Issue 3

August 1982

117 pages

ISSN:0001-5903

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 1982

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ge CLi YEilebrecht EChandramouli BKossmann DBoncz PManegold SAilamaki ADeshpande AKraska T(2019)Speculative Distributed CSV Data Parsing for Big Data AnalyticsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319898(883-899)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319898
Zhao ZShen X(2015)On-the-Fly Principled Speculation for FSM ParallelizationACM SIGARCH Computer Architecture News10.1145/2786763.269436943:1(619-630)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694369
Zhao ZShen X(2015)On-the-Fly Principled Speculation for FSM ParallelizationACM SIGPLAN Notices10.1145/2775054.269436950:4(619-630)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2775054.2694369
Zhao ZShen XOzturk OEbcioglu KDwarkadas S(2015)On-the-Fly Principled Speculation for FSM ParallelizationProceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/2694344.2694369(619-630)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2694344.2694369
Zhao ZWu BShen X(2014)Challenging the "embarrassingly sequential"ACM SIGARCH Computer Architecture News10.1145/2654822.254198942:1(543-558)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2654822.2541989
Zhao ZWu BShen X(2014)Challenging the "embarrassingly sequential"ACM SIGPLAN Notices10.1145/2644865.254198949:4(543-558)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2644865.2541989
Zhao ZWu BShen XBalasubramonian RDavis AAdve S(2014)Challenging the "embarrassingly sequential"Proceedings of the 19th international conference on Architectural support for programming languages and operating systems10.1145/2541940.2541989(543-558)Online publication date: 24-Feb-2014
https://dl.acm.org/doi/10.1145/2541940.2541989
Zhao ZBebenita MHerman DSun JShen X(2013)HParACM Transactions on Architecture and Code Optimization10.1145/2541228.255530110:4(1-25)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2541228.2555301
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
Duong BGeorge K(1986)Dividing patterns into deterministic regionsProceedings of the 1986 workshop on Applied computing10.1145/800239.807174(53-57)Online publication date: 10-Oct-1986
https://dl.acm.org/doi/10.1145/800239.807174
Show More Cited By

View Options

View options

Login options

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

Abstract

References

Cited By

Recommendations

LLLR parsing

Parsing minimalist languages

Parsing expression grammars: a recognition-based syntactic foundation

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations