Implement of tim's compile time regex -> https://gist.github.com/timshen91/f6a3f040e5b5b0685b2a

regex_runtime.cc

#include <functional>
#include <cassert>
#include <iostream>

enum ExprType {
  ConcatExpr,
  AltExpr,
  RepeatExpr,
  MatchExpr,
  EpsilonExpr
};

struct Expr {
  Expr(ExprType et) : _et(et) { }
  Expr(ExprType et, Expr* lt, Expr* rt) : _et(et), left(lt), right(rt) { }
  Expr(ExprType et, Expr* sub) : _et(et), sub_expr(sub) { }
  Expr(ExprType et, char c) : _et(et), ch(c) { }
  ExprType _et;

  union {
    struct { Expr* left, *right; };
    struct { Expr* sub_expr; };
    struct { char ch; };
  };

  ~Expr() {
    delete left;
    delete right;
    delete sub_expr;
  }
};

bool RegexMatchImpl(const Expr* expr, const char* target,
		const std::function<bool(const char* rest)>& cont) {
  switch(expr->_et) {
    case EpsilonExpr: {
      return cont(target);
    }
    case MatchExpr: {
      return *target && *target == expr->ch && cont(target + 1);
    }
    case ConcatExpr: {
      return RegexMatchImpl(expr->left, target, [cont, expr](const char* rest) -> bool {
	return RegexMatchImpl(expr->right, rest, cont);
      });
    }
    case AltExpr: {
      return RegexMatchImpl(expr->left, target, cont) ||
	      RegexMatchImpl(expr->right, target, cont);
    }
    case RepeatExpr: {
      return RegexMatchImpl(expr->sub_expr, target,
			    [target, cont, expr](const char* rest) -> bool {
			      return target < rest &&
				RegexMatchImpl(new Expr(RepeatExpr, expr->sub_expr), rest, cont);
			    }) || cont(target);
    }
  }
}

bool RegexMatch(const Expr* expr, const char* target) {
  return RegexMatchImpl(expr, target, [](const char* rest) -> bool { return *rest == '\0'; });
}

int main() {
  assert(RegexMatch(new Expr(ConcatExpr,new Expr(MatchExpr, 'a'), new Expr(MatchExpr,'b')), "ab"));
  assert(RegexMatch(new Expr(AltExpr, new Expr(MatchExpr, 'a'), new Expr(MatchExpr, 'b')), "a"));
  assert(RegexMatch(new Expr(AltExpr, new Expr(MatchExpr, 'a'), new Expr(EpsilonExpr)), ""));
}