Complex NFA state matching method that matches input symbols against character classes (CCLs), and compares sequence CCLs in parallel

摘要

Disclosed is a method and system for matching a complex NFA state comprising a spinner followed by a character class sequence which may be represented by the general regular expression form [S] {N,M}[A0][A1] . . . [Ak−1]. An input transition activates the spinner and the spin count increments with successive matches of the spin class [S]. When the spin count is between N and M, sequence matching begins. Several base sequence CCLs are compared in parallel with a corresponding window of input symbols. If all match, a signal enters a delay line until the end of the base sequence. When the signal exits the delay line, extended sequence CCLs are accessed from a table sequentially and compared with successive input symbols. After the final extension CCL matches, an output transition is signaled. For short sequences, unused base sequence CCLs may be configured with look-ahead classes.

主权项

1. A method of matching an NFA (nondeterministic finite automaton) state in at least one cell of an NFA cell array, said state comprising a spinner, said spinner comprising a spin class, followed by a CCL (character class) sequence, said method comprising:
configuring the at least one cell with predetermined information; activating the spinner via an input transition signal to the cell; incrementing a spin count pursuant to successive successful matches of the spin class with input symbols from an input stream; when the spin count ranges from a predetermined minimum to a predetermined maximum, beginning sequence matching; and comparing a predetermined number of the sequence CCLs in parallel with input symbols.