大概和我不以程序员为职业有关吧，我本人是比较喜欢算法的那种，当然是比不了科班出身的。

比如我就写过很多版本的算术表达式解析器，优先级堆栈的；二叉树的；分治策略的；修正计算顺序的……

正则表达式两个我也写过两个，一个采用的回溯算法，另一个则是二叉树版本的，虽然这俩倒是都能用吧，但是对分组的处理（分组是采用递归调用的方法实现的，相当于另一个正则表达式）实在是不太好，这个缺点导致很多时候搜索的结果会遗漏很多，而二叉树版本的还有个缺点是选择操作“|”只能获得第一个匹配…………

就效果看，这俩都是残次品。

后来，我在vczh的博客里看到了他的一个科普贴子，在那里面，我才了解到还有有限自动机这种方法。

之后我花了不少时间去思考，因为总觉得这个方法太麻烦了，断断续续有2-3个月吧，想来想去也没想出什么更好的法子，最后还是觉得只有用有限自动机才合适。

不过多少我还是做了些修改的，倒不是为了效率，是为了减少打字量……

主要修改如下：

（1）不每个字符转移一次状态，而是尽可能的把连续的字符作为一个整体进行比对。

（2）不弄什么字母分组表，数据结构就使用指针链表，节省工作量

（3）“{a,b}”这种有次数限定的重复，vczh是采用复制节点实现的，我采用增加状态边来解决（效率会下降）

（4）分组命名，向前向后预查这些花哨而实用的功能，俺就丢了

那么，整体上看，正则表达式引擎的设计我就划分为如下几个步骤：

1）对规则字符串做预处理，主要是换行这类要使用转义符的字符，这个预处理可以把这些字符还原

2）将规则字符串进行划分，修正成操作符、操作数的列表形式

3）对这个列表进行处理，获得NFA状态转移图

4）将NFA状态转移图里的ε边消去，减少状态转移数

5）利用得到的状态转移图，对字符串进行匹配

第一步很容易解决，无非就是找到'\'，然后将后跟't'、'n'、'r'等字符的修正为相应的制表、换行……

第二步也相对简单，无非是识别几个操作符:

'*'、'+'、'?'、'*?'、'+?'、'??'、'('、'(:'、')'、'|'、'['、']'、'{'、'}'

比较特殊的是：

因为把连续的字符看做一个整体，所以在后跟重复或者可选运算符时，要检查一下是否需要断开字符串；

'['后面要一直读取到前面不是'\'的']'，期间不作分析，结果作为一个整体

'{'后面有'{a}'、'{a,}'、'{,a}'、'{a,b}'这几种形式，同样是读取为一个整体

还有一个隐藏的操作符，它的作用是将两个操作数连接起来，类似算术里的“*”，关于它另有介绍[*]

如此一来，列表里的成员记录的内容就会有好几种，python里这不算啥，C++里就麻烦一些，我采用的是struct和union来回嵌套+标志字节的办法来处理这个问题。

（如果使用正则表达式这一步非常轻松，可是如果用了就真成了笑话了）

第三步见下一帖

[*]被隐藏了的“连接”运算符，比如“ab[cd]”这个字符串，分析后的两个元素“ab”和“[cd]”正是通过这个操作符连接的。这个隐藏运算符我是用后面的Operator类的一个补足函数来填充修复的，不然就得另外写一个函数了。