Name
Abstract | ||
|---|---|---|
We propose a fixed size one dimensional VLSI architecture for the parallel parsing of arbitrary context free (CF) grammars, based on Earley's algorithm. The algorithm is transformed into an equivalent double nested loop with loop carried dependencies. We first map the algorithm into a 1D array with unbounded number of cells. The time complexity of this architecture is O(n), which is optimal. We next propose the partitioning into a fixed number of off the shelf processing elements. Two alternative partitioning strategies are presented considering restrictions, not only in the number of the cells, but also in the inner structure of each cell. In the most restricted case, the proposed architecture has time complexity O(n3/p*k), where p is the number of available cells and the elements inside each cell are at most k |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/ICPADS.1998.741168 | ICPADS |
Keywords | Field | DocType |
1d array,time complexity,systolic array,parallel programming,mapping.,fixed size one dimensional vlsi architecture,off the shelf processing elements,parallel architectures,parallel parsing vlsi architecture,earley's algorithm,loop carried dependencies,context-free grammars,partitioning strategies,computational complexity,index terms --- parallel parsing,cf grammars,vlsi,partitioning,program control structures,earley algorithm,arbitrary context free grammars,equivalent double nested loop,indexing terms,context free grammar,natural languages,nested loops,dynamic programming,pattern recognition,context free grammars,concurrent computing,very large scale integration,computer architecture | Rule-based machine translation,Architecture,Context-free grammar,Computer science,Parallel computing,Parsing,Time complexity,Very-large-scale integration,Distributed computing,Computational complexity theory,Nested loop join | Conference |
ISSN | ISBN | Citations |
1521-9097 | 0-8186-8603-0 | 1 |
PageRank | References | Authors |
0.38 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| andreas g koulouris | 1 | 1 | 0.38 |
| nectarios koziris | 2 | 1 | 0.38 |
| theodore andronikos | 3 | 1 | 0.38 |
| george k papakonstantinou | 4 | 1 | 0.38 |
| Panayotis Tsanakas | 5 | 125 | 19.81 |