reg_expr.js

// 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'))),
    ""));