正規表現エンジンを作ろう （2）

NFAとDFAを実装する

DFAの実装

DFAの内部表現を決める

　次に、DFAを実装します。こちらも、NFAと同様に数学的な定義を見てみましょう。

DFAの定義

　数学的には、DFAは以下の5つの要素で定義されます。

• 状態の集合（丸）
• 文字の集合（Unicode文字）
• 遷移関数（矢印）
  • 引数: 今の状態, 文字
  • 戻り値: 次の状態
• 開始状態（最初の矢印がさす丸）
• 受理状態の集合（二重丸）

　NFAと瓜二つの定義です。一見するとどこが違うか分からないかもしれませんが、よく見ると遷移関数の引数と戻り値が異なっています。

　NFAの持っていた非決定性と言うのは、矢印の引き方のルールについてDFAよりも縛りが少ないと言うことでした。矢印は遷移関数で表しているので、ここに違いが現れていると言うわけです。NFAにおいて、「空文字（ε）が許される」と言うルールは引数側に空文字が含まれていたこと、「同じアルファベットで任意の本数の矢印が引ける」と言うルールは戻り値が集合だったことで表現されています。

DeterministicFiniteAutomatonクラス

　それでは、定義を元にPythonコードでDFAを表現しましょう。遷移関数以外は同じなのですから、NondeterministicFiniteAutomatonクラスのフィールド定義がそのまま使えそうです。

　そして、NFAの時とは遷移関数の引数と戻り値が違うのでした。ところが残念ながら、Pythonでは関数の引数や戻り値の型を強制することはできません。よって、NFAの遷移関数もDFAの関数もfunction型であり、全く一緒の定義をすることになります。

　以上より、DFAクラスのフィールドは、NFAクラスの持つフィールドと全く同じとなります。なお、DFAでもNFAの時と同様に、「状態の集合」と「文字の集合」はフィールドから省いてあります。

DeterministicFiniteAutomatonクラス

class DeterministicFiniteAutomaton(object):
    def __init__(self, 
                 transition , # 遷移関数
                 start      , # 開始状態
                 accepts    , # 受理状態の集合
                 ):
        self.transition = transition
        self.start      = start
        self.accepts    = accepts

　DFAとNFAのtransitionフィールドの引数・戻り値の違いは、それぞれの動作をシミュレートする時に効いてきます。NFAをシミュレートする場合、DFAと違ってtransition関数が複数の状態を返してくるため、これらの状態を再帰的に実行する必要があります。このためNFAを実行するソースはDFAに比べてかなり複雑になります。

　ただし、今回はNFAを実行することはないので、NFAを実行するソースは実装しません。その代わり、NFAをDFAに変更して、そのDFAを実行すると言う手法をとります。次回以降の回でNFAをDFAに変換する作業を行いますが、その時にNFAのtransition関数を用いてDFAの状態遷移関数を構築します。この部分でtransitionフィールドの引数・戻り値の違いを気にする必要が出てきます。

DFAのシミュレーション

　DFAは正規表現エンジンの評価機として、実際に動作しなければなりません。いきなり「正規表現のエンジンを作りなさい」と言われると実装するのは大変ですが、幸い、DFAの動作をシミュレートするのはとても簡単です。

　実行部分として、DFARuntimeと言うクラスを作ります。DFARuntimeクラスはDFA定義（DeterministicFiniteAutomatonオブジェクト）を内部に保持し、このDFA定義の動作をシミュレートすることで、入力文字列が真か偽か（受理されるか）を判定します。

DFARuntimeに必要なフィールド

　第1回で述べた通り、DFAはある一瞬にとりうる状態はただ1つだけです。よって、DFAの実行に関して保持する情報は、現在の状態（整数値）をひとつだけで済みます。

DFARuntimeクラス(1)

class DFARuntime(object):
    def __init__(self, DFA):
        self.DFA = DFA
        self.cur_state = self.DFA.start

　DFA定義をself.DFA、現在の状態をself.cur_stateとしました。cur_stateは、DFAの「開始状態」で初期化しておきます。

文字を入力し、状態を遷移させる

　このDFAに、新たな1文字を入力する関数 do_transition を作ります。文字の入力があると、DFAは現在の状態 self.cur_state を「遷移関数」に基づいて変化させます。

DFARuntimeクラス(2)

    def do_transition(self, char):
        self.cur_state = self.DFA.transition(self.cur_state, char)

　transition関数を呼び、cur_stateを次の状態に変化させています。

文字列が受理されるか判定する

　このDFAが、文字列を受理するかを判定する関数 does_accept を実装します。do_transitionを何度も呼ぶのは大変なので、このようなショートカットを用意しました。

DFARuntimeクラス(3)

    def is_accept_state(self):
        return self.cur_state in self.DFA.accepts

    def does_accept(self, input):
        for alphabet in input:
            self.do_transition(alphabet)
        return self.is_accept_state()

　文字列を1文字ずつDFAに入力して行き、全ての文字列の入力が終わった状態で受理状態にあるかを判定します。

前方一致のマッチングの実装

　前方一致なマッチングを行うには、does_acceptメソッドの受理状態の判定を、全ての文字列入力後ではなく1文字入力する度に行います。途中で受理状態となった時は、先頭からそこまでの文字列がこのDFAが表現する正規表現にマッチした、ということを意味します。

DFAからDFARuntimeを得られるようにする

　最後に、DeterministicFiniteAutomaton オブジェクトからDFARuntimeを取得できるように、DeterministicFiniteAutomatonクラスにメソッドを追加します。

DFARuntimeの取得（DeterministicFiniteAutomatonクラス）

    def get_runtime(self):
        return DFARuntime(self)

　試しに動かしてみましょう。以下のコードを実行してみます。

DFARuntimeのテスト

# DFAを作る(-> 1 -a-> 2 -b-> [3])
def transition(stat, char):
    if stat == 1 and char == 'a': return 2
    if stat == 2 and char == 'b': return 3
    return 0

dfa = DeterministicFiniteAutomaton(
    transition,
    1,
    frozenset([ 3 ]),
)

# 'ab'と'ba'が受理されるか、DFAを動かしてみる
for str in (u'ab', u'ba'):
    runtime = dfa.get_runtime()
    if runtime.does_accept(str):
        print u"%sは受理されました。" % str
    else:
        print u"%sは受理されませんでした。" % str

# 結果
# abは受理されました。
# baは受理されませんでした。

　はい、予期した通り動作しているようです。

まとめ

　今回は、以下の内容を説明しました。

• NFAの実装
• DFAの実装
• DFAの動作のシミュレート

　次回は、正規表現文字列を構文木に変えるコンパイラを作成します。

参考資料

1. 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月