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

前言

项目地址:Regex in Python

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

实现目标

实现了所有基本语法

1
2
3
4
5
6
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语言的编译器的思路来,只是没有那么复杂而已

  1. 首先进行词法分析
  2. 语法分析(这里用自顶向下)
  3. 语义分析 (因为正则的表达能力非常弱,所以可以省略生成AST的部分直接进行代码生成)
  4. 代码生成,这里也就是进行NFA的生成
  5. NFA到DFA的转换,这里开始就是正则和状态机的相关的知识了
  6. 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连接起来

image.png
image.png

词法分析

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

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

  1. 普通字符
  2. 含有语义的字符
  3. 转义字符

token

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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开始向下递归

1
2
3
4
5
group ::= ("(" expr ")")*
expr ::= factor_conn ("|" factor_conn)*
factor_conn ::= factor | factor factor*
factor ::= (term | term ("*" | "+" | "?"))*
term ::= char | "[" char "-" char "]" | .

BNF在之前写C语言编译器的时候有提到:从零写一个编译器(二)

主入口

这里为了简化代码,就把词法分析器作为全局变量,让所有函数共享

主要逻辑非常简单,就是初始化词法分析器,然后传入NFA头节点开始进行递归创建节点

1
2
3
4
5
6
7
8
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的主要逻辑就是根据当前读入的字符来判断应该构建什么节点

1
2
3
4
5
6
7
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

a

1
2
3
4
5
6
7
8
9
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

a

1
2
3
4
5
6
7
8
9
10
11
12
# . 匹配任意单个字符
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

a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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分析输入的字符串