Last active
June 27, 2018 12:17
-
-
Save yellowflash/0732325a3f7f41893c6a9ab39bde7039 to your computer and use it in GitHub Desktop.
A derivative based regex matching
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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