Skip to content

Instantly share code, notes, and snippets.

@yellowflash
Last active Jun 27, 2018
Embed
What would you like to do?
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