项目地址：Regex in Python
在看一下之前正则的语法的 BNF 范式
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 的构造
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 再生成两个节点进行连接
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
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
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_connfactor_conn ::= factor | factor factor*
对于 factor_conn 就是一个或者多个 factor 相连接，也就是说如果有多个 factor，只要将它们的头尾节点相连接
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 exprexpr ::= factor_conn ("|" factor_conn)*
对于 expr 就是一个 factor_conn 或者多个 factor_conn 用|相连接
构建|的 NFA 就是生成两个新节点，新生成的头节点有两条边分别连接到 factor_conn 的头节点，对于两个 factor_conn 的尾节点分别生成一条边连接到新生成的尾节点
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 groupgroup 其实就是在 expr 上加了两个括号，完全可以去掉
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，其它都是空
假设对于分析字符串123a
closure
从开始节点8进行分析，我们要做的第一个操作就是算出在节点8时不需要任何输入就可以到达的节点，这个操作称为closure，得到closure集合
move
之后我们就需要根据NFA和当前的输入字符来进行节点间的跳转，得到的自然也是一个集合
closure操作我们利用一个栈来实现closure操作
把传入集合里的所有节点压入栈中
然后对这个栈的所有节点进行判断是否有可以直接跳转的节点
如果有的话直接压入栈中