ISSN:
1573-7640
Keywords:
Parallel parser generation
;
SLR (1)
;
LALR (1)
;
follow set
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01407953
Permalink
