Why Sponsor Oils? | blog | oilshell.org

Three Great Videos About Regex Derivatives

I usually don't post videos here, but the first one in this series got a positive reaction on Reddit, and there are two more.

I've been interested in implementing simple and efficient regex matching with the derivatives technique for a couple years. But I haven't had time to play with code that implements it, or read the original papers more carefully.

These videos helped me understand the technique despite the fact I haven't done math in over a decade. Others apparently felt the same way. The explanation is simple but not dumbed down.

Context

For context, see the two July 2020 posts tagged #eggex, particularly this part of the second post, on derivatives.

Summary: A 2009 paper revived this regex matching technique. There have been many implementations since, though no popular ones.

How Does This Relate to Shell?

• As mentioned in those posts, a glob like [a-c]*.py is essentially a limited form of regex.
  • I noted in this Hacker News comment that the obscure "extended glob" feature of bash gives globs the power of regular expressions, by adding repetition and alternation.
• It would be nice if egg expressions could be compiled to a full DFA in C, as we do in Oil's lexer via re2c.
  • This seems doable, and the author of an F# compiler toolkit relays valuable experience at the bottom of the thread. I'd like to do the same thing without the .NET runtime, depending only on code in Oil.
• It would be nice if egg expressions weren't limited to the features of the pattern matching engine in libc. Non-greedy capturing like foo.*?bar would be nice, although capturing and matching are two different problems.

EasyTheory Videos

Derivative of a Regex?! (Brzozowski Derivative)

This video explains what a derivative is using the recursive definition of regular expressions.

Example

This one walks through an example of a regex and its derivative.

Regex to DFA Directly Using Brzozowski Derivatives (No NFA)

This one shows how to directly convert a regular expression to a DFA with derivatives. This is interesting because DFAs can be executed efficiently. See the Reddit thread for more color on this.

Why Call This Operation a Derivative?

I don't know, and the videos don't explain it! I assume there is some connection between algebra and calculus.

The Reddit thread has some speculation on this. Leave a comment if you have ideas.

I recently explained that languages are sets, not algorithms. And MathOverflow says that derivatives can be expressed in set theory. But I don't know if that's a useful way to think about it.

More Info

• These videos are part of the EasyTheory channel, which started 9 months ago, and has many videos that go deeply into the theory of computation.
  • Caveat: this is pure theory, and I'm mainly interested in engineering consequences, like compiling with fewer lines of code and executing efficiently. Posts tagged #computer-science explain other such connections.
• Recent posts tagged #eggex:
  • Comments on Eggex and Regular Languages (July 2020)
  • Regular Languages, Part 2: Ideas and Questions (July 2020). This post contains the section with many links about regex derivatives, also linked above.

Ad: I'm looking for help with Oil, which is written in Python, shell, and C++. See our README.md.