Fast hardware processing of regular expressions containing sub-expressions

A method for processing regular expression containing one or more sub-expressions, comprising:

• storing information regarding one or more regular expressions, each containing one or more sub-expressions, including converting a regular expression to tables stored in memory, wherein there is one table for each regular expression containing one or more sub-expressions, and wherein such tables each comprise a quantity of elements equal to at least twice the maximum number of sub-expressions in the rule, so that the start and end of each sub-expression can be separately stored in a table;
• comparing data to the stored information regarding expressions in only a single pass through the data;
• determining from the comparison, for any stored expression, the location within the data of the beginning and end of each sub-expression, and the end of the regular expression, wherein the determining step includes saving upon the start or end of a sub-expression, an identification of a rule with which the sub-expression is associated, an identification of the sub-expression within the rule, and an identification of whether it is the start or end of a sub-expression, and wherein the saving comprises means for storing the byte offset of the data which comprises the start or end of a sub-expression in an addressable memory;
• identifying from such determination the presence within the data of any one or more stored regular expressions containing one or more sub-expressions;
• and
• keeping track of the next location within the addressable memory for storing an identification.

A system for processing regular expressing containing one or more sub-expressions using a deterministic finite state automation comprising:

• means for storing information regarding one or more regular expressions, each containing one or more sub-expressions;
• means for comparing data to the stored information regarding the regular expressions and the sub-expressions in only a single pass through the data;
• means for determining from the comparison the location within the data of the beginning and end of each sub-expression, and the end of the regular expression storing location;
• and
• means for identifying from such determination the presence within the data of any one or more stored regular expressions containing one or more sub-expressions.