CodeZineさんで第ニ回が公開されました。今回は最も底辺の部分である、NFAとDFAを実装しています。ただし、NFAの実行部に関しては以下の通り実装しませんでした。
このためNFAを実行するソースはDFAに比べてかなり複雑になります。
ただし、今回はNFAを実行することはないので、NFAを実行するソースは実装しません。
これを、実装してみましょう。第一回で述べた通り、NFAを評価するには２種類の方法があります。
なお、実行部分の取り出しはDFAと同様に、get_runtime()メソッドで行います。実装は二つあるので、お好みの方で。*1
def get_runtime(self): return NFARuntime(self) # return NFABacktrackRuntime(self)
幅優先
最初は、幅優先の方法です。これは、選択しうる状態を全て保持しながらシミュレーションを進めていき、最後にまとめて受理状態になりうる可能性があるのかを判定する方法です。DFAエンジンはこの方式で実行されます。
class NFARuntime(object): def __init__(self, NFA): self.NFA = NFA self.cur_states = self.NFA.epsilon_expand( frozenset([ self.NFA.start ]) ) def do_transition(self, char): next_states = set() for state in self.cur_states: next_states |= self.NFA.transition(state, char) next_states = self.NFA.epsilon_expand(next_states) self.cur_states = next_states def is_accept_state(self): for state in self.cur_states: if state in self.NFA.accepts: return True return False def does_accept(self, input): for alphabet in input: self.do_transition(alphabet) return self.is_accept_state()
DFARuntimeではcur_stateを保持していますが、NFARuntimeではこれがcur_statesと集合型になっていることに気をつけて下さい。NFAの遷移関数(transition)は集合を返すので、これの和集合をとりながら文字を受け取っていきます。
後、NFAでは普通のアルファベット意外に空文字での遷移を許すのでした。このルールを実現しているのが NFA.epsilon_expand() メソッドです。こいつは今後の連載で登場するメソッドで、以下のように実装されてます。
def epsilon_expand(self, set_): # 空文字を辿るべき状態を集めたキュー que = set( set_ ) # 辿り終わった状態 done = set() while que: # キューから取り出す stat = que.pop() # 空文字によって辿れる遷移を辿る nexts = self.transition(stat, "") # この状態は辿り終わったので、保存 done.add(stat) # 辿って出て来た状態を、さらに空文字で辿るのに、キューに居れる for next_stat in nexts: # 辿り終わってない要素だけ if not next_stat in done: que.add(next_stat) return frozenset( done )
深さ優先
バックトラックを使う方法で、NFAエンジンはこちらの方法で実現されます。幅優先では、1文字を読み込んだ時にとりうる可能性をすべて保持して次の文字に移りましたが、深さ優先では逆に、1つの可能性に着目し、他の可能性の検証を後回しにしてどんどん後続の文字を読んでいきます。
class NFABacktrackRuntime(object): def __init__(self, NFA): self.NFA = NFA self.cur_state = self.NFA.start self.left = None self.branches = set() self.done = set() def do_transition(self): # 文字列を読み終わったので、Falseを返す if self.left is None: return False # とりうる遷移 branches = set() # εを読む for state in self.NFA.transition(self.cur_state, u""): branches.add( (state, self.left) ) if self.left: # まだ読める字があるので、次の1文字を読む char, self.left = self.left[0], self.left[1:] for state in self.NFA.transition(self.cur_state, char): branches.add( (state, self.left) ) else: # 読める字がないので、読まずに終わる branches.add( (self.cur_state, None) ); # すでに辿った道を除く branches = set( filter(lambda x: x not in self.done, branches) ) if branches: # どの選択肢をとるか選ぶ self.cur_state, self.left = self._select(branches) # 残りはバックトラックできるように溜める self.branches |= branches else: # 遷移がもうない。状態をNoneにしておく self.cur_state, self.left = None, None return True def _select(self, branches): selected = branches.pop() self.done.add(selected) return selected def backtrack(self): if self.branches: self.cur_state, self.left = self._select(self.branches) return True else: return False def is_accept_state(self): return self.cur_state in self.NFA.accepts def does_accept(self, input): self.left = input while True: # 適当な経路でNFAを辿る while self.do_transition(): pass if self.is_accept_state(): # 受理状態についたので、受理。 return True elif self.backtrack(): # ダメだったのでバックトラックして別の経路へ continue else: # バックトラックできない。受理しない。 return False
NFABacktrackRuntimeでは、DFARuntimeと同様にcur_stateは集合ではなく整数型です。このことがマッチの過程をわかりやすくし、さまざまな拡張を許す要因となっています。
does_accept()メソッドに着目すると、深さ優先シミュレーションの仕組みがよくわかります。まず、どんな経路でもいいので*2遷移図の矢印を最後まで辿ります。で、成功したらラッキー、ダメだったらbacktrach()メソッドで別の選択肢に移って再度遷移図の矢印を辿ります。何度も試行錯誤して、全部の経路で駄目だった場合はマッチ失敗となります。
