Instance-Specific Solutions For Accelerating The Cky Parsing Of Large Context-Free Grammars
Instance-Specific Solutions For Accelerating The Cky Parsing Of Large Context-Free Grammars
复制标题
用于加速大型上下文无关语法的 Cky 解析的特定于实例的解决方案
DOI：
10.1142/s0129054104002492
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
J. Bordim;O. Ibarra;Yasuaki Ito;K. Nakano
本文的主要贡献是基于FPGA的实例特定硬件的实现，该硬件可以加速CKY（Cocke-Kasami-Younger）对无上下文的语法进行解析。给定无上下文的语法G和一个字符串X，CKY解析决定G der x。我们开发了一个硬件生成器，该硬件生成器可创建一个Verilog HDL源，以使用FPGA供应商提供的设计软件将生成的源嵌入FPGA中。结果表明，与传统软件解决方案相比，我们特定实例的硬件解决方案达到了高达3,700的惊人速度。
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.
影响因子：
14.9
作者：
SAKAKIBARA, Y;BROWN, M;HAUSSLER, D
通讯作者：
HAUSSLER, D