Reconfigurable context-free grammar based data processing hardware with error recovery
James Moscola, Young H. Cho, John W. Lockwood · 2006
This paper presents an architecture for context-free grammar (CFG) based data processing hardware for re-configurable devices. Our system leverages on CFGs to tokenize and parse data streams into a sequence of words with corresponding semantics. Such a tok-enizing and parsing engine is sufficient for processing grammatically correct input data. However, most pat-tern recognition applications must consider data sets that do not always conform to the predefined grammar. Therefore, we augment our system to detect and re-cover from grammatical errors while extracting useful information. Unlike the table look up method used in traditional CFG parsers, we map the structure of the grammar rules directly onto the Field Programmable Gate Array (FPGA). Since every part of the grammar is mapped onto independent logic, the resulting design is an efficient parallel data processing engine. To eval-uate our design, we implement several XML parsers in an FPGA. Our XML parsers are able to process the full content of the packets up to 3.59 Gbps on Xilinx Virtex 4 devices. 1