Abstract
The generation of an LR parser consists of constructing a parse table, with one row per state (in a push-down automaton), and one column per terminal symbol. Traditionally, this is carried out row by row, with the computation of one row depending (potentially) on all the others. We present a technique for carrying out the lookahead computation of SLR (1) and LALR (1) parsers in a completely parallel fashion. Our technique performs the computation by column, rather than by row. We show that the computation is totally independent for each column, making it ideal for parallelization. The speedup factor of the technique is min (N, T), whereN is the number of processors andT is the number of terminal symbols in the user's grammar.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. DeRemer, Practical translators for LR(k) languages, Ph.D. Thesis, Department of Electrical Engineering M.I.T., Cambridge, Massachusetts (1969).
F. DeRemer, Simple LR(k) grammars,CACM 14(7):453–460 (July 1971).
T. J. Anderson, J. Eve, and J. J. Horning, Efficient LR (1) parsers,Acta Informatica 2(1):12–39 (1973).
F. DeRemer and T. Pennello, Efficient computation of LALR (1) look-ahead sets,ACM TOPLAS 4(4):615–649 (1982).
B. B. Kristensen and O. L. Madsen, Methods for computing LALR (k) lookahead,ACM TOPLAS 3(1):60–82 (1981).
W. R. LaLonde, An efficient LALR parser generator, Technical Report 2, Computer Systems Research Group, University of Toronto (1971).
D. Pager, A practical general method for constructing LR(k) parsers,Acta Informatica 7:249–268 (1977).
J. C. H. Park, K. M. Choe, and C. H. Chang, A new analysis of LALR formalisms,ACM TOPLAS 7(1):159–175 (1985).
A. V. Babichev, Some theoretical aspects of parallel parsing,Cybernetics 18(2):189–195 (March–April 1982).
J. Baer and C. Ellis, Model, design, and evaluation of a compiler for a parallel processing environment,IEEE Transactions on Software Engineering,SE-3(6):394–405 (November 1977).
J. Cohen, T. Hickey, and J. Katsoff, Upper bounds for speedup in parallel parsing,JACM 29:408–428 (1982).
M. K. Donegan and S. Katzke, Lexical analysis and parsing techniques for a vector machine,SIGPLAN Notices 10(3):138–145 (March 1975).
C. A. Ellis, Parallel compiling techniques,Proc. ACM 26th National Conference, pp. 508–519 (1971).
W. D. Hillis and G. Steele, Data parallel algorithms,CACM 29(12):1170–1183 (December 1986).
C. Fisher, On parsing context-free languages in parallel environments, Ph.D. Dissertation, Computer Science Department, Cornell University, Ithaca, New York (1975).
N. Lincoln, Parallel programming techniques for compilers,SIGPLAN Notices 5(10) (November 1970).
M. Mickunas and R. Schell, Parallel compilation in a multiprocessor environment,Proc. ACM 1978 Annual Conf., pp. 241–246 (1978).
D. B. Skillicorn and D. T. Barnard, Parallel parsing on the connection machine,Information Processing Letters 31:11–119 (1989).
M. Zosel, A parallel approach to compilation,Proc. ACM Symp. on Principles of Programming Languages, pp. 59–70 (October 1978).
S. C. Johnson, YACC-Yet another compiler compiler, Tech. Report CSTR 32, Bell Labs, Murray Hill, New York (1974).
A. Aho, R. Sethi, and J. Ullman, Compilers. Principles, techniques and tools, Addison-Wesley (1986).
C. Fischer and R. J. LeBlanc, Crafting a Compiler, Benjamin Cummings (ed.) (1988).
M. Harrison, An introduction to formal language theory, Addison-Wesley, Reading, Massachusetts (1978).
D. Knuth, Top down syntax analysis,Acta Informatica 1:79–110 (1971).
J. E. Burns,A Formal Model for Message Passing Systems, TR 91, Computer Science Department, Indiana University (May 1980).
R. A. Borodin and J. E. Hopcroft, Routing, merging and sorting on parallel models of computation,Proc. 14th ACM Symp. on the Theory of Computation, pp. 338–344 (1982).
S. Fortune and J. Wyllie, Parallelism in random access machines,Proc. of the 10th ACM Symp. on the Theory of Computing, pp. 114–118, (1978).
L. Goldschlager, A unified approach to models of synchronous parallel machines,Proc. of the 10th ACM Symp. on the Theory of Computing, pp. 89–94 (1978).
D. Barnes, The ILLIAC IV computer,IEEE Trans. on, Comput. C-17:746–757 (1968).
C. Seitz, The cosmic cube,CACM 28(1):22–23 (January 1985).
C. D. Thompson and H. T. Kung, Sorting on a mesh-connected parallel computer,CACM 20(4):263–271 (1977).
R. Cytron, Useful parallelism in a multiprocessing environment,Proc. of the Int. Conf. on Parallel Processing, pp. 450–457 (1985).
D. Knuth, On the translation of languages from left to right,Information and Control 8:607–639 (1965).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bermudez, M.E., Newman-Wolfe, R. & Logothetis, G. Parallel construction of SLR (1) and LALR (1) parsers. Int J Parallel Prog 19, 163–184 (1990). https://doi.org/10.1007/BF01407953
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01407953