曾经有人开玩笑：
当碰到棘手问题的时候，可以考虑使用正则表达式
当考虑正则表达式的时候，又多了一个棘手的问题
日常工作中，正则表达式是一个非常强大的工具，编写编译器/解释器的时候，正则表达式是必须的工具。自己动手写一个正则表达式，有利于使用者以正则表达式的方式思考，也是一个非常好的锻炼编码能力的小项目
思路
正则表达式的背后其实是图论算法，匹配的过程就是使用确定有限状态机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的《算法》(第四版)第五章正则表达式。
关于正则表达式的完整详实的说明，请参考《编译原理》(龙书)第三章词法分析
关于正则表达式的使用，最好的书是《精通正则表达式》，入门可以参考《正则表达式必知必会》
