Accelerating the CKY Parsing Using FPGAs

Jacir L. BORDIM  Yasuaki ITO  Koji NAKANO  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.5   pp.803-810
Publication Date: 2003/05/01
Online ISSN: 
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>>
Buy this Article

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.