正規表現の実装(python)

前回の記事で作ったεNFAを使って正規表現を実装できたのでまとめます。ソースは前回と同じくこのリポジトリに。

実装した正規表現

正規表現のすべての機能を実装するのは大変なので、実装するのは基本的なものだけにしました。

実装したのは

一文字 (“a"など)
文字の連結 (“ab"など)
文字の和集合 (“(a|b)"など)
表現の繰り返し(“a*"など)
任意の一文字 (“."のこと)

のみです。教科書には定義に"Φ"(空文字列)がありましたが使い所がなさそうなので代わりに".“を実装しました。

“a+”(aの一回以上の繰り返し)や"(^a|b)“(aでもbでもない文字全て)などの機能は上の表現を組み合わせれば作れます。

他の特徴として入力される文字集合を指定しなければならないというのがあります。これは正規表現の都合というよりもこれまで作ってきたεNFAが文字集合がないと定義できないという都合のためです。

インターフェース

関数regex_to_eNFA()で正規表現をεNFAに変換し、eNFA.run()で文字列が正規表現にマッチするかどうかを調べます。

enfa = regex_to_eNFA("10*1", {"0", "1"})
enfa.run("101")   # -> True
enfa.run("10101") # -> False
enfa.run("10001") # -> True

実装の手順

正規表現をεNFAに変換するプログラムは大きく分けて3つの部分からなります。

正規表現を一つづつに分ける
一つづつに分けた正規表現をεNFAに変換する
変換されたεNFAをε遷移で繋いで一つのεNFAを作る

この部分をコードにすると

def regex_to_eNFA(string, alphabet):
    """ 正規表現stringを認識するeNFAを返す """
    return eNFA.serial_connect([single_regex_to_eNFA(single_regex, alphabet) for single_regex in concat_split(string)])

となります。一行にまとめているので読みにくいですが、concat_split()で正規表現を一つづに分け、single_regex_to_eNFA()で一つづつに分けた正規表現をεNFAに変換し、最後にeNFA.serial_connect()でεNFAを繋いでいます。

順に説明します。

concat_split()

concat_split()は正規表現を一つづつに分ける関数です。一つづつと言うのは連結されていないという意味です。例えば、"a(b|c)de“は["a”, “(a|b)”, “d”, “e”]と分かれます。

ここでの詰まったのは、処理を始める前に一番外側のはずせるカッコを外しておく必要がある点です。もしカッコを外さないと、例えば"(a(b|c)d)“という正規表現は[”(a(b|c)d)“]としか分解されず、無限ループに陥ってしまうからです。対策としてremove_outer_branket()を作り、これに通してから処理を始めるようにしました。

def remove_outer_branket(string):
    """ 一番外側のカッコが外せるなら外して、外せないならそのまま返す """
    if not (string[0] == "(" and string[-1] == ")"):
        return string

    blanket_count = 0
    for char in string[:-1]:
        if char == "(":
            blanket_count += 1
        elif char == ")":
            blanket_count -= 1
        if blanket_count == 0:
            return string
        if blanket_count == 1 and char == "|":
            return string
    return remove_outer_branket(string[1:-1])

def concat_split(string):
    """ 正規表現の連結stringを正規表現一つづつに切って返す """
    ans = []
    right = left = 0
    string = remove_outer_branket(string)
    while left < len(string):
        if string[left] == "(":
            blanket_count = 1
            while blanket_count > 0:
                left += 1
                if string[left] == "(":
                    blanket_count += 1
                elif string[left] == ")":
                    blanket_count -= 1
        if left + 1 < len(string) and string[left + 1] == "*":
            left += 1
        ans.append(string[right:left + 1])
        right, left = left + 1, left + 1
    return ans

テストしてみます。なおgituhubのソースではdoctestを使ってテストをコメントに書いています。改変したときにあってるかどうかがすぐに調べられて便利です。

>>> remove_outer_branket("(abc)")
'abc'
>>> remove_outer_branket("(((abc))")
'abc'
>>> remove_outer_branket("(a|b)(c|d)")
'(a|b)(c|d)'
>>> concat_split("ab")
['a', 'b']
>>> concat_split("a*")
['a*']
>>> concat_split("(abc)*(a|b|c)(cba)*abc")
['(abc)*', '(a|b|c)', '(cba)*', 'a', 'b', 'c']
>>> concat_split("...")
['.', '.', '.']
>>> concat_split("((a|A)(b|B)(c|C))")
['(a|A)', '(b|B)', '(c|C)']
>>> concat_split("((a|A)(b|B)(c|C))*")
['((a|A)(b|B)(c|C))*']

single_regex_to_eNFA()

single_regex_to_eNFA()は連結のない正規表現を受け取り、それを認識するεNFAを返す関数です。

連結のない正規表現は

一文字 (“a"など)
文字の和集合 (“(a|b)"など)
表現の繰り返し(“a*"など)
任意の一文字 (“."のこと)

のどれかなので、場合分けして処理します。

def is_dot(string):
    """ stringが任意の一文字を表す記号"."ならTrue """
    return string == "."

def is_atom(string):
    """ stringが通常の文字一つならTrue、それ以外はFalse """
    return True if len(string) == 1 and string not in "()|*." else False

def is_repeat(string):
    """ stringが"X*"ならTrue、それ以外はFalse """
    return len(string) > 1 and string[-1] == "*"

def is_union(string):
    """ stringが文字の集合を表す正規表現ならTrue """
    return string[0] == "(" and string[-1] == ")"

def single_regex_to_eNFA(string, alphabet):
    """ 一項からなる正規表現stringを認識するeNFAを返す """
    if is_dot(string):
        return eNFA.any_word(alphabet)
    if is_atom(string):
        return eNFA.one_word(string, alphabet)
    elif is_repeat(string):
        return eNFA.repeat(regex_to_eNFA(string[:-1], alphabet))
    elif is_union(string):
        return eNFA.parallel_connect([regex_to_eNFA(sub_regex, alphabet) for sub_regex in union_split(string)])
    else:
        assert False, "invalid regular expression: %s" % string

わかりやすいようにis_…()という関数を作っていますが、判定は文脈に依存しています。例えばis_union()は場合分けの最後に置かれなければ正しく動きません。なので関数にしなくても良かったかもしれません。

εNFAを作る関数

any_word(), one_word(), repeat(), parallel_connect(), serial_connact() は全てεNFAを作る関数です。一例としてserial_connect()を示し、解説は省略します。

def serial_connect(automaton):
    """ 複数のオートマトンを横並びに一つにまとめる """
    alphabet = set()
    states = set()
    transitions = {}
    for i, automata in enumerate(automaton):
        # alphabetを更新
        alphabet = alphabet.union(automata.alphabet)

        # statesを更新
        # 状態とautomataのインデックスを組にすることで唯一性を確保
        states = states.union(set([(i, state) for state in automata.states]))

        # automata内部の遷移をtransitionsに追加
        for final_state in automata.final_states:
            transitions[(i, final_state)] = {}
        for state, trans_dict in automata.transitions.items():
            transitions[(i, state)] = {}
            for char, states_transit_to in trans_dict.items():
                transitions[(i, state)][char] = frozenset([(i, state) for state in states_transit_to])

        # 一つ前のautomataからのイプシロン遷移を追加
        if i == 0:
            continue
        for pre_final_state in automaton[i - 1].final_states:
            transitions[(i - 1, pre_final_state)][-1] = frozenset([(i, automata.init_state)])

    # 始状態と終状態を作る
    init_state = (0, automaton[0].init_state)
    final_states = set([(len(automaton) - 1, f) for f in automaton[-1].final_states])
    return NFAWithEpsilonTransition(states, alphabet, transitions, init_state, final_states)

DFAへの変換と最小化

εNFAのDFAへの変換とDFAの最小化はこれまでに作ったので、正規表現から作ったεNFAを最小DFAに変換することができます。

これによって正規表現の性質が分かります。

>>> from Regex import regex_to_eNFA
>>> any = regex_to_eNFA("(0|1)*", {"0", "1"})
>>> any_mindfa = any.convert_to_DFA().minimized()
Automata
    states      : {{{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}}}
    alphabet   : {'0', '1'}
    transitions : {{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}} : {'0': {{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}}, '1': {{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}}}
    init_state  : {{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}}
    final_states: {{{(0, (0, (1, (0, 0)))), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (0, (0, 1))))}, {(0, 1), (0, -1), (0, (0, 1)), (0, (0, (0, (0, 0)))), (0, (0, (1, (0, 0))))}, {(0, -1), (0, (0, 1)), (0, (0, (1, (0, 1)))), (0, (0, (1, (0, 0)))), (0, (0, (0, (0, 0))))}}}

とても見にくいですが、よく見ればこのDFAは状態が一つしか無い、どんな文字列も認識するDFAだとわかります。正規表現"(0|1)“が表すのは任意の文字列なので、このDFAが正しく変換されていることがわかります。

最小DFAは全て同型なので、DFAが同型かどうかを判定する関数を作れば正規表現が同値かどうかを判定できるようになるはずです(やってないけど)。

またDFAの表記がみにくい問題については、DFAのコンストラクタで状態の名前を振り直す処理を加えればマシになるはずです。デバッグがしにくくなるので実装はしませんでしたが。

yukiのブログ

作ったものなど