The C++ Template language is Turing complete.  That means it should easily be able to build an Acceptor for a Regular expression.  Yes, this is headed where you think it is. Get out while you still can.

Still with me?  Too bad for you:

#include <string>

using std::string;

namespace acceptor{

template <typename Next> class Expression{
    public:
    static bool accept(string& s){
        return Next::accept(s, s.begin());
    }
};

class EndType {
    public:
    static bool accept(string& s, string::iterator itr){
       return(itr == s.end());
    }
};

class NoOp {
    public:
    static bool accept(string& s, string::iterator itr){
        return true;
    }
};

template <char valid,typename Next = NoOp > class Char{
    public:
    static bool accept(string& s, string::iterator  itr){
        return (valid == *itr) && Next::accept(s,++itr);
    }
};

template <char first,char last,typename Next = NoOp >
class RangeAcceptor{
    public:
    static bool accept(string& s, string::iterator itr){
        return ((*itr >= first)
            && (*itr <= last)
            && Next::accept(s,++itr));
    }
};

template <int count, typename Acceptor ,typename Next = NoOp>
class Count{
    public:
    static bool accept(string& s, string::iterator itr){
        int i;
        for ( i = 0; i < count ; ++i){
            if (Acceptor::accept(s,itr)){
                ++itr;
            }else{
                return false;
            }
        }
        return Next::accept(s, itr);
    }
};

template <typename First, typename Second >
class Or {
    public:
    static bool accept(string& s, string::iterator itr){
        if ( First::accept(s,itr)) {
            return true;
        } else {
            return Second::accept(s,itr);
        }
    }
};

template <typename First, typename Second >
class And {
public:
    static bool accept(string& s, string::iterator itr){
        return (First::accept(s,itr) && Second::accept(s,itr));
    }
};

template <typename Next = NoOp >
class Digit: public RangeAcceptor<'0','9',Next>{};

template <typename Next>
class LowerLetter : public RangeAcceptor<'a','z',Next>{};

template <typename Next>
class UpperLetter : public RangeAcceptor<'A','Z',Next>{};

template <typename Next = NoOp >
class Letter : public Or < LowerLetter<NoOp> , UpperLetter<NoOp> > {};
};

How would you use this?

void testDigit(){
Expression<
Digit <
Digit <
Digit <
Char  < '-' ,
Digit <
Digit <
Char  < '-' ,
Digit <
Digit <
Digit <
Digit <
EndType
> > > > > > > > > > > >ssn;

string s("000-22-9999");
assertTrue(s, ssn.accept(s));

s = "abcdefghij";
assertFalse(s, ssn.accept(s));
};

Not shown:  Implementation of the Kleene Star, as that would require a writing a greedy algorithm, something I have no desire to do right now.