Last active
October 29, 2021 17:49
-
-
Save picasso250/0efc287080664f43eb93 to your computer and use it in GitHub Desktop.
This file contains 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
// from c++ version: https://gist.github.com/timshen91/f6a3f040e5b5b0685b2a | |
// author: wangxiaochi | |
function ConcatExpr (Left,Right) {this.Left = Left;this.Right=Right} // ab | |
function AltExpr(Left,Right) {this.Left = Left;this.Right=Right} // a|b | |
function RepeatExpr(SubExpr) {this.SubExpr= SubExpr;} // a* | |
function OptionalExpr(SubExpr) {this.SubExpr= SubExpr;} // a? | |
function MatchExpr(ch) { | |
this.ch= ch | |
} | |
MatchImplApply = function (expr, target, i, cont) { | |
switch (true) { | |
case expr instanceof ConcatExpr: | |
return MatchImplApply(expr.Left, target, i, (rest,ri) => | |
MatchImplApply(expr.Right, rest, ri, cont)) | |
case expr instanceof AltExpr: | |
return (MatchImplApply(expr.Left, target, i, cont) || | |
MatchImplApply(expr.Right, target, i, cont)) | |
case expr instanceof RepeatExpr: | |
return MatchImplApply(expr.SubExpr, target, i, (rest,ri) => | |
(MatchImplApply(expr, rest, ri, cont) || cont(rest,ri)) | |
) || cont(target, i) | |
case expr instanceof OptionalExpr: | |
return MatchImplApply(expr.SubExpr, target, i, cont) || cont(target, i) | |
case expr instanceof MatchExpr: | |
return target[i] !== undefined && target[i] == expr.ch && cont(target, i+1) // end of string, match a char | |
default: | |
throw "no expression type" | |
} | |
} | |
RegexMatch = (RegExpr,target) => // all match | |
MatchImplApply(RegExpr, target,0, (rest,i) => rest[i] === undefined) | |
RegexSearch = (RegExpr,target,i) => // partial match from begining | |
MatchImplApply(RegExpr, target,i, (rest,i) => true) || | |
(target[i] !== undefined && RegexSearch(RegExpr, target, i+1)) | |
console.assert(RegexMatch(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b')), "ab")); | |
console.assert(RegexMatch(new AltExpr(new MatchExpr('a'), new MatchExpr('b')), "a")); | |
console.assert(RegexMatch(new AltExpr(new MatchExpr('a'), new MatchExpr('b')), "b")); | |
console.assert(RegexMatch(new RepeatExpr(new MatchExpr('a')), "aaaaa")); | |
console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')), | |
"aaaaab")); | |
console.assert(RegexMatch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')), | |
"b")); | |
console.assert(RegexSearch(new ConcatExpr(new RepeatExpr(new MatchExpr('a')), new MatchExpr('b')), | |
"aaaaabb", 0)); | |
console.assert(RegexMatch(new OptionalExpr(new MatchExpr('a')), "a")); | |
console.assert(RegexMatch(new OptionalExpr(new MatchExpr('a')), "")); | |
console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b'))), | |
"ab")); | |
console.assert(RegexMatch(new OptionalExpr(new ConcatExpr(new MatchExpr('a'), new MatchExpr('b'))), | |
"")); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment