Systems and methods for processing regular expressions
View Patent ↗A method for reducing the size of a DFA associated with a regular expression separates the functions of locating subexpressions within the DFA and determining if the located subexpressions satisfy a regular expression. For example, the functions of (1) locating subexpressions in a range asserting expression and, (2) determining whether the subexpressions satisfy the range of the range asserting expression are partitioned. In one embodiment, a first component may locate the subexpressions in a data stream using one or more DFAs, while a second component determines if the located subexpressions satisfy the range. In this embodiment, because the DFAs are not configured to determine a relationship between subexpressions, such as a range between subexpressions, the size of the resultant DFA may be significantly reduced.
1. A computing device for compiling a regular expression, the regular expression indicating a first subexpression, a second subexpression, and a required relationship between the first subexpression and the second subexpression, the device comprising:
at least one processor: and
software code configured for execution by the at least one processor in order to cause the computing device to:
generate a DFA corresponding to the regular expression, wherein the DFA comprises a first terminal state indicative of locating the first subexpression and a second terminal state indicative of locating the second subexpression; and
define a match criteria indicating a required relationship between the first subexpression and the second subexpression such that first information regarding the first subexpression located in an input data stream, second information regarding the second subexpression located in the input data stream, and the required relationship indicated in the match criteria are usable to determine whether the regular expression is matched in the input data stream, wherein the DFA does not indicate the required relationship between the first subexpression and the second subexpression.
2. The device of claim 1 , wherein the second subexpression comprises the actual text of the first subexpression.
3. The device of claim 2 , wherein the software code is further configured to cause the computing device to initiates recordation of one or more tokens corresponding to candidate second subexpressions.
4. The device of claim 3 , wherein the software code is further configured to cause the computing device to compares information in a token associated with the first subexpression to information in each of the tokens associated with the candidate second subexpressions according to the match criteria, in order to determine if one or more of the candidate second subexpressions matches the actual text of the first subexpression.
5. The device of claim 3 , wherein a post-processing module evaluates the match criteria on the tokens in order to determine if the range asserting expression is matched in the data stream.
6. The device of claim 1 , wherein the required relationship comprises a relationship between locations in the data stream of a first character of the first subexpression and a first character of the second subexpression.
7. The device of claim 1 , wherein the required relationship comprises a relationship between locations in the data stream of a last character of the first subexpression and a last character of the second subexpression.
8. The device of claim 1 , wherein the required relationship comprises a relationship between locations in the data stream of a first character of the first subexpression and a last character of the second subexpression.
9. The device of claim 1 , wherein the required relationship comprises a relationship between locations in the data stream of a first character of the first subexpression and a last character of the second subexpression.
10. The device of claim 1 , wherein the required relationship comprises a range asserting expression including a range.
11. The device of claim 10 , wherein the range is infinite.
12. The device of claim 10 , wherein the range is more than 500 characters.
13. The device of claim 10 , wherein the range is more than 5,000 characters.
14. The device of claim 10 , wherein the range is more than 5,000,000 characters.
15. The device of claim 10 , wherein the range comprises a current character in the input data stream and all characters following the current character in the input data stream.
16. The device of claim 10 , wherein the match criteria indicates that if a distance between the first and second subexpressions is within the range then the range asserting expression is matched in the input data stream.
17. The device of claim 10 , wherein the match criteria indicates that if the second subexpression is located in the input data stream then the range asserting expression is not matched.
18. The device of claim 10 , wherein the match criteria indicates that if the second subexpression is located in the input data stream within the range of the first subexpression then the range asserting expression is not matched.
19. The device of claim 1 wherein the first subexpression is located in the input data stream prior to location of the second subexpression in the input data stream.
20. The device of claim 1 , wherein the second subexpression is located in the input data stream prior to location of the first subexpression in the input data stream.
21. The device of claim 1 , wherein the first information and the second information each include a byte position of a first character of the located subexpression.
22. The device of claim 1 , wherein the first information and the second information each include a character length of the located subexpression.
23. The device of claim 1 , wherein the match criteria defines a minimum and maximum distance between the respective first characters of the first and second subexpression.
24. The device of claim 1 , wherein generating a DFA corresponding to the regular expression comprises generating a NFA corresponding to the regular expression and then generating a DFA corresponding to the NFA.
25. The device of claim 1 , wherein the device is in data communication with a DFA engine configured to apply the DFA to the received data stream.
26. The device of claim 1 , wherein upon reaching the first or second terminal state, a DFA engine initiates recordation of tokens regarding the respective first and second subexpressions.
27. A computerized method of generating state machine data comprising a deterministic finite automata (DFA) and a match criteria, the computerized method comprising:
receiving a regular expression indicating a required relationship between a first subexpression of the regular expression and a second subexpression of the regular expression;
generating a DFA corresponding to the regular expression, wherein the DFA comprises a first terminal state indicative of locating the first subexpression of the regular expression and a second terminal state indicative of locating the second subexpression of the regular expression, wherein the required relationship is not indicated in the DFA;
generating a match criteria indicating the required relationship between the first subexpression and the second subexpression in an input data stream, wherein the match criteria is usable to determine whether the regular expression is matched in the input data stream in response to locating the first subexpression and the second subexpression in the input data stream.