Efficient reconfigurable embedded parsers

This paper presents a highly efficient architecture for the hardware implementation of context-free grammar (CFG) parsers. Its efficiency stems from an innovative combinatorial circuit that implements the fundamental operation of Earley's parsing algorithm in time complexity O(log2|G|)O(log2|G|), where |G||G| is the size of the CFG. Using this hardware architecture in a template form, we have developed an automated synthesis tool that, given the specification of an arbitrary CFG, generates the HDL (Hardware Design Language) synthesizable source code of the hardware parser for the given grammar. The generated source has been simulated for validation, synthesized and tested on a Xilinx FPGA (Field Programmable Gate Array) board. Our method increases the performance by a factor of one to two orders of magnitude, compared to previous hardware implementations, depending on the size of the grammar and the input string length. The speedup, compared to the pure software implementation, varies from two orders of magnitude for toy-scale grammars to six orders of magnitude for large real life grammars. This makes it particularly appealing for applications where (syntactic) pattern recognition response is a crucial aspect.