dr

README

dr

ERE derivative-based regex engine

This is based on the derivative-based membership checking from CS 598 GR, aka Runtime Verification.

The implementation is relatively trivial (it's quite literally the same as the paper), so it might as well be public. The parser was the time consuming part.

"dr" comes from dR, i.e. derivative of R, because I think I'm funny.

The syntax uses ! for complement, * for the Kleene star, + for union, and . for any character.

The characters +*!\(). can be escaped by prefixing with a \.

The output of the test program in cmd/drtest is:

asdfg => asdfg
aaa+bbb => (aaa)+(bbb)
!(a)b*(cd)*e+f => (!(a)(b)*(cd)*e)+(f)
\+\++\*(\!\\) => (\+\+)+(\*\!\\)

matching against ab(c)*
: false
a: false
ab: true
abc: true
abccccc: true

Which shows the input and output after parsing and generating the regex, as well as various examples of matching a common expression.

In addition to those rules described in class, I've also added a rule for . (any), which accepts any single character, although, it could have been represented by (!a+a).

Documentation

Index

• func Match(r Regex, s string) bool
• type Regex
  • func MustParse(s string) Regex
  • func NewAny() Regex
  • func NewChar(r rune) Regex
  • func NewComp(r Regex) Regex
  • func NewConcat(l, r Regex) Regex
  • func NewEmpty() Regex
  • func NewEpsilon() Regex
  • func NewKleene(r Regex) Regex
  • func NewUnion(l, r Regex) Regex
  • func Parse(s string) (Regex, error)

Functions

func Match

func Match(r Regex, s string) bool

Match returns true if the string matches the regex. This is sugar for calling Derivative on the regex repeatedly, then checking if the current state accepts epsilon.

Types

type Regex

type Regex interface {
	fmt.Stringer
	Derivative(rune) Regex
	Accepting() bool
}

Regex represents the nodes of the regex, which support printing a string, as well as transformation under derivative.

func MustParse

func MustParse(s string) Regex

func NewAny

func NewAny() Regex

NewAny creates a regex that accepts any single character.

func NewChar

func NewChar(r rune) Regex

NewChar creates a regex that only accepts the given character.

func NewComp

func NewComp(r Regex) Regex

NewComp creates a regex that accepts the complement of a regex.

func NewConcat

func NewConcat(l, r Regex) Regex

NewConcat creates a regex that accepts the concatenation of two regexes, taking into consideration the simplifiying equations.

func NewEmpty

func NewEmpty() Regex

NewEmpty creates a regex that accepts nothing.

func NewEpsilon

func NewEpsilon() Regex

NewEpsilon creates a regex that only accepts the empty string.

func NewKleene

func NewKleene(r Regex) Regex

NewKleene creates a regex that accepts the Kleene star of a regex.

func NewUnion

func NewUnion(l, r Regex) Regex

NewUnion creates a regex that accepts the union of two regexes, taking into consideration the simplifiying equations.

func Parse

func Parse(s string) (Regex, error)