Practical regular expression derivatives

Background

Regular expression derivatives

Asides...

Teh formal stuff

Java

This code is strongly based on Matt Might's Scala code.

The code is defined in terms of the regular language which the given expression operator accepts, for example a single character or the union of two other regular languages. The conversion of a regular expression into the corresponding description of the regular language should be fairly obvious, after you have seen the code.

RegularLanguage

A RegularLanguage, the superclass of the individual operators, requires four methods and has a few helpful operations.

public abstract class RegularLanguage
{

  abstract public RegularLanguage derive(char c);
  abstract public boolean acceptsEmptyString();
  abstract public boolean rejectsAll();
  abstract public boolean isEmptyString();
  
  public boolean mustBeSubsumedBy(RegularLanguage other) { return false; }
  
  public RegularLanguage oneOrMore()
  {
    if (this.isEmptyString()) { return this; }
    if (this.rejectsAll()) { return EmptySet.instance; }
    return Catenation.concatenate(this, Star.star(this));
  }
  
  public RegularLanguage option()
  {
    if (this.isEmptyString()) { return this; }
    if (this.rejectsAll()) { return Epsilon.instance; }
    return Union.union(Epsilon.instance, this);
  }
}

derive() implements D_c; acceptsEmptyString() implements δ. rejectsAll() and isEmptyString() are tests, effectively for ∅ and ε.

mustBeSubsumedBy() is a small, but important, optimization; it tests whether this expression is a sub-language of the other expression. It is hard to compute and as a result by default false.

oneOrMore() and option() are basic extensions to the regular expression language so far; oneOrMore() is equivalent to the '+' operation and option() is the '?' operation. EmptySet, Catenation, Star, Union, and Epsilon are described below.

EmptySet

The EmptySet is the RegularLanguage that contains no strings; It does not accept the empty string, the derivative with respect to anything is also the EmptySet, and it rejects any input.

  public static class EmptySet extends RegularLanguage
  {
    public static final EmptySet instance = new EmptySet();

    @Override public RegularLanguage derive(char c) { return this; }
    @Override public boolean acceptsEmptyString() { return false; }
    @Override public boolean rejectsAll() { return true; }
    @Override public boolean isEmptyString() { return false; }

    private EmptySet() { }
  }

Epsilon

Epsilon represents ε, the language consisting of the empty string. The derivative is the EmptySet, since any character is not the empty string.

  public static class Epsilon extends RegularLanguage
  {
    public static final Epsilon instance = new Epsilon();

    @Override public RegularLanguage derive(char c) { return EmptySet.instance; }
    @Override public boolean acceptsEmptyString() { return true; }
    @Override public boolean rejectsAll() { return false; }
    @Override public boolean isEmptyString() { return true; }
    
    private Epsilon() { }
  }

Character

Character is the language consisting of the string with the one, given character. Unlike the above classes, Character cannot be a singleton, although you could optimize this a bit by caching instances.

The derivative is Epsilon, if the character matches, or EmptySet, if it does not. Character does not accept the empty string.

Character is one case where mustBeSubsumedBy() is possible to compute; it is true if the other language is also this same character or is AnyChar.

  public static class Character extends RegularLanguage
  {
    public final char ch;
    
    public Character(char ch) { this.ch = ch; }

    @Override public RegularLanguage derive(char c) { return (this.ch == c) ? Epsilon.instance : EmptySet.instance; }
    @Override public boolean acceptsEmptyString() { return false; }
    @Override public boolean rejectsAll() { return false; }
    @Override public boolean isEmptyString() { return false; }
    
    @Override public boolean mustBeSubsumedBy(RegularLanguage other)
    {
      return ((other instanceof Character && this.ch == ((Character) other).ch) || (other instanceof AnyChar));
    }
  }

AnyChar, CharSet, and NotCharSet

AnyChar is equivalent to the regular expression '.', CharSet implements '[...]', equivalent to the union of a finite set of Characters. NotCharSet is the negation of a CharSet. I'm not going to present the code because they are very similar to Character.

Catenation

This is where things start to get interesting. In fact, it is the most complex of the classes.

A Catenation is built from a prefix expression and a suffix expression. As an optimization, the factory method concatenate() checks whether either is the empty string or if either rejects all input, in which cases the result is simpler than the inputs.

The derivative is,

• The concatenation of the derivative of the prefix and the suffix, if the prefix does not accept the empty string, or
• The union of the above and the derivative of the suffix, if the prefix accepts the empty string.

A Catenation accepts the empty string if both the prefix and the suffix accept the empty string. It rejects all input if either the prefix or the suffix reject all input. It is the empty string if both the prefix and the suffix are the empty string, although this and the rejects all input case should have been handled by the concatenate() factory.

  public static class Catenation extends RegularLanguage
  {
    public final RegularLanguage prefix;
    public final RegularLanguage suffix;
    
    public static RegularLanguage concatenate(RegularLanguage prefix, RegularLanguage suffix)
    {
      if (prefix.isEmptyString()) { return suffix; }
      if (suffix.isEmptyString()) { return prefix; }
      if (prefix.rejectsAll() || suffix.rejectsAll()) { return EmptySet.instance; }
      return new Catenation(prefix, suffix);
    }
    
    private Catenation(RegularLanguage prefix, RegularLanguage suffix) { this.prefix = prefix; this.suffix = suffix; }
    
    @Override
    public RegularLanguage derive(char c)
    {
      final RegularLanguage simple = concatenate(prefix.derive(c), suffix);
      return prefix.acceptsEmptyString() ? Union.union(simple, suffix.derive(c)) : simple;
    }

    @Override public boolean acceptsEmptyString() { return prefix.acceptsEmptyString() && suffix.acceptsEmptyString(); }
    @Override public boolean rejectsAll() { return prefix.rejectsAll() || suffix.rejectsAll(); }
    @Override public boolean isEmptyString() { return prefix.isEmptyString() && suffix.isEmptyString(); }
  }

Union

The Union has left and right subexpressions. The union() factory method simplifies the resulting expression if the left or right subexpressions reject all input or must be subsumed by one another.

The derivative of a Union is a Union of the derivatives of the components and a Union accepts the empty string if either of the components accepts the empty string.

  public static class Union extends RegularLanguage
  {
    public final RegularLanguage left;
    public final RegularLanguage right;
    
    public static RegularLanguage union(RegularLanguage left, RegularLanguage right)
    {
      if (left.rejectsAll() || left.mustBeSubsumedBy(right)) { return right; }
      if (right.rejectsAll() || right.mustBeSubsumedBy(left)) { return left; }
      return new Union(left,right);
    }
    
    private Union(RegularLanguage left, RegularLanguage right) { this.left = left; this.right = right; }
    
    @Override public RegularLanguage derive(char c) { return Union.union(left.derive(c), right.derive(c)); }
    @Override public boolean acceptsEmptyString() { return left.acceptsEmptyString() || right.acceptsEmptyString(); }
    @Override public boolean rejectsAll() { return left.rejectsAll() && right.rejectsAll(); }
    @Override public boolean isEmptyString() { return left.isEmptyString() && right.isEmptyString(); }
  }

Star

Star implements the Kleene star; it has a base language and the factory method simplifies the result if the base is the empty string or rejects all input. The derivative is the concatenation of the derivative of the base language and this original Star instance. Star accepts the empty string, which would be zero repetitions of the base language.

  public static class Star extends RegularLanguage
  {
    public final RegularLanguage language;
    
    public static RegularLanguage star(RegularLanguage l)
    {
      if (l.isEmptyString()) { return l; }
      if (l.rejectsAll()) { return Epsilon.instance; }
      return new Star(l);
    }
    
    private Star(RegularLanguage language) { this.language = language; }
    
    @Override public RegularLanguage derive(char c) { return Catenation.concatenate(language.derive(c), this); }
    @Override public boolean acceptsEmptyString() { return true; }
    @Override public boolean rejectsAll() { return false; }
    @Override public boolean isEmptyString() { return language.isEmptyString(); }
  }

Conclusion

The code for this engine is a little over 300 lines, including some comments and code that I haven't presented. That is about the same size as Matt Might's Scala version. A quick test showed a moderately complex match of /usr/share/dict/words took 180-200ms, which is roughly an order of magnitude slower than wc.

How could I use it to implement an open scanner for TCP connections? The state of the match is the current RegularLanguage, created by deriving from the prior RegularLanguage based on the last input character. By exposing that RegularLanguage, or an interface to it, I can throw each incoming character at the regex engine, handling matches as they occur, and then go off to do something else when I reach the end of a segment and need to wait for further input.

At the moment, I am not going to make the code available; there is not much to it as it is. Instead, my next project is to look at the context free parsers that Might, et al., describe, created using grammar derivatives.

Comments

You might enjoy looking at how we compile a simple implementation of regular expression derivatives using partial evaluation, and get super-fast regular expression matchers as a result.

William Cook

Copyright © 2007-2017 Tommy M. McGuire