实现一个正则表达式引擎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每个节点都有唯一的一个标识
-
visited则是为了debug用来遍历NFA
class Nfa(object):
STATUS_NUM = 0
def __init__(self):
self.edge = EPSILON
self.next_1 = None
self.next_2 = None
self.visited = False
self.input_set = set()
self.set_status_num()
def set_status_num(self):
self.status_num = Nfa.STATUS_NUM
Nfa.STATUS_NUM = Nfa.STATUS_NUM + 1
def set_input_set(self):
self.input_set = set()
for i in range(ASCII_COUNT):
self.input_set.add(chr(i))
简单节点的构造
节点的构造在nfa.construction下，这里为了简化代码把Lexer作为全局变量，让所有函数共享
正则表达式的BNF范式如下，这样我们可以采用自顶向下来分析，从最顶层的group开始向下递归
group ::= ("(" expr ")")*
expr ::= factor_conn ("|" factor_conn)*
factor_conn ::= factor | factor factor*
factor ::= (term | term ("*" | "+" | "?"))*
term ::= char | "[" char "-" char "]" | .
BNF在之前写C语言编译器的时候有提到： 从零写一个编译器（二）
主入口
这里为了简化代码，就把词法分析器作为全局变量，让所有函数共享
主要逻辑非常简单，就是初始化词法分析器，然后传入NFA头节点开始进行递归创建节点
def pattern(pattern_string):
global lexer
lexer = Lexer(pattern_string)
lexer.advance()
nfa_pair = NfaPair()
group(nfa_pair)
return nfa_pair.start_node
term
虽然是采用的是自顶向下的语法分析，但是从自底向上看会更容易理解，term是最底部的构建，也就是像单个字符、字符集、.符号的节点的构建
term ::= char | "[" char "-" char "]" | | .
term的主要逻辑就是根据当前读入的字符来判断应该构建什么节点
def term(pair_out):
if lexer.match(Token.L):
nfa_single_char(pair_out)
elif lexer.match(Token.ANY):
nfa_dot_char(pair_out)
elif lexer.match(Token.CCL_START):
nfa_set_nega_char(pair_out)
三种节点的构造函数都很简单，下面图都是用markdown的mermaid随便画画的
- nfa_single_char
单个字符的NFA构造就是创建两个节点然后把当前匹配的字符作为edge
def nfa_single_char(pair_out):
if not lexer.match(Token.L):
return False
start = pair_out.start_node = Nfa()
pair_out.end_node = pair_out.start_node.next_1 = Nfa()
start.edge = lexer.lexeme
lexer.advance()
return True
- nfa_dot_char
. 这个的NFA和上面单字符的唯一区别就是它的edge被设置为CCL，并且设置了input_set
# . 匹配任意单个字符
def nfa_dot_char(pair_out):
if not lexer.match(Token.ANY):
return False
start = pair_out.start_node = Nfa()
pair_out.end_node = pair_out.start_node.next_1 = Nfa()
start.edge = CCL
start.set_input_set()
lexer.advance()
return False
- nfa_set_nega_char
这个函数逻辑上只比上面的多了一个处理input_set
def nfa_set_nega_char(pair_out):
if not lexer.match(Token.CCL_START):
return False
neagtion = False
lexer.advance()
if lexer.match(Token.AT_BOL):
neagtion = True
start = pair_out.start_node = Nfa()
start.next_1 = pair_out.end_node = Nfa()
start.edge = CCL
dodash(start.input_set)
if neagtion:
char_set_inversion(start.input_set)
lexer.advance()
return True
小结
篇幅原因，现在已经写到了三百多行，所以就分篇写，准备在三篇内完成。下一篇写构造更复杂的NFA和通过构造的NFA来分析输入字符串。最后写从NFA转换到DFA，再最后用DFA分析输入的字符串
About The Author
