有限状态自动机

Question

这是一种不确定的有限状态自动机(NFA)，用于Regex引擎。为了展示一些示例用法，假设您希望为regex (ad|[0-9])*构造一个NFA。它看起来可能是这样的：

ad_literal = NFA.from_string('ad')
number_set = NFA.from_set({str(x) for x in range(10)})
union = ad_literal.union(number_set)
final_nfa = union.kleene()
final_nfa.match('adbeadf')
>>> ad

我主要是希望有更好的组织和可读性的指点。我对公共活动的结果很满意，但似乎所有的帮手都有点混乱。我想也许有另一个类隐藏在某个地方，但由于它都是一个简单的包装列表，我看不出有什么地方可以划出界限。

import string


class DFA(object):
    def __init__(self, table, terminals):
        self._table = table
        self._terminals = terminals

    def match(self, pattern: str) -> str:
        match_string = ''
        state = 0
        last_match = ''
        for char in pattern:
            try:
                state = self._table[state][ord(char)]
                if state == -1:
                    return last_match
                if char in string.printable:
                    match_string += char
                if state in self._terminals:
                    last_match = match_string
            except KeyError:
                return last_match
        return last_match


class NFA(object):
    def __init__(self):
        self._initial_state = 0
        self._terminal_state = 0
        self._table = []
        self._dfa = None  # type: DFA

    def match(self, source: str) -> str:
        if not self._dfa:
            self._dfa = self.to_dfa()
        return self._dfa.match(source)

    def concat(self, other: 'NFA') -> 'NFA':
        new_nfa = NFA()
        new_nfa._table = [x.copy() for x in self._table]
        self._copy_table(other._table,
                         new_nfa._table,
                         lambda s: s + self._terminal_state)
        new_nfa._terminal_state = len(new_nfa._table)
        return new_nfa

    def kleene(self):
        new_table = [self._empty_row()]
        self._set_transition(new_table[0], '\0', {1, self._terminal_state + 1})

        self._copy_table(self._table, new_table, lambda s: s + 1)

        # Add null transition to new terminal state, or to beginning
        new_table.append(self._empty_row())
        self._set_transition(new_table[-1], '\0', {self._terminal_state + 2, 1})

        new_nfa = NFA()
        new_nfa._table = new_table
        new_nfa._terminal_state = self._terminal_state + 2
        return new_nfa

    def union(self, other: 'NFA'):
        new_terminal_state = self._terminal_state + other._terminal_state + 1
        new_table = [self._empty_row()]
        new_table[0][ord('\0')] = {1, self._terminal_state + 1}

        self._copy_table(self._table, new_table,
                         lambda s: new_terminal_state if s == self._terminal_state else s + 1)

        self._copy_table(other._table, new_table,
                         lambda s: (new_terminal_state if s == other._terminal_state
                                    else s + 1 + self._terminal_state))
        new_nfa = NFA()
        new_nfa._table = new_table
        new_nfa._terminal_state = new_terminal_state
        return new_nfa

    def to_dfa(self) -> DFA:
        characters = [chr(i) for i in range(128)]
        start_state = frozenset(self._epsilon_closure({self._initial_state}))
        dfa_states = self._collect_nfa_states(characters, start_state)

        nfa_to_dfa_state_map = {start_state: 0}
        for i, state in enumerate(dfa_states.difference({start_state})):
            nfa_to_dfa_state_map[state] = i + 1
        nfa_to_dfa_state_map[frozenset()] = -1

        # Just invert it
        dfa_to_nfa_state_map = {v: k for k, v in nfa_to_dfa_state_map.items()}

        dfa_table = [[-1 for _ in characters] for _ in dfa_states]
        for dfa_state in dfa_to_nfa_state_map:
            if dfa_state == -1:
                continue
            nfa_state = dfa_to_nfa_state_map[dfa_state]
            for char in characters:
                if char == '\0':
                    continue
                next_nfa_state = frozenset(self._epsilon_closure(self._next_states(nfa_state, char)))
                next_dfa_state = (nfa_to_dfa_state_map[next_nfa_state]
                                  if next_nfa_state in nfa_to_dfa_state_map
                                  else -1)
                dfa_table[dfa_state][ord(char)] = next_dfa_state

        terminal_nfa_states = {state for state in dfa_states if self._terminal_state in state}
        terminal_dfa_states = {nfa_to_dfa_state_map[state] for state in terminal_nfa_states}

        return DFA(dfa_table, terminal_dfa_states)

    def _collect_nfa_states(self, characters, start_state):
        dfa_states = {start_state}
        checked_dfa_states = set()
        while dfa_states:
            current_state = dfa_states.pop()
            new_states = set()
            for char in characters:
                next_state = frozenset(self._epsilon_closure(self._next_states(current_state, char)))
                checked_dfa_states.add(current_state)
                if next_state and next_state not in checked_dfa_states:
                    new_states.add(next_state)
            dfa_states.update(new_states)
        return checked_dfa_states

    def _next_states(self, states: {int}, char: str) -> {int}:
        result = set()

        for state in states:
            result.update(self._at(state, char))
        return result

    def _single_state_closure(self, state: int) -> {int}:
        return self._at(state, '\0')

    def _epsilon_closure(self, state: {int}) -> {int}:
        if not state:
            return set()
        to_check = state.copy()
        checked = set()
        closure = state.copy()
        iteration = set()
        while to_check:

            # Copy states to current iteration
            while to_check:
                iteration.add(to_check.pop())

            for state in iteration:
                next_states = self._single_state_closure(state)
                if state not in checked:
                    checked.add(state)
                    to_check.update(next_states)
                closure.update(next_states)

        return closure

    def _at(self, state: int, char: str):
        if state >= len(self._table):
            return set()
        return self._table[state][ord(char)]

    def _add_row(self, row_number):
        while row_number >= len(self._table):
            self._table.append(self._empty_row())

    def _add_transition(self, start_state: int, next_state: int, char: str) -> None:
        assert len(char) == 1
        if start_state >= len(self._table):
            self._add_row(start_state)
        self._table[start_state][ord(char)].add(next_state)

    @staticmethod
    def _empty_row():
        return [set() for _ in range(128)]

    @staticmethod
    def _set_transition(row: [set], character: str, states: {int}):
        row[ord(character)] = states

    @staticmethod
    def from_string(pattern: str) -> 'NFA':
        nfa = NFA()
        current_state = nfa._initial_state
        for char in pattern:
            nfa._add_transition(current_state, current_state + 1, char)
            current_state += 1
        nfa._terminal_state = len(pattern)
        return nfa

    @staticmethod
    def from_set(union: {str}) -> 'NFA':
        nfa = NFA()
        nfa._add_row(0)
        for char in union:
            nfa._table[0][ord(char)] = {1}
        nfa._add_transition(1, 2, '\0')
        nfa._terminal_state = 2
        return nfa

    @staticmethod
    def _copy_table(source, dest, state_function):
        for row in source:
            row_copy = []
            for state_set in row:
                row_copy.append({state_function(state) for state in state_set})
            dest.append(row_copy)

下面是一些更多的用法示例。下面是一些简单的单元测试：

import unittest
from automata import NFA


class TestNfa(unittest.TestCase):

    def test_union(self):
        nfa = NFA.from_string('abc')
        nfa = nfa.union(NFA.from_string('def'))

        self.assertEqual(nfa.match('abc'), 'abc')
        self.assertEqual(nfa.match('def'), 'def')
        self.assertEqual(nfa.match('de'), '')

    def test_kleene(self):
        nfa = NFA.from_string('abc')
        nfa = nfa.kleene()

        self.assertEqual(nfa.match(''), '')
        self.assertEqual(nfa.match('abc'), 'abc')
        self.assertEqual(nfa.match('abcabc'), 'abcabc')
        self.assertEqual(nfa.match('abcDabc'), 'abc')

    def test_concat(self):
        nfa = NFA.from_string('ab')
        nfa = nfa.concat(NFA.from_string('cd'))

        self.assertEqual(nfa.match('abcd'), 'abcd')
        self.assertEqual(nfa.match('abcde'), 'abcd')
        self.assertEqual(nfa.match('abc'), '')

下面是我的Regex类的一个(不可运行的)摘录，它显示了上下文中的用法：

def parse_basic_re(self):
    """
    <elementary-re> "*" | <elementary-re> "+" | <elementary-re>
    """
    nfa = self.parse_elementary_re()
    if not nfa:
        return None
    next_match = self._lexer.peek()
    if not next_match or next_match.token != Token.METACHAR:
        return nfa
    if next_match.lexeme == '*':
        self._lexer.eat_metachar('*')
        return nfa.kleene()
    if next_match.lexeme == '+':
        self._lexer.eat_metachar('+')
        return nfa.union(nfa.kleene())
    return nfa

Answer 1

谢谢你的测试，它使代码更容易理解。

(我的观点)我认为代码的构造和设计的最大问题是NFA()对象本身的重新设计。我相信，因为您是如何做到这一点的-它迫使您跳过某些圈，以使您的代码工作。通过阅读汤普森的“构造”和回顾分解成图表的正则表达式的例子，我认为结构应该简单得多。我会挑战你去学习一些图形和顶点的例子，然后回来尝试重新创建你的NFA/DFA。我相信您应该能够对代码进行相当大的改进。

在代码的各个部分:您有一个重复的循环(一个循环应该总是足够的)：

    while to_check:

        # Copy states to current iteration
        while to_check:

然后修改它在循环中检查的内容：

    while to_check:

        # Copy states to current iteration
        while to_check:
            iteration.add(to_check.pop())

这也不是好事。即使您使用的是copy功能，但您多次使用它的事实意味着您真的不明白数据构造器内部发生了什么。复制内容，然后删除内容的片段，然后在下面的语句修改(再次)为循环提供控件的变量时，比较(在第一次运行时)空集if state not in checked:。这是不好的-有一个混乱的数量的状态变化，在内部和外部循环。

(快速添加)

    def _single_state_closure(self, state: int) -> {int}:
        return self._at(state, '\0')

若要继续前面的代码，请执行以下操作：

            for state in iteration:
                next_states = self._single_state_closure(state)
                if state not in checked:
                    checked.add(state)
                    to_check.update(next_states)
                closure.update(next_states)

您对self._single_state_closure(state)的调用只在代码中的这一个位置执行(不值得使用单独的函数，如果人们在读取代码时不得不“弹出”，则会使人感到困惑)。另外，您的def _at(self, state: int, char: str)函数也只使用两次--一次使用硬编码值(如上面提到的_single_state_closure)，另一次在_next_states中找到的循环中使用。

虽然操作可能是相同的，但我认为最好将_at函数分解为它们在这些点上的单独语句，并丢弃_at函数。如果您这样做，将更容易理解代码。

最后，(我知道我已经跳过了很多)，您的def kleene(self):和def union(self, other: 'NFA'):函数非常相似--显然不是因为lambdas中的硬编码值(您肯定应该提取到一个单独的函数)，而是表状态的创建、表的复制、终端状态的修改--它们在功能上都是相同的(kleen和union)。

这意味着两者都可以在其中共享标准创建函数或修改函数(甚至如果您希望将其拆分并尝试坚持单一责任主体，则两者都可以共享)。

我希望这不会太让人困惑，我希望我和您一样理解您的代码。如前所述，请尝试使用python中的图形，然后从头开始编写这段代码。

祝好运!