1、基础理论
非确定有限自动机（NFA)，是计算理论中抽象出来的状态机计算模型。它拥有有限个状态，当前状态根据不同的输入可以迁移到其他的状态，它的下一个状态不是唯一确定的。
正则表达式本身是有限长度的字符串，在这里可以看做NFA上输入状态组成的序列。于是，NFA可以用来作为一种识别装置识别正则表达式。
Thompson构造法：将正则表达式转换为NFA。这里的NFA包括ε状态及其转换，即不需要输入就可以进行状态转换。
两个状态之间的转换图如下：
（注：以下图片为使用在线绘图工具画图后截图所得）
正则表达式中包括一些子表达式的组合关系，可以概括如下：
对于NFA上的每个状态，我们可以概括为如下三种:
对于第一种状态，只有一个箭头，代表唯一的输出状态，c代表输入的字符（我们在此算法上进行改进，程序里的c是一个代表功能边的字符串）；对于第二种状态，我们定义为‘|’所代表的状态，它有两个输出状态；对于第三种状态，不需要输入信息而且也没有输出状态，代表了“终极状态”，也就是我们最后匹配成功的状态。
Thompson算法理论上只能实现基本的正则表达式的匹配，而不能实现扩展正则表达式以及后向引用等。我们在此算法的基础上，改进了数据结构，用一个功能边字符串来代替c，并在State中加了另一个字符变量ch来判定此状态属于哪一个后向引用。例如：字符串“[a-zA-Z]”被当做一个功能边来判定某个字符是否符合这里的规则，ch=‘2’代表此状态在第二个后向引用中。
根据以上状态和状态转换的分类，我们就可以将正则表达式构造出NFA了。
2、数据结构和算法思想
（1）首先，由于正则表达式是前缀表达式，而构造NFA的过程需要的是由后缀表达式代表的语法树。比如，“（ab)|c”的语法树如下：
其中的○即为两个子表达式的连接符号，在这是（），我们在后缀表达式中用两个点’..’来替换小括号起连接作用，所以后缀表达式为”ab..c|”。在程序中，我们通过函数std::vector<std::string>regexpToPostfix(void); 将语法树中每个节点中上的内容当做一个字符串（有的节点上的字符长度大于1，比如 “..”，此外，为了识别 “\w” 等转义符，我们提前处理成了 “\\w”，长度也大于1），后续遍历然后加入一个vector容器中。
（2）为了模拟状态和状态转换的关系，我们定义一个结构体State。成员变量c代表跳转到下一状态时携带的字符串信息。前文提到的三种状态中，对于第一种普通状态，c为原文信息；对于第二种，我们称之为Split状态，我们定义c的值为 “Split”；对于第三种，我们称之为Match状态，c值为“Match”；而变量ch即为第ch-‘0’个后向引用。结构体State定义如下：
struct State { //NFA状态
std::string c; //每条边上代表匹配功能的字符串
State *out; //指向下一个状态的指针，
State *out1;//当本状态为split时，out1表示分支
char ch; //后向引用时，ch为数字字符，否则为空格字符
int listIndex; //状态编号
State():c(""),out(NULL),out1(NULL),ch(' '),listIndex(-1) {}
State(std::string _c,State* p1,State* p2,char ct=' ',int listIndex=-1)
:c(_c),out(p1),out1(p2),ch(ct) {}
};
对于单个状态，有些状态可能存在多个输出状态，在此我们将这些输出状态连接成一个链表，然后就有了结构体PtrList，定义如下：
struct Ptrlist { //指向State指针的指针链表
Ptrlist *next;
State **outp;
Ptrlist(State **ptr):next(NULL),outp(ptr) {}
};
在NFA状态机构造过程中，我们将已经构造好成State，但是还没有加入到状态栈里的状态称为Frag，定义如下：
struct Frag {
State *start; //开始节点
Ptrlist* out; //out是一组指向未链接到任何东西的状态指针的列表的指针
Frag():start(NULL),out(NULL) {}
Frag(State *s,Ptrlist *list):start(s),out(list) {}
};
（3）全局变量：
const char *str; //待匹配的字符串
std::string regexp; //构造NFA的正则表达式
int listid;
List currentList; //当前状态链表
List nextList; //下一个状态链表
State *matchState; //匹配状态
std::vector<std::string> edge; //从regexp中分离出的token字符串
Pos pos[10]; //各个后向引用的开始与结束位置
int reference[10];
std::map<char,std::string> result_reference; //每个后向引用对应的必须匹配的字符串
bool no_addstate;
int iteratorTimes; //防止死循环的迭代次数
int isEmpty; //判断某个后向引用是否为空字符串，
（4）匹配结果必须是从左到右匹配到的第一个结果，且满足贪婪原则。为此，对于一行待匹配的字符串，我们设置一个两个下标left、right，分别作为子字符串两端的下标，两个for语句循环，外面一层是left从0开始自增，里面一层是right从右边界开始自减。然后用函数intmatchString(State *start,int left,int right)匹配子字符串，一旦成功即退出循环并成功返回。
3、程序模块
（1）构造NFA
函数：State*postfixToNfa(std::vector<std::string> postfix);
经过前面处理后得到的后缀表达式，可以用来构造NFA。举个例子，对于上文出现的后缀表达式 “ab..c|”（实际上是包含 “a”,“b”,“..”,“c”,“|” 的字符串容器），大概实现过程如下：
对于 “a”,首先生成一个State变量，然后构造出该状态State的碎片Frag，然后加入到一个存放Frag栈，即stack<Frag>；然后到 “b”,同上，Frag入栈；对于 “..”，即我们定义的连接符，这时从栈顶取出两个碎片Frag e1,e2,通过函数voiddanglingPointLinkToState(e1.out,e2.start); 将两个状态连接起来，然后把连接后两个状态构成的Frag入栈。对于 “c”,同“a”；对于 “|”，这里代表分支，取出栈顶两个元素，然后新生成一个Split状态，将取出的两个状态作为Split的输出状态，Split状态构造Frag然后入栈；最后，也是判断正则表达式匹配是否成功的关键，需要生成一个Match状态，将其连接到栈顶元素的状态后面。函数执行完后返回栈底元素的state。最终生成状态图如下：
（2）匹配字符串
函数：intmatchString(State *start,int right)；
NFA工作过程是从左到右逐个去匹配字符。实现过程如下：首先初始化当前状态列表，然后进入循环，一步一步去匹配。循环结束后检查是否成功匹配整个字符串。在这个过程中涉及到两个重要子函数：
单步匹配函数voidnextState(List *cur_list,List *next_list,const char* str,char end)；状态匹配成功后，调用函数addStateToList将其添加一个新状态到列表中。在这个函数中，需要根据当前状态输入信息，即state->c，做不同的处理。state->c如果是占位符，比如 “a”，“\w”，则调用isEqual函数判断该占位符是否能匹配字符串的指定位置；如果不是占位符， “^”,“\b”,“\B”,“$”,则需要调用isWBoudary等函数判断字符串当前位置是否合法，如果合法，字符串指定当前位置不变，状态机的下一个状态去匹配字符串该位置。
检查匹配成功函数intisMatch(List *l); 根据列表中的状态集是否包含Match状态判断是否匹配成功。
匹配过程中的相关操作函数：/*** * 判断字符c与NFA的状态是否匹配 */ bool RegexpToNfa::isEqual(string edgeStr,char c,State *s) /*** * 对一个字符c进行匹配状态操作 */ void RegexpToNfa::nextState(List *cur_list,const char* testStr,char end)（3）其他字符串处理的函数
/*** * 将输入的字符串按token分开为字符串 */ void RegexpToNfa::getToken(string re) /**** * 将字符串中的大括号里的重复次数 * 换成代表重复的*，+，？等等 */ void RegexpToNfa::dealBrace(string re) /*** * 获取中括号[]的位置 * 通过指针pStart,pEnd返回左括号[和右括号]的位置信息 */ void RegexpToNfa::FindBracket(const char* pStart,const char*& pEnd) /*** * 根据中括号里第一个字符位置指针pStart和最后一个字符地位置指针pEnd * 返回其中所有可能取值的字符串的集合，作为一个字符串 */ string RegexpToNfa::GetBracketContent(const char* pStart,const char* pEnd) /*** * 判断字符c是否是中括号取值集合里面的一个 */ int RegexpToNfa::MatchBracket(char c,string str) /** * 判断当前指针位置是否为行结尾 */ bool RegexpToNfa::isLEnd(const char* pStr)
