用自动机实现一个简易的正则表达式引擎

起因

这学期上了一门《计算机软件理论》的课，其实就是本科的《自动机与形式语言》的翻版。由于疫情的缘故，这门课从原来的笔试改成了大作业的形式，其中有一道题目就是让我们将正则表达式转换成自动机，并用自动机来判断输入的文本时候满足正则表达式的描述。写完之后觉得蛮好玩的，就决定写个博客记录一下。

BTW，这里只是实现了一个非常简易的版本。

理论

在这门课中证明了正则表达式与自动机的对应关系，可以通过递归构造的方式先将一个正则表达式转换为子表达式，然后构建子表达式对应的子自动机（或者说)，并通过一定的规则将这些子自动机连接成一个大的自动机。

不妨假设正则表达式中只有ab，a|b，a*三种运算（当然这里支持用括号嵌套）,不妨假设，a 和 b 对应自动机分别为：FA1 和 FA2，那么我们这三种运算所对应的链接方式分别为:

用自动机实现一个简易的正则表达式引擎-20200708220015-2020-07-08

用自动机实现一个简易的正则表达式引擎-20200708220206-2020-07-08

用自动机实现一个简易的正则表达式引擎-20200708220253-2020-07-08

利用上面的规则，我们就可以将正则表达式转换为一个，然后当读入输入的时候，我们就默认对输入进行判断，当然我们也可以先将转换为，在对输入进行判断。

实现

为了方便，我们先将连接操作ab转换为a-b：

ab转换为a-b的规则可以通过找规律得到，即当左边的字符不为(或|，且右边的字符不为*、)或|时，两个字符之间就是连接关系，应该加入-符号：

def addConcatOp(s):
    if len(s) == 0:
        return s
    output = s[0]
    for i in range(len(s) - 1):
        L, R = s[i], s[i+1]
        if L not in '(|' and R not in '*)|':
            output += '-'
        output += R
    return output

然后将正则表达式从中缀表示转换为后缀表示，这样在后面解析的时候会方便许，中缀转后缀只需要利用一个栈来记录操作即可搞定：

def infix2postfix(s):
    output = ''
    st = []
    for c in s:
        if c in '(|-':
            st.append(c)
        elif c == ')':
            assert(len(st) != 0)
            assert(st[-1] == '(')
            st.pop()
        else:
            output += c
            # print(st, c)
            if len(st) != 0 and st[-1] != '(':
                output += st[-1]
                st.pop()
    while len(st) != 0:
        output += st[-1]
        st.pop()
    return output

在实现正则表达式之前，我们先定义一下 State 和 NFA 的数据结构，我们在State中存储一个isEnd的 Flag 来记录是否为接收状态以及一个字典来记录跳转，为了实现空跳转，我们用一个特殊的字符串Epsilon来表示：

Epsilon = 'Epsilon'

class State:

    def __init__(self, isEnd = False):
        self.isEnd = isEnd
        self.next = {}

    def addNext(self, token, to):
        # print(self.next, token, to)
        if token not in self.next: 
            self.next[token] = []
        self.next[token].append(to)

NFA 的数据结构只需要记住一个开始状态和接收状态即可，记住开始状态就可以遍历出整个 NFA，而记住接收状态是为了后面连接 NFA 时方便操作，而之所以只有一个接收状态是因为如果有多个接收状态，可以通过空跳转将其转换成只有一个接收状态。因此其数据结构为：

class NFA:
    def __init__(self, start, end):
        self.start = start
        self.end= end

然后是就是正则表达式转换为 NFA 的过程，我们逐字符读取已经转成后缀表示的正则表达式：

如果读到一个字符，我们就构造一个start -- token --> end形式的 NFA，并将其压入栈中。
如果读到一个-或者|，我们就从栈中弹出两个 NFA，并按照上面提到的规则重新构造一个NFA，并将其压入栈中。
如果读到一个*，我们就从栈中弹出一个 NFA，并按照上面提到的规则构造一个NFA，并将其压入栈中。

最后在栈中留下来的 NFA 就是正则表达式对应的 NFA：

def re2nfa(pattern):
    st = []
    for c in pattern:
        if c == '|':
            assert(len(st) >= 2)
            nfa1, nfa2 = st[-2], st[-1]
            st.pop(), st.pop()
            st.append(NFA.OR(nfa1, nfa2))
        elif c == '-':
            assert(len(st) >= 2)
            nfa1, nfa2 = st[-2], st[-1]
            st.pop(), st.pop()
            st.append(NFA.CONCAT(nfa1, nfa2))
        elif c == '*':
            assert(len(st) >= 1)
            nfa = st[-1]
            st.pop()
            st.append(NFA.CLOSURE(nfa))
        else:
            st.append(NFA.BASIC(c))
    return st[-1]

其中，构造 NFA 的过程被封装到NFA类的静态方法中去了，其实现为：

class NFA:
    def __init__(self, start, end):
        self.start = start
        self.end= end
    
    @staticmethod
    def _initState():
        return State(), State(True)

    @staticmethod
    def BASIC(token):
        start, end = NFA._initState()
        start.addNext(token, end) # S -- token --> E
        return NFA(start, end)

    @staticmethod
    def OR(nfa1, nfa2):
        start, end = NFA._initState()
        
        start.addNext(Epsilon, nfa1.start) # S -- e --> NFA1
        start.addNext(Epsilon, nfa2.start) # S -- e --> NFA2
        nfa1.end.addNext(Epsilon, end)  # NFA1 -- e --> E
        nfa2.end.addNext(Epsilon, end)  # NFA2 -- e --> E

        nfa1.end.isEnd, nfa2.end.isEnd = False, False
        return NFA(start, end)
    
    @staticmethod
    def CONCAT(nfa1, nfa2):
        start, end = NFA._initState()
        
        start.addNext(Epsilon, nfa1.start) # E -- e --> NFA1
        nfa1.end.addNext(Epsilon, nfa2.start) # NFA1 -- e --> NFA2
        nfa2.end.addNext(Epsilon, end) # NFA2 -- e --> NFA1

        nfa1.end.isEnd = False
        nfa2.end.isEnd = False

        return NFA(start, end)

    @staticmethod
    def CLOSURE(nfa):
        start, end = NFA._initState()
        start.addNext(Epsilon,nfa.start) # S -- e --> NFA
        nfa.end.addNext(Epsilon,end) # NFA -- e --> NFA
        end.addNext(Epsilon, start) # E -- e --> S

        nfa.end.isEnd = False
        return NFA(start, end)

由于我们的 NFA 是一个，所以在使用它时需要大量进行求空闭包的操作，所以我们在实现match操作前，我们需要实现求闭包的操作。我们用一个队列来实现空跳转的遍历，然后返回遍历到的状态：

def GetEpsilonClosure(states):
		visited = set(states)
		q = deque(states)
		while len(q):
				state = q.popleft()
				for item in state.next.get(Epsilon, []):
						if item not in visited:
								q.append(item)
								visited.add(item)
		return visited

然后是match操作，就是根据读入的字符串来决定如何跳转，遍历完字符串之后再判断一下当前状态是否存在接收状态即可：

def match(self, s):
    states = set([self.start])
    for c in s:
        # Epsilon ->
        states = NFA.GetEpsilonClosure(states)
        nextStates = set()
        for state in states:
            for nextState in state.next.get(c, []):
                nextStates.add(nextState)
        states = nextStates
        if len(states) == 0:
            break
    states = NFA.GetEpsilonClosure(states)
    for state in states:
        if state.isEnd:
            return True
    return False

上面实现的部分已经可以实现一个支持a*,a|b,ab三种操作的正则表达式了，为了支持更多的特性，我们可以可以通过转换的方式，将其他操作转化为上面三种操作，如{a,b,c}可以转换为(a|b|c)，a+可以转换为aa*等。

同时，我们还实现了将 NFA 使用graphviz绘制成图片和到的转换的功能。

因为使用了graphviz库，所以需要先安装对应的包：

pip install graphviz

绘制的过程其实就是用广度优先遍历去遍历所有状态，在遍历的时候给这些状态标好序，同时记录所有跳转，然后在用graphviz绘制即可：

def toGraph(self, state_prefix='State'):
    dot = Digraph(name='nfa', format="png")
    dot.attr(rankdir='LR')
    state2index = {}
    q = deque()
    q.append(self.start)
    g = []

    while len(q):
        state = q.popleft()
        if state in state2index:
            continue
        state2index[state] = state_prefix + str(len(state2index))
        index = state2index[state]
        dot.node(name = index, label=index, shape= 'doublecircle' if state.isEnd else 'circle')
        for token, states in state.next.items():
            for nextState in states:
                g.append((state, token, nextState))
                q.append(nextState)

    # output
    for start, token, end in g:
        startIndex, endIndex = state2index[start], state2index[end]
        print('{} -- {} --> {}'.format(startIndex, token, endIndex))
        dot.edge(startIndex, endIndex, label=token)

    dot.node(name='start', label='S', shape="plaintext")
    dot.edge('start', state2index[self.start])

    dot.render(filename='nfa', directory='./')
    return state2index

因为在实现到的转换时需要先知道字母表，所以我们同样用遍历的方式得到字母表，同时构造一个状态到序号的字典，先给 NFA 的状态标序可以帮助我们给后面构造 DFA 时判断两个状态集合是否相同提供便利：

def geneState2Index(self, state_prefix='State', alphabet_flag = False):
    state2index = {}
    alphabet = []
    q = deque()
    q.append(self.start)

    while len(q):
        state = q.popleft()
        if state in state2index:
            continue
        state2index[state] = state_prefix + str(len(state2index))
        index = state2index[state]
        for token, states in state.next.items():
            if alphabet_flag:
                alphabet.append(token)
            for nextState in states:
                q.append(nextState)
    if alphabet_flag:
        return state2index, set(alphabet)
    return state2index

NFA 转 DFA 的基本原理就是 NFA 中一个状态集合对应与 DFA 中的一个状态，所以我们刚才生成的状态到序号的字典来生成 DFA 的序号，其实就是简单拼接字符串，只不过拼接前先做一次排序，我们将其写成一个函数hashfun，利用hashfun就可以将其 NFA 的状态集合映射成 DFA 的序号。我们通过递归的方式来生成 DFA，从 NFA 开始状态为初始的状态集合（当然这里要先求个克林闭包），调用递归函数GeneNewState：

通过hashfun来生成 DFA 中的序号，如果这个序号对应的 DFA 状态已经存在了（被记录在一个全局的字典中），我们就直接返回该状态。
如果不存在，我们就生成一个新的 DFA 状态与该序号对应起来，这个状态是否为接收状态通过输入的状态集合中时候存在接收状态来判断；然后遍历字母表中的所有字符来确定输入了这个字符后，当前状态集合会跳转到的状态集合next_states（别忘记了求克林闭包），然后对next_states递归调用GeneNewState，并将返回的状态与当前状态连接起来即可

实现代码如下：

def toDFA(self):
    state2index, alphabet = self.geneState2Index('', alphabet_flag=True)
    alphabet.remove(Epsilon)
    # print(alphabet)
    index2state = {}
    def hashfunc(states):
        return '#'.join(sorted(set([state2index[state] for state in states])))

    def statesIsEnd(states):
        for state in states:
            if state.isEnd:
                return True
        return False
    
    def GeneNewState(states):
        index = hashfunc(states)
        if index not in index2state:
            isEnd = statesIsEnd(states)
            new_state = State(isEnd)
            index2state[index] = new_state
            for c in alphabet:
                next_states = [] 
                for i_state in states:
                    next_states += i_state.next.get(c, [])
                next_states = NFA.GetEpsilonClosure(set(next_states))
                next_index = hashfunc(next_states)
                next_state = GeneNewState(next_states)
                next_state = index2state[next_index]
                new_state.addNext(c, next_state)
        return index2state[index]

    states = NFA.GetEpsilonClosure([self.start])
    start = GeneNewState(states)
    return NFA(start, None)

作者：wuxiaobai24
发表日期：7/8/2020
本文首发地址：用自动机实现一个简易的正则表达式引擎
版权声明：CC BY NC SA 4.0