4
$\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 Pearl regexps). Why is this the case? Is the technique I mentioned too slow? Is it missing functionalities? Does anybody know what is the complexity of regular expression matching using derivatives?

|cite|improve this question
$\endgroup$
  • $\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
3
$\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.

|cite|improve this answer
$\endgroup$
  • $\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
  • $\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).

|cite|improve this answer
$\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.