直到栈为空则结束操作
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的最小化