序言
在实际工作中，我们几乎无可避免的接触到正则表达式，但很多时候又很容易犯迷糊：
-
为什么 grep、egrep、grep -P 会有不同的表现？
-
为什么 Golang 不支持反向引用、零宽断言等特性？
-
为什么有时贪婪匹配能正常工作，但相似的非贪婪匹配却引起内存暴涨？
以上问题不止一次的使我感到困惑，终于有一天，我决定好好弄清楚这些。
但本文并不是打算直接告诉大家以上问题的答案，而是想根据前人的理论使用 Golang 从零实现一个 Demo 版的正则表达式。虽然其理论基础和实现都并不复杂，通常在一个周末就可以完全搞定，但动手实现一遍对正则表达式的理解还是有相当大的帮助。
本文的实现依据是论文：swtch.com/~rsc/regex…
即正则表达式转换为 NFA(非确定有限状态自动机)。
Golang 官方库 regex 也是依据该篇论文的实现，所以完全弄懂该篇论文也是理解 regex 的关键。
实现代码我放在了仓库：codebase.byted.org/repo/zhoudi…
正则表达式运算
根据龙书介绍，最初的正则表达式包含三种基本运算，优先级从高到低依次是：
-
Kleene 闭包（*）、连接运算（.)、并运算（|）
-
相同运算符按照左结合运算
注意，此处的点不是通常的匹配“任意字符”的含义。
实际的实现中，都会对正则表达式运算进行大规模扩展。按上述论文我也扩充了两个：
-
零个或者一个(?)、一个或者多个(+)
-
其优先级等同于 (*)，并按左结合运算。
所以本 Demo 中也会实现上述五中运算（其实还包括了改变运算优先级的())。
状态转换图
每一个正则表达式都能找到对应的 DFA/NFA。以下我列出了五种正则表达式运算符的状态转换图。
其中：
-
s1、s2、s3 表示状态（节点）；start、end 表示广义的该状态的前继、后继状态；
-
状态后的边上如果跟了一个字符，表示该状态需要消耗该字符，才能流转到其后继状态；
-
状态后的边上如果没有跟字符（即空边，图中红色状态），表示可以直接流转到其后继状态；
-
白色节点是遇到字符形成的节点；红色节点是遇到操作符形成的节点；
解析正则表达式
在内存中，我们将上面的状态转换图表示成一棵可以形成环的二叉树。树中的每个节点可以对应到正则表达式的一个普通字符、一元运算符（* ? +) 或者 二元运算符（ . |)。
因此，我们的第一步是将正则表达式解析成一颗二叉树。树中节点的定义为：
type State struct {
C byte // 字符值
Out *State // 第一个后继
Out1 *State // 第二个后继
LastListID int // 先忽略该字段
}
如果节点代表普通字符（操作数），C 就为对应需要匹配的字符；
如果节点代表操作符，由于操作符节点不需要直接参与匹配。C 只起标记的作用。
正则表达式的过程，其实类似解析四则运算：如果遇到普通字符，直接生成对应节点；如果遇到操作符，根据优先级对操作数做某种运算。
正则表达式操作符的运算过程，则是改变相应普通字符节点的前继、后继节点指向。
字符分类
做个字符说明，这里把字符分为了如下几类：
-
左括号 (
-
右括号 )
-
一元操作符 * ? +
-
二运操作符 . |
-
普通字符
逆波兰表达式
我们首先用逆波兰式，表示出正则表达式，以方便操作符对操作数进行运算（实际生产中都是直接从正则表达式生成解析树）。
如 a.b|c.d 的逆波兰式为：ab.cd.| 。
用 . 在正则表达式中表示连接我感觉很奇怪，我写了一个方法对正则表达式自动加上 . 。也因此同时支持了基本的 () 操作，以能改变运算符之间的优先级。完整代码如下：
// 表达式增加连接符，便于逆波兰式转换
func AddConcatToExp(s string) string {
res := ""
for i := 0; i < len(s)-1; i++ {
first := s[i]
second := s[i+1]
if needAddContatChar(first, second) {
res += string(first)
res += string(ConcatChar)
} else {
res += string(first)
}
}
res += string(s[len(s)-1])
return res
}
func needAddContatChar(first, second byte) bool {
if first == RightParenthesis && isLiteralChar(second) {
return true
}
if first == RightParenthesis && second == LeftParenthesis {
return true
}
if (isOneOp(first) || isLiteralChar(first)) &&
(isLiteralChar(second) || second == LeftParenthesis) {
return true
}
return false
}
逆波兰式生成算法也很简单，主要是栈操作，就不再赘述，代码帖在这里：
// 转换成逆波兰表达式
func ToPostfix(s string) string {
res := ""
cStack := stack.NewStack()
for i := 0; i < len(s); i++ {
// fmt.Printf("res:%s, stack:%sn", res, cStack.View())
// 操作数
c := s[i]
if isLiteralChar(c) {
res += string(c)
continue
}
// 左括号
if c == LeftParenthesis {
cStack.Push(c)
continue
}
// 右括号，一直出栈到左括号
if c == RightParenthesis {
// (a+b*d)*c // abd*+ (+* )
for {
top := cStack.Pop().(byte)
if top == LeftParenthesis {
break
}
res += string(top)
}
continue
}
// 操作符，出栈更高或者相等优先级的操作符
for {
if cStack.Empty() {
break
}
top := cStack.Top().(byte)
if top == LeftParenthesis {
break
} else if OpPriorityIsGE(top, c) {
cStack.Pop()
res += string(top)
} else {
break
}
}
cStack.Push(c)
}
for !cStack.Empty() {
top := cStack.Pop().(byte)
res += string(top)
}
return res
}
解析树
有了逆波兰表达式后，就可以正式开始生成正则表达式解析树了。从左到右遍历逆波兰表达式：
-
如果遇到操作数就生成节点并入栈；
-
如果遇到操作符就从栈顶取出节点、生成一个新的节点、处理节点间链接，并用新节点代替旧节点入栈；
在如下简单的表达式a|b 中，由于 s2、s3 节点在合并到 s1 表示之后，还无法确定指向，我们还需要一个新的结构体临时字段来标识所有未确定的指向信息（悬空指针），以方便以后更新。
因为可以同时表示子节点的状态，该结构体是栈操作的真正对象。结构体如下（称作 Frag)：
type Frag struct {
Start *State
Out []**State // 指向悬空指针
}
在主体程序的最后我们让树的所有叶子节点指针都指向了终止状态（MatchState)。
解析树的主体程序如下：
func Parse(s string) *State {
fs := NewFragStack()
for i := 0; i < len(s); i++ {
switch s[i] {
default:
parseLiteralChar(fs, s[i]) // 普通字符
case SplitChar:
parseSplitChar(fs, s[i]) // 并操作符 |
case ConcatChar:
parseConcatChar(fs, s[i]) // 链接符 .
case QuestionChar:
parseQuestionChar(fs, s[i]) // ？
case PlusChar: // 会在树中形成环
parsePlusChar(fs, s[i]) // +
case StarChar: // 会在树中形成环
parseStarChar(fs, s[i]) // *
}
}
first := fs.Pop()
patchOutToState(first.Out, MatchState)
return first.Start
}
主要操作都在相应的解析方法里。各个具体解析方法是整个操作的核心，都是生成一个新的 Frag、处理指向关系、入栈。如并操作(其余不再赘述）：
// 并操作 |
func parseSplitChar(fs *FragStack, c byte) {
e1 := fs.Pop() // 后节点
e2 := fs.Pop() // 前节点
start := NewState(c, e2.Start, e1.Start)
nOut := make([]**State, 0)
nOut = append(nOut, e2.Out...)
nOut = append(nOut, e1.Out...)
f := NewFrag(start, nOut)
fs.Push(f)
}
匹配正则表达式
由于解析树的每个节点其实是代表了状态转换图的每个状态，所以有了解析树之后，匹配的过程就显的很自然。由于是 NFA ，每一个状态都是一个集合，所以：
-
首先构建状态转换图的初始状态集合；
-
读入一个字符，驱动当前状态集合转换到下一个状态集合；
-
不断重复上一个步骤，直至字符串读入到结尾；
-
判断状态集合中是否含有终止状态；有则匹配成功，否则匹配失败
主体代码如下：
type List struct {
s []*State
id int
}
func Match(start *State, s string) bool {
cList := &List{} // 当前状态集合
nList := &List{} // 下一个状态集合
listid := 0 // 状态消重用的，就是一个状态不能反复加入到当前状态中，不然会死循环
startList(start, cList, &listid)
var i int
for i = 0; i < len(s); i++ {
step(cList, s[i], nList, &listid)
cList, nList = nList, cList
}
return isMatch(cList)
}
在状态驱动时，如果当前节点是普通字符节点，则可以直接将其子节点放入下一个状态集合；如果当前节点是操作符节点，则应该将操作符节点的子节点放入下一个状态集合。
func addStateToList(l *List, s *State, listid int) {
if s == nil || s.LastListID == listid {
return
}
s.LastListID = listid
if s.C == SplitChar {
addStateToList(l, s.Out, listid)
addStateToList(l, s.Out1, listid)
return
}
// s 本身加入列表
l.s = append(l.s, s)
}
测试
观察解析树
我们随便看一个较为复杂的例子，进一步加深对解析树的理解：
-
正则表达式：ab|c?d*e+
-
图中 * 只是起占位作用，方便观察整个二叉树结构
-
图中 | 表示这个节点是一个“操作符节点”
-
图中小写字母表示节点是一个“普通字符节点”
-
大写字母和 表示，这个节点位置存在指向父节点的环路
通过下图，我们可以直观的看到解析树的结构，操作符节点相对操作数节点的位置，环路的状态等；
从上面的图，我们可以知道，在 d* 、e+ 两处存在环路；并且由于 c? 的原因，d* 和 e+ 节点被重复指向了。
测试匹配文本：cddddeee ， 可以匹配成功。
