The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] CKY parsing(1hit)

1-1hit
  • Accelerating the CKY Parsing Using FPGAs

    Jacir L. BORDIM  Yasuaki ITO  Koji NAKANO  

     
    PAPER

      Vol:
    E86-D No:5
      Page(s):
    803-810

    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.