A modular NFA architecture for regular expression matching
Hao Henry Wang, Shi Pu, Gabriel Knezek, Jyh‐Charn Liu · 2010
We propose a non-deterministic finite automata (NFA) based architecture for regexp scanners on FPGA, called CES: the Character Class with Constraint Repetition (CCR) based regExp Scanner. CES is designed to realize a new MIN-MAX counting algorithm, which can solve both the character class ambiguity problem and the overlapped matching problem. CES also supports non-regular Perl grammars such as zero-width pattern and back-reference. We propose a CCR-syntax tree and its parsing scheme to map a Perl or POSIX regexp rule to a CES topology. The interconnection patterns, and operational parameters of CCR modules (CCRM), which are the building blocks of CES, can be easily configured by regular memory writes when regexp rules change, without re-synthesis of low-level logic.