项目地址: 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_conn
- factor_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
- expr
- expr ::= 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
- group
group 其实就是在 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, 其它都是空
所以这个图表示的正则表达式 [0-9]*[a-z]+
假设对于分析字符串 123a
closure
从开始节点 8 进行分析, 我们要做的第一个操作就是算出在节点 8 时不需要任何输入就可以到达的节点, 这个操作称为 closure, 得到 closure 集合
move
之后我们就需要根据 NFA 和当前的输入字符来进行节点间的跳转, 得到的自然也是一个集合
closure 操作
我们利用一个栈来实现 closure 操作
把传入集合里的所有节点压入栈中
然后对这个栈的所有节点进行判断是否有可以直接跳转的节点
如果有的话直接压入栈中
直到栈为空则结束操作
- 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 的条件的话
就加入到下一个状态集合中
- 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 接收还需要一个条件就是当前字符已经全匹配完了
- 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 的最小化
来源: https://www.cnblogs.com/secoding/p/11579650.html