PROGRAMMABLE REGULAR EXPRESSION AND CONTEXT FREE GRAMMAR MATCHER
First Claim
1. A computer program product, comprising:
- a computer readable storage device to store a computer readable program, wherein the computer readable program, when executed by a processor within a computer, causes the computer to perform operations for expression matching, the operations comprising;
comparing data from an input stream to a word on a programmable ternary content addressable memory (TCAM) matcher to determine a state-to-state transition in an expression matcher from a comparison result;
identifying a next state in the expression matcher based on the comparison result using a programmable logic connected to an output of the programmable TCAM matcher;
updating the expression matcher to the next state; and
storing a sequence of required state transitions for the expression matcher in a collection data structure coupled to the TCAM matcher and the programmable logic, wherein the programmable logic determines a next required state transition to be matched from the sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
A regular expression matcher system, including: a deterministic finite state machine (DFSM); a ternary content addressable memory (TCAM) matcher to compare a word stored at the TCAM matcher to an input stream, wherein the word determines a state-to-state transition of the DFSM from a comparison result; a programmable logic connected to an output of the TCAM matcher to identify a next state in the DFSM based on the comparison result; a state register to update a current state of the DFSM to the next state; and a collection data structure coupled to the TCAM matcher and the programmable logic to store a sequence of required state transitions for the DFSM, wherein the programmable logic determines a next required state transition to be matched from the sequence.
-
Citations
20 Claims
-
1. A computer program product, comprising:
a computer readable storage device to store a computer readable program, wherein the computer readable program, when executed by a processor within a computer, causes the computer to perform operations for expression matching, the operations comprising; comparing data from an input stream to a word on a programmable ternary content addressable memory (TCAM) matcher to determine a state-to-state transition in an expression matcher from a comparison result; identifying a next state in the expression matcher based on the comparison result using a programmable logic connected to an output of the programmable TCAM matcher; updating the expression matcher to the next state; and storing a sequence of required state transitions for the expression matcher in a collection data structure coupled to the TCAM matcher and the programmable logic, wherein the programmable logic determines a next required state transition to be matched from the sequence. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
8. A method for regular expression matching, comprising:
-
comparing data from an input stream to a word on a programmable ternary content addressable memory (TCAM) matcher to determine a state-to-state transition in an expression matcher from a comparison result; identifying a next state in the expression matcher based on the comparison result using a programmable logic connected to an output of the programmable TCAM matcher; updating the expression matcher to the next state; and storing a sequence of required state transitions for the expression matcher in a collection data structure coupled to the TCAM matcher and the programmable logic, wherein the programmable logic determines a next required state transition to be matched from the sequence. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A regular expression (regex) matcher system, comprising:
-
an expression matcher; a ternary content addressable memory (TCAM) matcher to compare a word stored on the TCAM matcher to an input stream, wherein the word determines a state-to-state transition of the expression matcher from a comparison result; a programmable logic connected to an output of the TCAM matcher to identify a next state in the expression matcher based on the comparison result; a state register to update a current state of the expression matcher to the next state; and a collection data structure coupled to the TCAM matcher and the programmable logic to store a sequence of required state transitions for the DFSM, wherein the programmable logic determines a next required state transition to be matched from the sequence. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification