International Journal of Foundations of Computer Science · 2004 · 29 citations · 7 references
Context-free GrammarsSyntactic ParsingEngineeringHardware AlgorithmComputer ArchitectureCky ParsingNatural Language ProcessingFpga VendorSyntaxComputational LinguisticsHardware Description LanguageGrammarLanguage StudiesParallel ComputingMachine TranslationComputer EngineeringComputer ScienceGrammar InductionSemantic ParsingFpga DesignShallow ParsingParsingTreebanksHardware AccelerationProgram AnalysisParallel ProgrammingIntermediate RepresentationLinguistics
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.
7
Stochastic context-free grammers for tRNA modeling
Yasubumi Sakakibara, Michael P. Brown, Richard Hughey et al. · Nucleic Acids Research · 1994 · 389 citations · Full text