Summary
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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)
Banatre, J.P., Routeau, J.P., Trilling, L.: An event driven compiling technique. In: Communications of the ACM, Vol. 22, N∘ 1 (1979)
Fisher, C.N.: On parsing and compiling arithmetic expressions on vector computers. ACM Trans. Program. Lang. and Syst. 2, 203–224 (1980)
Gonzales, R.C., Thomason, M.G.: Syntactic pattern recognition. Addison Wesley 1978
Good, I.J.: The number of individuals in the cascade process. Proc. Camb. Phil. Soc. 45, 360–363 (1949)
Gries, D.: Compiler construction for digital computers. John Wiley & Sons, New York 1971
Harris, T.E.: The theory of branching processes. Springer, Berlin 1963
Hopcroft, J.E., Ullman, J.D.: Formal languages and their relation to automata. Addison-Wesley 1969
Mickunas, M., Schell, E.: Parallel compilation in a multiprocessor environment. In: Proc. ACM Annu. Conf. 1978, pp. 241–246
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Baccelli, F., Fleury, T. On parsing arithmetic expressions in a multiprocessing environment. Acta Informatica 17, 287–310 (1982). https://doi.org/10.1007/BF00264355
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00264355