×

Systems and methods for processing regular expressions

  • US 8,386,530 B2
  • Filed: 07/27/2011
  • Issued: 02/26/2013
  • Est. Priority Date: 06/05/2006
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of processing a regular expression, the method comprising:

  • receiving the regular expression comprising a range asserting expression;

    determining a first subexpression and a second subexpression of a range asserting expression;

    storing information indicating a relationship between the first subexpression and the second subexpression as indicated in the range asserting expression;

    generating a deterministic finite-state automata (DFA) corresponding to the regular expression, the generated DFA comprising terminal states corresponding to locations of each of the first and the second subexpressions in a received data stream;

    in response to reaching a first terminal state indicating the location of the first subexpression;

    applying the DFA to the received data stream in order to generate information regarding two or more subexpressions in the received data stream; and

    processing information regarding a relationship between the two or more subexpressions and the information regarding the two or more subexpressions in the received data file stream in order to determine if the received data stream satisfies the regular expression by;

    in response to reaching a second terminal state indicating the location of the second subexpression;

    storing the location of the first subexpressionstoring the location of the second subexpression; and

    evaluating the relationship information, wherein the evaluating further comprises determining if the relationship between the first and second subexpression is satisfied by the location of the first subexpression and the location of the second subexpression.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×