­

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

  • 2019 年 10 月 3 日
  • 筆記

项目地址：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的最小化

VirMach 便宜 VPS

QNews

QNews