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

项目地址:Regex in Python

在看一下之前正则的语法的 BNF 范式

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

上一篇构造了 term 的简单 NFA

构造复杂的 NFA

factor

根据上面的factor ::= (term | term ("*" | "+" | "?"))*,先进行 term 的 NFA 的生成,然后根据词法分析器来判断要进行哪个 factor 的 NFA 的构造

1
2
3
4
5
6
7
8
def factor(pair_out):
term(pair_out)
if lexer.match(Token.CLOSURE):
nfa_star_closure(pair_out)
elif lexer.match(Token.PLUS_CLOSE):
nfa_plus_closure(pair_out)
elif lexer.match(Token.OPTIONAL):
nfa_option_closure(pair_out)

nfa_star_closure

*操作就是对之前的 term 再生成两个节点进行连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def nfa_star_closure(pair_out):
if not lexer.match(Token.CLOSURE):
return False
start = Nfa()
end = Nfa()
start.next_1 = pair_out.start_node
start.next_2 = end

pair_out.end_node.next_1 = pair_out.start_node
pair_out.end_node.next_2 = end

pair_out.start_node = start
pair_out.end_node = end

lexer.advance()
return True

nfa_plus_closure

+和*的唯一区别就是必须至少匹配一个字符,所以不能从节点 2 直接跳转到节点 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def nfa_plus_closure(pair_out):
if not lexer.match(Token.PLUS_CLOSE):
return False
start = Nfa()
end = Nfa()
start.next_1 = pair_out.start_node

pair_out.end_node.next_1 = pair_out.start_node
pair_out.end_node.next_2 = end

pair_out.start_node = start
pair_out.end_node = end

lexer.advance()
return True

nfa_option_closure

?对应的则是只能输入 0 个或 1 个的匹配字符,所以相对于*就不能再次从节点 1 跳转会节点 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def nfa_option_closure(pair_out):
if not lexer.match(Token.OPTIONAL):
return False
start = Nfa()
end = Nfa()

start.next_1 = pair_out.start_node
start.next_2 = end
pair_out.end_node.next_1 = end

pair_out.start_node = start
pair_out.end_node = end

lexer.advance()
return True

factor_conn

factor_conn ::= factor | factor factor*

对于 factor_conn 就是一个或者多个 factor 相连接,也就是说如果有多个 factor,只要将它们的头尾节点相连接

1
2
3
4
5
6
7
8
9
10
11
def factor_conn(pair_out):
if is_conn(lexer.current_token):
factor(pair_out)

while is_conn(lexer.current_token):
pair = NfaPair()
factor(pair)
pair_out.end_node.next_1 = pair.start_node
pair_out.end_node = pair.end_node

return True

expr

expr ::= factor_conn ("|" factor_conn)*

对于 expr 就是一个 factor_conn 或者多个 factor_conn 用|相连接

构建|的 NFA 就是生成两个新节点,新生成的头节点有两条边分别连接到 factor_conn 的头节点,对于两个 factor_conn 的尾节点分别生成一条边连接到新生成的尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def expr(pair_out):
factor_conn(pair_out)
pair = NfaPair()

while lexer.match(Token.OR):
lexer.advance()
factor_conn(pair)
start = Nfa()
start.next_1 = pair.start_node
start.next_2 = pair_out.start_node
pair_out.start_node = start

end = Nfa()
pair.end_node.next_1 = end
pair_out.end_node.next_2 = end
pair_out.end_node = end

return True

group

group 其实就是在 expr 上加了两个括号,完全可以去掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def group(pair_out):
if lexer.match(Token.OPEN_PAREN):
lexer.advance()
expr(pair_out)
if lexer.match(Token.CLOSE_PAREN):
lexer.advance()
elif lexer.match(Token.EOS):
return False
else:
expr(pair_out)

while True:
pair = NfaPair()
if lexer.match(Token.OPEN_PAREN):
lexer.advance()
expr(pair)
pair_out.end_node.next_1 = pair.start_node
pair_out.end_node = pair.end_node
if lexer.match(Token.CLOSE_PAREN):
lexer.advance()
elif lexer.match(Token.EOS):
return False
else:
expr(pair)
pair_out.end_node.next_1 = pair.start_node
pair_out.end_node = pair.end_node

构造 NFA 总结

可以看到对于整个 NFA 的构造,其实就是从最顶部开始向下递归,整个过程大概是:

  • expr -> factor_conn -> factor -> term

  • 当递归过程回到factor_conn会根据factor_conn ::= factor | factor factor*判断可不可以继续构造下一个factor

  • 如果不可以就返回到expr,expr则根据expr ::= factor_conn ("|" factor_conn)*
    判断能不能继续构造下一个factor_conn

  • 重复上面的过程

匹配输入字符串

现在已经完成了NFA的构造,接下来就是通过这个NFA来对输入的字符串进行分析

一个例子

以刚刚的图作为演示,假设0-1节点的边是字符集0-9,4-5节点的边是字符集a-z,其它都是空

所以这个图表示的正则表达式[0-9]*[a-z]+

假设对于分析字符串123a

  • closure

从开始节点8进行分析,我们要做的第一个操作就是算出在节点8时不需要任何输入就可以到达的节点,这个操作称为closure,得到closure集合

  • move

之后我们就需要根据NFA和当前的输入字符来进行节点间的跳转,得到的自然也是一个集合

closure操作

我们利用一个栈来实现closure操作

  • 把传入集合里的所有节点压入栈中
  • 然后对这个栈的所有节点进行判断是否有可以直接跳转的节点
  • 如果有的话直接压入栈中
  • 直到栈为空则结束操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def closure(input_set):
if len(input_set) <= 0:
return None

nfa_stack = []
for i in input_set:
nfa_stack.append(i)

while len(nfa_stack) > 0:
nfa = nfa_stack.pop()
next1 = nfa.next_1
next2 = nfa.next_2
if next1 is not None and nfa.edge == EPSILON:
if next1 not in input_set:
input_set.append(next1)
nfa_stack.append(next1)

if next2 is not None and nfa.edge == EPSILON:
if next2 not in input_set:
input_set.append(next2)
nfa_stack.append(next2)

return input_set

move操作

  • move操作就是遍历当前的状态节点集合,如果符合的edge的条件的话
  • 就加入到下一个状态集合中
1
2
3
4
5
6
7
def move(input_set, ch):
out_set = []
for nfa in input_set:
if nfa.edge == ch or (nfa.edge == CCL and ch in nfa.input_set):
out_set.append(nfa.next_1)

return out_set

match

现在最后一步就是根据上面的两个操作进行字符串的分析了

  • 首先先计算出开始节点的closure集合
  • 开始遍历输入的字符串,从刚刚的closure集合开始做move操作
  • 然后判断当前的集合是不是可以作为接收状态,只要当前集合有某个状态节点没有连接到其它节点,它就是一个可接收的状态节点,能被当前NFA接收还需要一个条件就是当前字符已经全匹配完了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def match(input_string, nfa_machine):
start_node = nfa_machine

current_nfa_set = [start_node]
next_nfa_set = closure(current_nfa_set)

for i, ch in enumerate(input_string):
current_nfa_set = move(next_nfa_set, ch)
next_nfa_set = closure(current_nfa_set)

if next_nfa_set is None:
return False

if has_accepted_state(next_nfa_set) and i == len(input_string) - 1:
return True

return False

小结

这篇主要讲了复杂一点的NFA节点的构建方法,和对利用构造的NFA来对输入自负床进行分析。到目前为止,其实一个完整的正则表达式引擎已经完成了,但是如果想更近一步的话,还需要将NFA转换成DFA,再进行DFA的最小化