本文将介绍简易正则转nfa的一个python实现。

前置知识

• python
• 编译原理

简易正则转NFA实现

简介

  NFA，即非确定性有限状态自动机。他将文本匹配转化为状态的转移，给予初态与终态。当一串文本随着输入，能成功从初态转换到终止状态，即为匹配成功。并且由于其为非确定型，相同的文本匹配模式，可能存在的NFA形态会很多。
  正则表达式，即一串用于描述文本匹配规则的文本。通过特殊字符组合成规则字符串，用于过滤文本。
  本项目将实现使用python，将简易正则，即包含连接运算，克林星号运算，或操作运算的正则表达式，转换到等价NFA的过程。

NFA实现

  状态机本身相当于图，包含边集与点集。由于我们不需要实际进行匹配，只需要转换，因此可以省略部分点，只保留起点与终点。但我们需要展示所有边，因而边不可以省略。
  根据上述描述，我们来定义类：

class NFA:

    def __init__(self,ch):
        self.head = 1
        self.tail = 2
        self.lines = [[1,ch,2]]

  初始化方法，起点与终点，初始化的边。我们便拥有了一个最简单的NFA。在此基础上，我们再来实现相应运算功能。

连接操作
  连接操作最为简单。我们只需要将第二个NFA起点连接到第一个NFA终点即可。注意结点序号问题。我们需要标识每个结点，这时候只需要将接在后面的NFA的每个结点的序号增加前NFA节点个数-1的数量即可。

def and_NFA(self,NFA_b):
    NFA_b.add_num(len(self)-1)
    for line in NFA_b.lines:
        self.lines.append(line)
    self.tail = NFA_b.tail

或运算操作
  或运算稍为复杂，但也不难。或运算相当于将两个NFA并联起来。我们只需要增加头节点，尾结点，再在中间并联两个NFA即可。同样，注意结点序号问题。

def or_NFA(self,NFA_b):
    self.add_num(1)
    NFA_b.add_num(len(self)+1)
    for line in NFA_b.lines:
        self.lines.append(line)
    self.lines.append([1,'~',self.head])
    self.lines.append([1,'~',NFA_b.head])
    self.lines.append([self.tail,'~',NFA_b.tail+1])
    self.lines.append([NFA_b.tail,'~',NFA_b.tail+1])
    self.tail = NFA_b.tail+1
    self.head = 1

克林星号运算
  克林星号运算所表示的NFA并不复杂。它表示前面的字符可以匹配0次或者多次。这里我们需要有一个循环的思想。即起点可以直接跳到终点，终点也可以直接跳到起点。那么增加两条边即可。

def kleen_NFA(self):
    self.lines.append([self.head,'~',self.tail])
    self.lines.append([self.tail,'~',self.head])  

  由于我们只实现简易正则，实现三个运算即可。在完成NFA方法构建后，我们来关注正则的解析问题。

正则表达式解析

  正则的解析如同计算器一样，需要符号栈与文本栈，并且要处理优先级问题。但我们只实现了三种运算，优先级问题并不困难。
  对于克林运算，我们可以直接对文本栈顶进行运算。它的优先级最高。
  对于连接运算，我们需要放入符号栈，等待遇到或运算清理栈时候来处理。
  对于或运算，当检测到或时候，我们可以将栈顶的连接运算全部清空，直到遇到或运算或者左括号为止。再放入符号栈。
  对于括号运算，左括号直接进入符号栈，右括号则清理文本栈，直到遇到左括号为止。
  当算法结束后，若文本栈未规约完成，则继续弹出两个文本与一个符号，进行运算，直至规约完成。
  对于上述规则，我们可以得到代码.此处连接使用点来代替。calculate函数代表将符号作用于文本栈：

def parse(s):
    sign_stack = []
    nfa_stack = []
    for ch in s:
        if ch=='(':
            sign_stack.append(ch)
            
        elif ch == ')':
            while len(sign_stack) != 0 and sign_stack[-1] != '(':
                tmp = sign_stack[-1]
                sign_stack.pop()
                nfa_stack[-2] = calculate(tmp,nfa_stack[-2],nfa_stack[-1])
                nfa_stack.pop()
        elif ch == '*':
            nfa_stack[-1] = calculate(ch,nfa_stack[-1],None)
        elif ch == '|':
            while len(sign_stack) != 0 and sign_stack[-1] == '.':
                sign_stack.pop()
                nfa_stack[-2] = calculate('.',nfa_stack[-2],nfa_stack[-1])
                nfa_stack.pop()
            sign_stack.append(ch)
        elif ch == '.':
            sign_stack.append(ch)
        else :
            nfa_stack.append(NFA(ch))
    while len(nfa_stack)>1:
        ch = sign_stack[-1]
        sign_stack.pop()
        nfa_stack[-2] = calculate(ch,nfa_stack[-2],nfa_stack[-1])
        nfa_stack.pop()
    return nfa_stack[0]

One more thing
  最后一个问题。在默认的正则表达式中没有连接运算符。我们可以硬编码一下增加连接运算符的规则，然后将原来的表达式转换为可以解析的表达式。

def RegexToNFA(s):
    ret = s[0]
    for i in range(1,len(s)):
        pre = s[i-1]
        now = s[i]
        if isCharacter(pre) and isCharacter(now):
            ret +='.'
            ret += now
        elif isCharacter(pre) and now == '(':
            ret +='.'
            ret += now
        elif pre == ')' and isCharacter(now):
            ret +='.'
            ret += now
        elif pre == '*' and isCharacter(now):   
            ret +='.'
            ret += now
        elif pre == '*' and now == '(':
            ret +='.'
            ret += now
        else :
            ret += now
    print(ret)
    return parse(ret)

  规则阐述不必多说。上述可能有遗漏，欢迎指正。

总结

  本文提供了一个简单正则转NFA的python实现。之所以使用python是因为写着简单，数据结构随意。在最开始我想拿scheme写，但api还是不熟悉。最后选用了python。
  本文技术含量不高，纯粹为课堂记录。