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