5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I put a derivatives-based regex engine into production in the TXR language some seven years ago. The source code is kylheku.com/cgit/txr/tree/regex.c. The derivatives back-end is used if the AST of the regex (after some optimizations) still contains complement and intersection operators. Otherwise a NFA graph is built and a NFA simulator is used on it. In developing and debugging the derivative-based engine, I discovered some tricks that aren't in the literature. $\endgroup$ – Kaz Jun 23 '17 at 23:24
  • $\begingroup$ @Kaz is there any chance that you could expand on the "tricks that aren't in the literature" aspect? I'm putting together a derivative-based engine at the moment. $\endgroup$ – kiwidrew Jul 1 '17 at 4:20
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why would a table-driven approach be harder to prove correct? The conversion of regular expression to finite state automaton is a well studied subject with standard algorithms that are proved correct in any textbook. Isn't a table just an implementation of that? $\endgroup$ – Hendrik Jan Jan 21 '16 at 15:28
  • 1
    $\begingroup$ @HendrikJan, I don't recall. I think that the algorithm based on Brzozowski derivatives could be implemented very concisely in a functional language, in a way that follows the definitions closely, whereas a table-driven approach needs more code and more lemmas/invariants/etc. -- not that it can't be done, just that it's a bit more effort during verification. At least, that's my vague recollection -- but I could be wrong. $\endgroup$ – D.W. Jan 21 '16 at 17:07
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Let me point out that it is not true in general that derivatives are slower than DFA-based matchers. This is because by "performance" we should include the cost of compiling the regular expression to a DFA, and sometimes this is simply infeasible, particularly because in practice regular expressions have complex constructs such as counting loops which immediately result in state space blowup. Derivatives are one way of avoiding that complexity because typically the derivative can be computed efficiently even though the space of all possible states is too expensive to compute statically. $\endgroup$ – 6005 Aug 22 '20 at 22:07
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.