Efficient (basic) regular expression implementation for streaming data

Question

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 not 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.

• Language: usable from C/C++

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:

Apply a Regex on Stream?

Applying a regular expression to a Java I/O Stream

Code Guru - Building a Regular Expression Stream Search with the .NET Framework

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!

Answer 1

The "answer" to this unfortunately turns out to be that there is no prebuilt library for doing this. Instead I opted for the following compromise: I implemented a simple string matcher (no RE support), which keeps state using a single counter per stream and per search string, which tracks how many characters of the search string have been matched in that stream. It gets incremented with each correct character, and reset to zero when a non-matching character is found. This is fast and doesn't require too much memory overhead.

For more complicated searches, I instead just dump all streams out to disk, and then search through them using traditional tools. It's extremely slow, but luckily most of our use cases can get by with just simple string matching.

Answer 2

I have exactly what you're looking for: https://github.com/agentzh/sregex http://agentzh.org/misc/slides/yapc-na-2013-sregex.pdf‎

And if you know javascript (or want a javascript version), I have an exercise that lets you easily do that using an existing RE implementation: https://github.com/dhruvbird/regexp-js

Answer 3

Intel has released hyperscan library that does exactly what is needed. Here it is a brief overview of it.

Answer 4

Take a look at an old grep implementation like this one from Brian W. Kernighan and Rob Pike. They process the stream of text in a buffer, and apply on simple regex rules, not even BRE.