Regular expressions allow us to describe patterns in text. They are very useful and show up all over the place in programming, but matching regular expressions can be difficult. One well-known technique for matching regular expressions is converting the regular expression to a finite state machine. This is pretty elegant, but can get complicated and messy.

An alternative technique, which is the subject of this blog post, involves something called a Brzozowski derivative. This technique can be used to compute the derivative of a generalized regular expression.

1  The Derivative of a Regular Expression?

We take the derivative of a regular expression with respect to a string by repeatedly taking the derivative of the regular expression with respect to each character.

That’s the idea. If the derivative of the regular expression with respect to the target string is a regular expression which matches the empty string, we have a match.

We will represent regular expressions with racket datums:

• character matches the character character

• 'empty matches the empty string

• 'null doesn’t match any strings

• (list 'or a b) matches strings that match a or b

• (list 'and a b) matches strings that match a and b. This is a feature that most regular expression implementations do not support.

• (list 'not a) matches strings that do not match a. This is a feature that most regular expression implementations do not support.

• (list 'seq a b) matches strings that can be partitioned into a substring that matches a followed by a substring that matches b. This is the concatenation of two regular expressions.

• (list '* a) matches strings that match zero or more concatenations of a with itself

First, we must define a helper function that determines whether a regular expression matches the empty string. If it does, we return 'empty. Otherwise, we return 'null.

Now, we’re ready to implement the derivative:

For the character case, we check if the target character matches the regular expression character. If it does, then the only thing that can follow the target character in a string is the empty string, so that’s the derivative. If it doesn’t, there are no strings that can follow the character, so we return null. Remember, the result of a derivative is a regular expression that matches strings that, when appended after the target character, match the original regular expression. If the derivative is 'null, then the match failed because there are no strings that can follow the character and produce a match. In other words, the target character is not the first character of any matches of the regular expression.

For the 'empty expression, we return 'null because the empty expression does not match a character. The empty expression only matches the empty string.

For the 'null expression, we return 'null because the null expression does not match any strings.

For star expressions, we concatenate the sub-expression’s derivative with the star expression. Concatenating the original star expression gives us the repetition behavior.

For sequences, there are two cases. The intuitive case is the first one, `(seq ,(d/dc a c) ,b). This is the derivative of the first regular expression concatenated with the second expression. However, if the first regular expression matches the empty string, the derivative of the sequence could also be (d/dc b c). We implement this using our v helper and properties of regular expressions.

If (v a) returns 'empty, the second case becomes `(seq empty ,(d/dc b c)), which is equivalent to (d/dc b c). If (v a) is 'null, we get `(seq null ,(d/dc b c)), which is equivalent to 'null. So we only ever "try" the derivative of b when a matches the empty string.

We want the derivative to match all strings matched by either of these two cases, so we use 'or.

The other cases are just straightforward recursive cases, threading the derivative through the sub-expressions.

The first two examples show the simple character cases. The following examples seem complicated, but if we use the properties of regular expressions, we can simplify the results. For example, (d/dc `(seq #\a #\b)  #\a) evaluates to '(or (seq empty #\b) (seq null null)), which is equivalent to #\b. Try to simplify the other outputs and make sure the results are what you expect.

1.1  Detour: A Simplifier

If you simplified those by hand, you’d probably agree that this is a computer’s job. So let’s make a function to do it for us! This will make it easier to analyze our derivatives and it’s a fun exercise.

We’ll start by writing the rewrite rules:

These are some simple rewrite rules for simplifying regular expressions. For example, the rule `(and null ,b)  ~> 'null makes sense because a string has to match both 'null and some regular expression b to match `(and null ,b), but it won’t match 'null, so the whole thing is equivalent to 'null. Make sure all of the rules make sense to you.

Now we’ll implement the recursive part:

simplify-step* repeatedly applies simplify-step until the result is unchanged. This is guaranteed to terminate because our rewrite rules either produce a sub-expression, an atomic expression, or the unchanged input expression. Atomic expressions are returned unchanged, so eventually, we’ll either produce an expression with no rewrite rule (gets returned unchanged) or an atomic and then terminate.

simplify simplifies the expression bottom-up, simplifying sub-expressions first and then repeatedly applying our rewrite rules on the input expression with simplified children.

This is by no means an exhaustive, rigorous simplifier, but it gets the job done for our purposes.

Finally, we can simplify those derivatives:

Beautiful!

2  Putting it All Together

Now that we can differentiate a regular expression with respect to a character, we can differentiate with respect to a string by sequencing character derivatives.

With this, we can finally determine if a string matches a regular expression:

This method is cool and simple, but does not generalize well to features like capture groups. Regardless, I think it is a very interesting idea and a fun exercise.