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

visited则是为了debug用来遍历NFA

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开始向下递归

group ::= ("(" expr ")")* expr ::= factor_conn ("|" factor_conn)* factor_conn ::= factor | factor factor* factor ::= (term | term ("*" | "+" | "?"))* term ::= char | "[" char "-" char "]" | .

BNF在之前写C语言编译器的时候有提到：从零写一个编译器（二）

主入口

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

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

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

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

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

# . 匹配任意单个字符 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

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分析输入的字符串