はじめに
こんにちは。hirataraです。
前回は、正規表現文字列をコンパイルし、構文木を作成する部分までを実装しました。今回は各正規表現の演算がどのようにNFAで表現されるかを解説し、この構文木をInterpreterパターンに対応させます。
対象読者
- 正規表現をもっと知りたい方
- 情報科学分野に興味がある方
- 正規表現エンジンを実装する必要がある方
NFA変換のための道具作り
前回の記事により、入力文字列から構文解析を終えた構文木を作ることができました。今手にしている構文木は、例えば以下のような物です。
![構文木](http://cz-cdn.shoeisha.jp/static/images/article/3158/tree_s.gif)
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
メソッドを呼ぶことで、第2回で実装したNondeterministicFiniteAutomaton
オブジェクトに変換することが可能です。
以後の説明では、以下の図をNFAFragmentインスタンスのイメージとして利用します。
![フラグメント](http://cz-cdn.shoeisha.jp/static/images/article/3039/NFAFragment.png)
四角で囲まれている部分が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つのフラグメントを結ぶ矢印は存在していません。 | 演算子で合成した後、それぞれのフラグメント間をまたぐ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
フィールドのバリュー値を戻り値として返却するだけの単純な関数です。