For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Accelerating the CKY Parsing Using FPGAs
Jacir L. BORDIM Yasuaki ITO Koji NAKANO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/05/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Reconfigurable Computing)
CKY parsing, FPGAs, reconfigurable architectures, reconfigurable computing,
Full Text: PDF>>
The main contribution of this paper is to present an FPGA-based implementation of an instance-specific hardware which accelerates the CKY (Cocke-Kasami-Younger) parsing for context-free grammars. Given a context-free grammar G and a string x, the CKY parsing determines whether G derives x. We have developed a hardware generator that creates a Verilog HDL source to perform the CKY parsing for any given context-free grammar G. The generated source is embedded in an FPGA using the design software provided by the FPGA vendor. We evaluated the instance-specific hardware, generated by our hardware generator, using a timing analyzer and tested it using the Altera FPGAs. The generated hardware attains a speed-up factor of approximately 750 over the software CKY parsing algorithm.