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

はじめに

　こんにちは。hirataraです。

　前回は、正規表現文字列をコンパイルし、構文木を作成する部分までを実装しました。今回は各正規表現の演算がどのようにNFAで表現されるかを解説し、この構文木をInterpreterパターンに対応させます。

対象読者

• 正規表現をもっと知りたい方
• 情報科学分野に興味がある方
• 正規表現エンジンを実装する必要がある方

NFA変換のための道具作り

　前回の記事により、入力文字列から構文解析を終えた構文木を作ることができました。今手にしている構文木は、例えば以下のような物です。

a|(bc)*の構文木（図）（再掲）

Union(
    Character('a'), 
    Star(
        Concat(
            Character('b'), 
            Character('c')
        ) 
    ) 
)

　次のステップでは、この構文木がInterpreterパターンに対応するよう、各ノードにassembleメソッドを実装します。ツリーを潜りながらこのメソッドを再帰的に呼ぶことで、NFAへの変換を実現します。

　実装に入る前に、まずは組み立てに必要な道具を揃えましょう。各ノードから共通して使われるクラスである、ContextクラスとNFAFragmentクラスを導入します。

Contextクラス

　Contextクラスは、NFAの変換時に共有する情報のコンテナです。NFAを作成するには、状態を表す整数値を一意に生成する必要があります。そこで、Contextオブジェクト内の_state_countフィールドに整数値を保持し、generate_stateメソッドでカウントアップしながら一意の値を生成します。

class Context(object):
    def __init__(self):
        self._state_count = 0

    def new_state(self):
        self._state_count += 1
        return self._state_count

NFAFragmentクラス

　NFAFragmentは、NFAの構成部品となるクラスです。NFAの一部分を表現しており、自由に組み合わせて繋げられる部品です。また、buildメソッドを呼ぶことで、第２回で実装したNondeterministicFiniteAutomatonオブジェクトに変換することが可能です。

　以後の説明では、以下の図をNFAFragmentインスタンスのイメージとして利用します。

フラグメント

　四角で囲まれている部分がNFAFragmentを表します。外から矢印が向いている丸が初期状態で、二重丸で示されているのが受理状態です。初期状態は一つですが、受理状態は複数存在しうるので、図中では2つ書いています。その他の状態の丸や遷移の矢印は、この表記においては省略しています。

コンストラクタとフィールド定義

　以下がNFAFragmentが持つフィールドです。

class NFAFragment(object):
    def __init__(self):
        self.start   = None  # æ•´æ•°åž‹
        self.accepts = None  # frozensetåž‹
        self.map     = dict()

　NondeterministicFiniteAutomatonクラスと同様に、初期状態を表すstartと受理状態の集合を表すacceptsをフィールドとして持っています。NFAを表すにはあともう一つ、遷移関数が必要でした。NFABuilderはNFAの組み立てに使う部品なので、自由に変更をしやすいことが求められます。そこで、変更をしにくいfunction型としてではなく、代わりに変更が容易なdict型を利用して遷移関数を表します。self.mapが、この遷移関数に該当します。

　self.mapは、(状態, 入力文字)のタプルをキーとし、次に遷移する状態の集合を値として持ちます。これはちょうどNFAの遷移関数の引数と戻り値と一致する定義になってますので、self.mapã‚’nfa.transitionの関数の形に変更するのは簡単です。

フラグメントの演算

　次に、フラグメントの組み立てに必要なメソッドを作ります。

　まずは、connectメソッドです。このメソッドは、2つの状態from_とtoを受け取り、文字charによってこの2つの状態を接続します。もっと具体的に言うと、フラグメントの遷移関数に、from_からcharによってtoへ遷移する遷移を付け加える、と言うことです。

　遷移関数は dict型のmapフィールドによって表現されていますので、ここに該当する遷移を表すエントリーを追加することで遷移矢印の追加を実現できます。

    def connect(self, from_, char, to):
        slot = self.map.setdefault( (from_, char), set() )
        slot.add(to)

　次に、new_skeltonメソッドですが、このメソッドはフラグメントの新しい骨組みを作るのに使います。このメソッドを呼ぶと、現在のフラグメントと同じ状態と遷移関数を持つフラグメントが生成されます。ただしこのメソッドでは、初期状態（start）と受理状態（accepts）はコピーしませんので、自分で設定する必要があります。

    def new_skelton(self):
        # コピーして返す
        new_frag = NFAFragment()
        new_frag.map = deepcopy(self.map)
        return new_frag

　最後に、 特殊メソッドである__or__を定義しています。この定義により、2つのフラグメントfragment1とfragment2を、 | 演算子に よってfragment1 | fragment2のように合成することができます。合成されてできる新しいNFAFragmentは、fragment1とfragment2の遷移関数を併せた遷移関数を持ちます。ただし、この演算も先ほどのnew_fragmentメソッドと同様に、初期状態と受理状態はコピーしません。

    def __or__(self, frag):
        new_frag = self.new_skelton()
        for k, v in frag.map.iteritems():
            new_frag.map[k] = v.copy()

        return new_frag

　この演算を遷移図で考えると、矢印を保持したまま2つのフラグメントを1つの遷移図中に移すと言うことを表します。ただしこの時点ではまだ、2つのフラグメントを結ぶ矢印は存在していません。 | 演算子で合成した後、それぞれのフラグメント間をまたぐ２つの状態に対してconnectメソッドを呼ぶことで、2つのフラグメントを合体させることができます。

フラグメントからNFAを作成

　最後に、組み立て終わってからNFAを作成するメソッドであるbuildメソッド の実装です。

    def build(self):
        map_ = self.map
        def transition(state, char):
            return frozenset(map_.get( (state, char), []))

        return nfa.NondeterministicFiniteAutomaton(
            transition,
            self.start,
            self.accepts
            )

　NFAFragmentオブジェクトは、NondeterministicFiniteAutomatonオブジェクトと同様にstart、acceptsを持っていますので、これはこのままNondeterministicFiniteAutomatonクラスのコンストラクタへ渡します。遷移関数は、dict型からfunction型に変換する必要があります。これは、self.mapフィールドを内部に保持するtransitionと言う名前のクロージャとして実装しています。中を見てわかるように、引数をそのままmapフィールドのキーとして使い、mapフィールドのバリュー値を戻り値として返却するだけの単純な関数です。