Efficient (basic) regular expression implementation for streaming data
- by Brendan Dolan-Gavitt
I'm looking for an implementation of regular expression matching that operates on a stream of data -- i.e., it has an API that allows a user to pass in one character at a time and report when a match is found on the stream of characters seen so far. Only very basic (classic) regular expressions are needed, so a DFA/NFA based implementation seems like it would be well-suited to the problem.
Based on the fact that it's possible to do regular expression matching using a DFA/NFA in a single linear sweep, it seems like a streaming implementation should be possible.
Requirements:
The library should try to wait until the full string has been read before performing the match. The data I have really is streaming; there is no way to know how much data will arrive, it's not possible to seek forward or backward.
Implementing specific stream matching for a couple special cases is not an option, as I don't know in advance what patterns a user might want to look for.
For the curious, my use case is the following: I have a system which intercepts memory writes inside a full system emulator, and I would like to have a way to identify memory writes that match a regular expression (e.g., one could use this to find the point in the system where a URL is written to memory).
I have found (links de-linkified because I don't have enough reputation):
stackoverflow.com/questions/1962220/apply-a-regex-on-stream
stackoverflow.com/questions/716927/applying-a-regular-expression-to-a-java-i-o-stream
www.codeguru.com/csharp/csharp/cs_data/searching/article.php/c14689/Building-a-Regular-Expression-Stream-Search-with-the-NET-Framework.htm
But all of these attempt to convert the stream to a string first and then use a stock regular expression library.
Another thought I had was to modify the RE2 library, but according to the author it is architected around the assumption that the entire string is in memory at the same time.
If nothing's available, then I can start down the unhappy path of reinventing this wheel to fit my own needs, but I'd really rather not if I can avoid it. Any help would be greatly appreciated!
