正規表現エンジンin Python(3)を実現

プロジェクトアドレス:Regex in Python
前の2編はすでに完成して1つのNFAの正規表現のエンジンに基づいて書いて、以下は更に1歩近くして、NFAをDFAに変換して、そしてDFAに対して最小化します
DFAの定義
NFAをDFAに変換するアルゴリズムでは,主にNFAで可能な状態ノードを統合し,さらに状態ノードに入力文字に対して一意のジャンプノードを持たせる.
したがって、DFAのノードには、nfa状態ノードのセットと、受信状態であるか否かを一意に識別するflagとが含まれる

class Dfa(object):
    STATUS_NUM = 0

    def __init__(self):
        self.nfa_sets = []
        self.accepted = False
        self.status_num = -1

    @classmethod
    def nfas_to_dfa(cls, nfas):
        dfa = cls()
        for n in nfas:
            dfa.nfa_sets.append(n)
            if n.next_1 is None and n.next_2 is None:
                dfa.accepted = True

        dfa.status_num = Dfa.STATUS_NUM
        Dfa.STATUS_NUM = Dfa.STATUS_NUM + 1
        return dfa

NFAからDFAへの変換
NFAをDFAに変換する最終的な目標は、以前のC言語でコンパイルされた構文解析テーブルに似ているジャンプテーブルを得ることです.
この関数はNFAがDFAに変換するすべてのアルゴリズムで、主な論理は:

以前のclosureアルゴリズムを用いて、統合可能なNFAノードを算出した後、DFAのノード

を生成する.

そしてこのDFA集合を

遍歴する

以降、入力文字毎にmove操作を行い、得られたmoveセットに対してもう一度closure操作を行うことで、次のDFA状態ノード(ここでは、現在のDFA状態ノードが既に生成する可能性がある)

を得ることができる.

その後、これら2つのノードの対応関係をジャンプテーブル

に入れる.

このときのDFAに含まれるNFAに受信可能な状態ノードが存在する場合、現在のDFAの当然のことながら

を受け入れることができる.

def convert_to_dfa(nfa_start_node):
    jump_table = list_dict(MAX_DFA_STATUS_NUM)
    ns = [nfa_start_node]
    n_closure = closure(ns)
    dfa = Dfa.nfas_to_dfa(n_closure)
    dfa_list.append(dfa)

    dfa_index = 0
    while dfa_index < len(dfa_list):
        dfa = dfa_list[dfa_index]
        for i in range(ASCII_COUNT):
            c = chr(i)
            nfa_move = move(dfa.nfa_sets, c)
            if nfa_move is not None:
                nfa_closure = closure(nfa_move)
                if nfa_closure is None:
                    continue
                new_dfa = convert_completed(dfa_list, nfa_closure)
                if new_dfa is None:
                    new_dfa = Dfa.nfas_to_dfa(nfa_closure)
                    dfa_list.append(new_dfa)
                next_state = new_dfa.status_num
            jump_table[dfa.status_num][c] = next_state
            if new_dfa.accepted:
                jump_table[new_dfa.status_num]['accepted'] = True
        dfa_index = dfa_index + 1
    
    return jump_table

DFA最小化
DFA最小化は本質的には状態ノードのマージであり,次いでパーティション化である.

は、まず、受信状態であるか否かに基づいてパーティション

を行う.

は、DFAジャンプテーブルのジャンプ関係に基づいてパーティション内のノードを再パーティション化し、現在のDFAノードのジャンプ後のステータスノードも同じパーティションに存在する場合、1つのパーティション

に分類できることを証明する.

上記のアルゴリズム

を繰り返す
Dfaパーティション定義
DfaGroupは以前の定義と大同小異であり,いずれも一意の識別とDFA状態ノードを配置するlistである.

class DfaGroup(object):
    GROUP_COUNT = 0

    def __init__(self):
        self.set_count()
        self.group = []

    def set_count(self):
        self.group_num = DfaGroup.GROUP_COUNT
        DfaGroup.GROUP_COUNT = DfaGroup.GROUP_COUNT + 1

    def remove(self, element):
        self.group.remove(element)

    def add(self, element):
        self.group.append(element)

    def get(self, count):
        if count > len(self.group) - 1:
            return None
        return self.group[count]

    def __len__(self):
        return len(self.group)

Minimize DFA
partitionはDFAアルゴリズムを最小化する最も重要な部分である.

は、現在のDFAに対応するジャンプの次の状態ノード

をジャンプテーブルから先に見つける.

firstは、比較のためのDFAノード

である

nextノードの次の状態とfirstノードの次の状態が同じパーティションでない場合、それらは同じパーティション

ではいけないことを示す.

は、新しいパーティション

を再作成します.
だからDFAを最小化するのは同じ次のジャンプ状態のノードを統合することです

def partition(jump_table, group, first, next, ch):
    goto_first = jump_table[first.status_num].get(ch)
    goto_next = jump_table[next.status_num].get(ch)

    if dfa_in_group(goto_first) != dfa_in_group(goto_next):
        new_group = DfaGroup()
        group_list.append(new_group)
        group.remove(next)
        new_group.add(next)
        return True

    return False

ジャンプテーブルの作成
再分割後はノードとノード間のジャンプがゾーンと区間のジャンプになります

DFA集合

を巡る

は、前のジャンプテーブルから対応するノードと対応するジャンプ関係

を見つける.

は、その後、対応するパーティションを見つける、すなわち、パーティションとパーティションとの間のジャンプ

に変換する.

def create_mindfa_table(jump_table):
    trans_table = list_dict(ASCII_COUNT)
    for dfa in dfa_list:
        from_dfa = dfa.status_num
        for i in range(ASCII_COUNT):
            ch = chr(i)
            to_dfa = jump_table[from_dfa].get(ch)
            if to_dfa:
                from_group = dfa_in_group(from_dfa)
                to_group = dfa_in_group(to_dfa)
                trans_table[from_group.group_num][ch] = to_group.group_num
        if dfa.accepted:
            from_group = dfa_in_group(from_dfa)
            trans_table[from_group.group_num]['accepted'] = True

    return trans_table

入力文字列の一致
ジャンプテーブルによる入力文字列のマッチングのロジックは非常に簡単です

入力文字列を巡る

現在の状態に対応する入力のジャンプ関係

を取得する.

ジャンプまたはマッチング

完了

def dfa_match(input_string, jump_table, minimize=True):
    if minimize:
        cur_status = dfa_in_group(0).group_num
    else:
        cur_status = 0 
    for i, c in enumerate(input_string):
        jump_dict = jump_table[cur_status]
        if jump_dict:
            js = jump_dict.get(c)
            if js is None:
                return False
            else:
                cur_status = js
        if i == len(input_string) - 1 and jump_dict.get('accepted'):
            return True

    return jump_table[cur_status].get('accepted') is not None

まとめ
これで、単純な正規表現エンジンのすべてのプロセスが完了しました.
正規表現->NFA->DFA->DFA最小化->マッチング