Golang 实现正则表达式

序言

在实际工作中，我们几乎无可避免的接触到正则表达式，但很多时候又很容易犯迷糊：

为什么 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:%s\n", 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)
}