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 system for matching input symbols from an input stream against CCLs in an NFA cell array, comprising:
a CCL comparator enabled to accept symbols from the input stream; and a spin sequence monitor and counter enabled to accept signals from the CCL comparator; wherein:
the NFA cell array is configured with a predetermined set of information,the CCL comparator performs CCL comparisons for a spinner and a base sequence of a complex state; andthe spin sequence monitor and counter monitors spinner comparisons, maintains a spin count for comparison to a minimum spin count and maximum spin count, and receives an in-transition signal which enables spin count.