实现一个正则表达式引擎in Python(一)

项目地址：Regex in Python

开学摸鱼了几个礼拜，最近几天用Python造了一个正则表达式引擎的轮子，在这里记录分享一下。

实现目标

实现了所有基本语法

st = 'AS342abcdefg234aaaaabccccczczxczcasdzxc' pattern = '([A-Z]+[0-9]*abcdefg)([0-9]*)(\*?|a+)(zx|bc*)([a-z]+|[0-9]*)(asd|fgh)(zxc)' regex = Regex(st, pattern) result = regex.match() log(result)

更多示例可以在github上看到

前置知识

其实正则表达式的引擎完全可以看作是一个小型的编译器，所以完全可以按之前写的那个C语言的编译器的思路来，只是没有那么复杂而已

首先进行词法分析

语法分析（这里用自顶向下）

语义分析 （因为正则的表达能力非常弱，所以可以省略生成AST的部分直接进行代码生成）

代码生成，这里也就是进行NFA的生成

NFA到DFA的转换，这里开始就是正则和状态机的相关的知识了

DFA的最小化

NFA和DFA

有限状态机可以看作是一个有向图，状态机中有若干个节点，每个节点都可以根据输入字符来跳转到下一个节点，而区别NFA((非确定性有限状态自动机)和DFA(确定性有限状态自动机)的是DFA的下一个跳转状态是唯一确定的)

有限状态自动机从开始的初始状态开始读取输入的字符串，自动机使用状态转移函数move根据当前状态和当前的输入字符来判断下一个状态，但是NFA的下一个状态不是唯一确定的，所以只能确定的是下一个状态集合，这个状态集合还需要依赖之后的输入才能确定唯一所处的状态。如果当自动机完成读取的时候，它处于接收状态的话，则说明NFA可以接收这个输入字符串

对于所有的NFA最后都可以转换为对应的DFA

NFA构造O(n)，匹配O(nm)

DFA构造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)

n=regex长度，m=串长，k=字母表大小，n'=原始的dfa大小

NFA接受的所有字符串的集合是NFA接受的语言。这个语言是正则语言。

例子

对于正则表达式：[0-9]*[A-Z]+，对应的NFA就是将下面两个NFA的节点3和节点4连接起来

词法分析

对于NFA和DFA其实只要知道这么多和一些相应的算法就已经足够了，相应的算法在后面提及，先完成词法分析的部分，

这个词法分析比之前C语言编译器的语法分析要简单许多，只要处理几种可能性

普通字符

含有语义的字符

转义字符

token

token没什么好说的，就是对应正则里的语法

Tokens = { '.': Token.ANY, '^': Token.AT_BOL, '$': Token.AT_EOL, ']': Token.CCL_END, '[': Token.CCL_START, '}': Token.CLOSE_CURLY, ')': Token.CLOSE_PAREN, '*': Token.CLOSURE, '-': Token.DASH, '{': Token.OPEN_CURLY, '(': Token.OPEN_PAREN, '?': Token.OPTIONAL, '|': Token.OR, '+': Token.PLUS_CLOSE, } advance

advance是词法分析里最主要的函数，用来返回当前输入字符的Token类型

def advance(self): pos = self.pos pattern = self.pattern if pos > len(pattern) - 1: self.current_token = Token.EOS return Token.EOS text = self.lexeme = pattern[pos] if text == '\\': self.isescape = not self.isescape self.pos = self.pos + 1 self.current_token = self.handle_escape() else: self.current_token = self.handle_semantic_l(text) return self.current_token

advance的主要逻辑就是读入当前字符，再来判断是否是转义字符或者是其它字符

handle_escape用来处理转义字符，当然转义字符最后本质上返回的还是普通字符类型，这个函数的主要功能就是来记录当前转义后的字符，然后赋值给lexem，供之后构造自动机使用

handle_semantic_l只有两行，一是查表，这个表保存了所有的拥有语义的字符，如果查不到就直接返回普通字符类型了

完整代码就不放上来了，都在github上

构造NFA

构造NFA的主要文件都在nfa包下，nfa.py是NFA节点的定义，construction.py是实现对NFA的构造

NFA节点定义

NFA节点的定义也很简单，其实这个正则表达式引擎完整的实现只有900行左右，每一部分拆开看都非常简单

edge和input_set都是用来指示边的，边一共可能有四种种可能的属性

对应的节点有两个出去的ε边
edge = PSILON = -1

边对应的是字符集
edge = CCL = -2
input_set = 相应字符集

一条ε边
edge = EMPTY = -3

边对应的是单独的一个输入字符c
edge = c

status_num每个节点都有唯一的一个标识