Skip to content

Instantly share code, notes, and snippets.

@yellowflash
Last active June 27, 2018 12:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yellowflash/0732325a3f7f41893c6a9ab39bde7039 to your computer and use it in GitHub Desktop.
Save yellowflash/0732325a3f7f41893c6a9ab39bde7039 to your computer and use it in GitHub Desktop.
A derivative based regex matching
class Regex {
constructor(matchesEmpty) {
this.matchesEmpty = matchesEmpty;
}
derivativeBy(ch) {
throw "Not implemented";
}
matches(str) {
return str.length > 0 ? this.derivativeBy(str[0]).matches(str.substr(1)) : this.matchesEmpty;
}
}
class Char extends Regex {
constructor(ch) {
super(false)
this.ch = ch;
}
derivativeBy(x) {
return this.ch == x? new Empty() : new MatchNothing();
}
}
class MatchNothing extends Regex {
constructor() {
super(false);
}
derivativeBy(ch) {
return this;
}
}
class Empty extends Regex {
constructor() {
super(true);
}
derivativeBy(ch) {
return new MatchNothing();
}
}
class Concat extends Regex {
constructor(left, right) {
super(left.matchesEmpty && right.matchesEmpty);
this.left = left;
this.right = right;
}
derivativeBy(ch) {
const justLeft = new Concat(this.left.derivativeBy(ch), this.right);
return this.left.matchesEmpty ?
new Or(justLeft, this.right.derivativeBy(ch)) :
justLeft;
}
}
class Or extends Regex {
constructor(left, right) {
super(left.matchesEmpty || right.matchesEmpty);
this.left = left;
this.right = right;
}
derivativeBy(ch) {
return new Or(this.left.derivativeBy(ch), this.right.derivativeBy(ch));
}
}
class Kleene extends Regex {
constructor(re) {
super(true);
this.re = re;
}
derivativeBy(ch) {
return new Concat(this.re.derivativeBy(ch), this);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment