Implementing regular expression matching using Brzozowski derivatives

Question

I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. If you take the derivative of a regular expression with respect to a given string and the resulting expression matches the empty string ($\varepsilon$), then the original expression matches the string used in the derivative:

$$ w \text{ matches } e \Leftrightarrow \varepsilon \text{ matches } D_w(e) $$

I did a web search and, as expected, other people had the same idea before. There is an implementation here and another one here. They are short and simple.

Is this used in practice anywhere? I'm not sure, but I believe that most regular expression matchers are implemented using either finite automata or backtracking algorithms (like Perl regular expressions). Why is this the case? Is the technique I mentioned too slow? Is it missing functionalities? Does anybody know what the complexity of regular expression matching using derivatives is?

Answer 1

Yes. This approach has been used before. I've seen it used in a research project, where the goal was to build a regexp matcher that could be formally verified to be correct (with as little effort as possible). This algorithm was implemented in Coq and then proven correct. The nice thing is that it is relatively easy to prove correct. In contrast, a table-driven lexer would be harder to prove correct, because one would have to prove that the table was constructed correctly.

I think that table-driven lexers are often faster in practice. Your scheme essentially computes the transition table on the fly. Table-driven lexers involve pre-computing the transition table, and now you only need to do a few instructions per character read from the input (read one character, do a table lookup based on the current state and just-read character, update the current state). Therefore, their constant factor can be lower.

To be clear, by table-driven lexer, I mean something that converts the regexp to a DFA and then precomputes a table that represents the transition table. This is useful in cases where the regexp is fixed and known at compile time. For many regexps seen in practice, the size of the DFA is not too large and so this leads to a fairly efficient matcher algorithm.

Answer 2

The principal reason is the performance. Such a direct use of derivatives would be slower than any DFA-based matchers because constructing a DFA already corresponds to a pre-computation of derivatives. Besides the original paper of Ken Thompson (Regular expression search algorithm, 1968) states that the algorithm is an fast parallel implementation of Brzozowski derivatives. So the concept of derivatives was there from the very beginning.

In short, by analogy, if DFA construction is the compilation of a regular expression, then matching with derivatives is the interpretation.

For complexity results one can check the paper "Testing Extended Regular Language Membership Incrementally by Rewriting" by Grigore Rosu and Mahesh Viswanathan (2003).

Answer 3

Derivatives do have some important advantages in practice over competing approaches.

Firstly, while matching time per element is typically slower with derivatives than with a DFA, compile time can be completely avoided. This is because derivatives work on regexes syntactically, so they don't need to be converted to any other representation. For example, in cases where NFA to DFA conversion blows up, derivatives avoid the blowup. They dynamically and lazily update the regex as the input string is read in, which may result in finding the match without actually compiling the entire (exponentially large) state space.

This advantage particularly shows up on regexes with complex features, such as counting loops (e.g. .{200} to match a sequence of 200 characters), which are typically allowed in practical regex libraries. Compiling regexes with such features to DFAs is typically very inefficient and can hang on bad examples. Using derivatives, the derivative expressions that result typically remain simple even though the full state space might be exponentially large or worse.

Finally, compared with many implementations of regexes based on backtracking, derivatives do not backtrack and so enjoy linear-time matching. They share this advantage with DFA-based approaches. The desire to avoid expensive backtracking (and hence, potentially hanging on bad regex examples) was the motivation behind Google's RE2 matcher, which is based on DFAs.

Due to these advantages and others, there is interest in using derivatives for practical regex matching, though it may not be mainstream. For an example of a real implementation based on derivatives, see the Symbolic Regex Matcher from Microsoft (Veanes, Saarikivi, Wan, and Xu).