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.