REGULAR EXPRESSION MATCHING WITH BACK-REFERENCES USING BACKTRACKING

摘要

A device for matching, in input data, a regular expression with back-references, represented by a finite-state machine (FSM). The device comprises a plurality of parallel processing elements (PPEs), an interconnection network for interconnecting the PPEs with each other, and a memory for receiving and storing input data. The PPEs process the input data stored in the memory, based on backtracking to process the back-references, and implement FA next state logic to generate new active FA configurations or mark themselves as available to receive active FA configurations. The interconnection network retrieves active FA configurations from the PPEs and allocates the active FA configurations to available PPEs. The PPEs are configured to match a regular expression in the input data.

主权项

1. A device for matching a regular expression in input data, wherein the regular expression includes one or more back-references and is represented by a finite-state machine (FSM), the device comprising:
a plurality of parallel processing elements (PPEs); an interconnection network for interconnecting the plurality of PPEs with each other; and a memory for receiving and storing input data; wherein the PPEs operate to process the input data stored in the memory, based on backtracking to process the back-references, and to implement FA next state logic to generate new active FA configurations or to mark themselves as available to receive active FA configurations; wherein the interconnection network operates to retrieve active FA configurations from the PPEs, and to allocate the active FA configurations to available PPEs of the plurality of PPEs; and wherein the plurality of PPEs is configured to match a regular expression in the input data.