title: Efficient (basic) regular expression implementation for streaming data
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>Requirements:</p>
  
  <ul>
  <li><p>The library should <em>not</em> 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.</p></li>
  <li><p>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.</p></li>
  <li><p>Language: usable from C/C++</p></li>
  </ul>
  
  <p>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).</p>
  
  <p>I have found:</p>
  
  <p><a href="https://stackoverflow.com/questions/1962220/apply-a-regex-on-stream">Apply a Regex on Stream?</a></p>
  
  <p><a href="https://stackoverflow.com/questions/716927/applying-a-regular-expression-to-a-java-i-o-stream">Applying a regular expression to a Java I/O Stream</a> </p>
  
  <p><a href="http://www.codeguru.com/csharp/csharp/cs_data/searching/article.php/c14689/Building-a-Regular-Expression-Stream-Search-with-the-NET-Framework.htm" rel="nofollow noreferrer">Code Guru - Building a Regular Expression Stream Search with the .NET Framework</a></p>
  
  <p>But all of these attempt to convert the stream to a string first and then use a stock regular expression library.</p>
  
  <p>Another thought I had was to modify the <a href="http://code.google.com/p/re2/" rel="nofollow noreferrer">RE2 library</a>, but <a href="https://groups.google.com/d/msg/re2-dev/6M-nj-MFHMY/B1u8BwN44LgJ" rel="nofollow noreferrer">according to the author</a> it is architected around the assumption that the entire string is in memory at the same time.</p>
  
  <p>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!</p>