动手写一个正则表达式引擎

曾经有人开玩笑：
当碰到棘手问题的时候，可以考虑使用正则表达式
当考虑正则表达式的时候，又多了一个棘手的问题

日常工作中，正则表达式是一个非常强大的工具，编写编译器/解释器的时候，正则表达式是必须的工具。自己动手写一个正则表达式，有利于使用者以正则表达式的方式思考，也是一个非常好的锻炼编码能力的小项目

思路

正则表达式的背后其实是图论算法，匹配的过程就是使用确定有限状态机DFA或者非确定有限状态机NFA模拟识别过程，两者是等价的。更下一层，会使用有向图的遍历算法。

有向图

class Digraph:
    """
    有向图的邻接表表示
    """
    def __init__(self, v):
        self.v = v  # 顶点数
        self.e = 0  # 边数
        self.adj = [set() for _ in range(v)]  # 邻接表
    
    def add_edge(self, edge):
        s, e = edge
        self.adj[s].add(e)
        self.e += 1

    def dfs(self, sources, marked=None):
        """
        ε闭包: 深度优先搜索, 记录可达的顶点集
        """
        marked = marked or set()
        for s in sources:
            if s not in marked:
                marked.add(s)
                self.dfs(self.adj[s], marked)
        return marked

深度优先dfs给定多个起始节点，计算这些点开始可达的顶点集

简单的正则引擎模型

正则表达式的定义：
一·空字符是正则表达式ε
二·单个字符是正则表达式
三·包含在括号()中的另一个正则表达式
四·两个或多个连接起来的正则表达式
五·由或运算符|分割的两个或多个正则表达式
六·由闭包运算符标记的一个正则表达式

闭包运算符有：*，+，?，本demo中只实现了 *

正则表达式的运行分为两个阶段

第一阶段：编译正则表达式，生成NFA或者DFA，对应初始化MyRE（本处时NFA）

第二阶段：识别目标文本，（在NFA上模拟DFA步骤）

class MyRE:
    """
    使用非确定有限状态机(NFA)模拟匹配过程
    """
    def __init__(self, regexp):
        self.regexp = f'(.*{regexp}.*)'
        self.g = Digraph(len(self.regexp)+1)
        
        ops = []
        for i, c in enumerate(self.regexp):
            lp = i
            if c in '(|':
                ops.append(i)
            elif c == ')':
                ori = ops.pop()
                if self.regexp[ori] == '|':
                    lp = ops.pop()
                    self.g.add_edge([lp, ori+1])
                    self.g.add_edge([ori, i])
                else:
                    lp = ori
            if i < len(self.regexp)-1 and self.regexp[i+1] == '*':
                self.g.add_edge([lp, i+1])
                self.g.add_edge([i+1, lp])
            if c in '(*)':
                self.g.add_edge([i, i+1])

    def recognizes(self, txt):
        pc = self.g.dfs([0])
        for c in txt:
            match = set()  # 识别c后能够到达的顶点集
            for v in pc:
                if v < len(self.regexp):
                    if self.regexp[v] == c or self.regexp[v] == '.':
                        match.add(v+1)
            pc = self.g.dfs(match)  # 计算ε闭包
        return len(self.regexp) in pc  # 包含结束状态顶点

识别的过程中，从第一个字符和开始状态开始，先计算开始状态可以直接到达的状态集（ε-闭包），然后识别下一个字符，然后再计算ε-闭包，再识别下一个字符，依次递进。识别字符结束，如果结束时的状态集包含结束状态，就表示这个NFA接受文本。

测试运行

# 文件名： grep.py

if __name__ == '__main__':
    import sys
    pattern = sys.argv[1]
    search_file = sys.argv[2]
    my_re = MyRE(pattern)
    with open(search_file) as fp:
        for line in fp.readlines():
            line = line.strip()
            if my_re.recognizes(line):
                print(line)

效果

(env3.6.7) ➜  mydemo cat my.txt
AC
AD
AAA
ABD
ADD
BCD
ABCCBD
BABAAA
BABBAAA
(env3.6.7) ➜  mydemo python grep.py "(A*B|AC)D" my.txt
ABD
ABCCBD
(env3.6.7) ➜  mydemo

补充说明

本demo的实现参考Sedgewick的《算法》(第四版)第五章正则表达式。

关于正则表达式的完整详实的说明，请参考《编译原理》(龙书)第三章词法分析

关于正则表达式的使用，最好的书是《精通正则表达式》，入门可以参考《正则表达式必知必会》