Name
Title | ||
|---|---|---|
Instance-Specific Solutions For Accelerating The Cky Parsing Of Large Context-Free Grammars |
Abstract | ||
|---|---|---|
The main contribution of this paper is an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing of context-free grammars. Given a context-free grammar G and a string X, the CKY parsing determines whether G derives x. We developed a hardware generator that creates a Verilog HDL source to perform the CKY parsing for any fixed context-free grammar G. The generated source is embedded in an FPGA using the design software provided by the FPGA vendor. The results show that our instance-specific hardware solution attains an astonishing speed-up factor of up to 3,700 over traditional software solutions. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1142/S0129054104002492 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
CKY parsing, FPGAs, reconfigurable architectures, reconfigurable computing | Rule-based machine translation,Top-down parsing,Programming language,Context-free grammar,Computer science,Parallel computing,Field-programmable gate array,Software,Verilog,Parsing,Reconfigurable computing | Journal |
Volume | Issue | ISSN |
15 | 2 | 0129-0541 |
Citations | PageRank | References |
20 | 1.12 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacir Luiz Bordim | 1 | 57 | 18.86 |
| Oscar H. Ibarra | 2 | 650 | 101.57 |
| Yasuaki Ito | 3 | 511 | 60.47 |
| Koji Nakano | 4 | 1165 | 118.13 |