© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Regular expression matching using associative memory
Gerald Tripp
Technical Report 4-10, School of Computing, University of Kent., Canterbury, Kent. CT2 7NF. UK., October 2010.Abstract
This paper describes a method for the implementation of regular expression matching based on the use of a form of associative (or content addressable) memory. The regular expression matching is performed by converting the regular expression into a Deterministic Finite Automata, but then using associative memory to hold the state transition information. Rather than try to simplify the resulting automata, this approach starts from the point of view of each next state in the automata being arrived at from some particular area of state-input space. We implement our automata by defining a number of orthogonal regions of state-input space, each of which is compared against our current state and input data. The highest priority region that produces a match will identify a corresponding next state for the automata. This work differs from previous work in that the associative memory used performs a full set membership test, and is hence more selective than systems based on Ternary Content Addressable Memory. This report describes work in progress, which to date has produced the rule processing software and outline designs for the hardware.
Download publication 263 kbytes (PDF)Bibtex Record
@techreport{3055,
author = {Gerald Tripp},
title = {Regular expression matching using associative memory},
month = {October},
year = {2010},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2010/3055},
publication_type = {techreport},
submission_id = {29377_1288276523},
institution = {School of Computing, University of Kent.},
type = {Technical Report},
number = {4-10},
address = {Canterbury, Kent. CT2 7NF. UK.},
}