A. Koulouris, T. Andronikos, C. Pavlatos, A. Dimopoulos, I. Panagopoulos, and G. Papakonstantinou (Greece)
Signal Processing, Syntactic Pattern Recognition, FPGA.
This paper presents an optimal architecture for hardware
implementation of Context-Free Grammar (CFG) parsers,
which can be used to accelerate the performance of appli
cations where response to real time signal processing is a
crucial aspect, such as Electrocardiogram (ECG) analysis.
Our architecture increases the performance by a factor of
approximately two orders of magnitude compared to the
pure software implementation, depending on the CFG. This
speed up derives mainly from the hardware nature of the
implementation, the innovative combinatorial nature of the
circuit that implements the fundamental operation of the
parsing algorithm and the underlying data representation.
We further propose an automated synthesis tool that, given
the speciﬁcation of an arbitrary CFG and using the afore
mentioned hardware architecture in a template form, gener
ates the HDL (Hardware Design Language) synthesizable
source code of the hardware parser for the given grammar.
The proposed architecture may be used for real time appli
cations, e.g. natural languages interfaces. The generated
source has been simulated for validation, synthesized and
tested on a Xilinx FPGA (Field Programmable Gate Array)