An FPGA-based syntactic parser for real-life almost unrestricted context-free grammars. (English) Zbl 1001.68840

Ciressan, Cristian; Sanchez, Eduardo; Rajman, Martin; Chappelier, Jean-Cédric

Brebner, Gordon (ed.) et al., Field-programmable logic and applications. 11th international conference, FPL 2001, Belfast, Northern Ireland, GB, August 27-29, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2147, 590-594 (2001).

Summary: This paper presents an FPGA-based implementation of a syntactic parser that can process languages generated by almost unrestricted real-life context-free grammars (CFGs). More precisely, we study the advantages offered by a hardware implementation of a parallel version of an item-based tabular parsing algorithm adapted for word lattice parsing. A description of the parsing algorithm and of the associated hardware design is provided. A method called tiling, that allows a better processor and I/O bandwidth exploitation is introduced. Finally, an evaluation of the design performance on real-life data is given and the measured \(244\) speed-up factor makes our design a promising solution for Natural Language Processing applications, for which parsing speed is an important issue.
For the entire collection see [Zbl 0972.68674].

MSC:

68U99	Computing methodologies and applications
68Q45	Formal languages and automata
68M07	Mathematical problems of computer architecture