Parallel construction of SLR (1) and LALR (1) parsers |
| |
Authors: | Manuel E. Bermudez Richard Newman-Wolfe George Logothetis |
| |
Affiliation: | (1) University of Florida, Florida, USA;(2) AT&T Bell Laboratories, USA |
| |
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. |
| |
Keywords: | Parallel parser generation SLR (1) LALR (1) follow set |
本文献已被 SpringerLink 等数据库收录! |
|