連載第五回にして、ようやく正規表現エンジンが完成しました。それとも、逆にあっけなく完成してしまって拍子抜けと言ったほうがいいでしょうか？？(笑) こんなに簡単に実装できたのは、今回のエンジンではキャプチャを実装してないことが大きいでしょう。キャプチャを実装するとなると、同時に「最長一致*1」を実現しなければならなくなりますので、実装は複雑になります。
さて、今回作ったエンジンはDFAエンジンでしたが、こちらのエントリで作った深さ優先のNFA評価器を使うと、NFAエンジンもどきを作ることができます。
今回のコードは全てCodeRepos上にありますので、試したい方はダウンロードして以下のdiffを適用して下さい。一言で言えば部分集合構成法をやめただけで、他のコードは一緒です。
--- dfareg/__init__.py (revision 25809) +++ dfareg/__init__.py (working copy) @@ -4,14 +4,13 @@ ---------------------------------------- Author: hiratara <hira.tara@gmail.com> """ -import nfa2dfa from parser import Parser from lexer import Lexer class Regexp(object): def __init__(self, regexp, debug=False): self.regexp = regexp - self.dfa = None + self.fa = None self._compile(debug) def _compile(self, debug=False): @@ -19,17 +18,14 @@ lexer_ = Lexer(self.regexp) parser_ = Parser(lexer_) nfa = parser_.expression() - # 部分集合構成法 - self.dfa = nfa2dfa.nfa2dfa(nfa) + self.fa = nfa if debug: - from dump import dump_nfa, dump_dfa + from dump import dump_nfa print "[NFA]" dump_nfa(nfa) - print "[DFA]" - dump_dfa(self.dfa) def matches(self, string, debug=False): - runtime = self.dfa.get_runtime(debug) + runtime = self.fa.get_runtime(debug) return runtime.does_accept(string) def compile(regexp, debug=False):
こいつを実行してみると、以下のようになります。試行＆バックトラックしながら正答に行き着いてる様子が見られます。
>>> import dfareg >>> r = dfareg.compile("a*a", debug=1) [NFA] 開始 状態 3 '' -> 1 '' -> 4 状態 4 'a' -> 5 受理 状態 5 状態 1 'a' -> 2 状態 2 '' -> 1 '' -> 4 >>> r.matches("aaa", debug=1) -''->4 -'a'->5 [failed!] backtracked: status=1, left=aaa -'a'->2 -''->1 -'a'->2 -''->1 -'a'->2 [failed!] backtracked: status=4, left= [failed!] backtracked: status=1, left= [failed!] backtracked: status=4, left=a -'a'->5 True >>> r.matches("aab", debug=1) -''->4 -'a'->5 [failed!] backtracked: status=1, left=aab -'a'->2 -''->1 -'a'->2 -''->1 [failed!] backtracked: status=4, left=b [failed!] backtracked: status=4, left=ab -'a'->5 [failed!] False
これでNFAエンジンっぽくなりましたが、この動きには一般的なNFAエンジンと大きく異なる部分があります。それが、最初に述べた「最長一致マッチをしてない」と言う点です。このエントリでのバックトラックの実装は、特にポリシーを持たずに適当に選択肢を選びます。が、キャプチャをきちんと実装するには、「最長一致となる選択肢を優先する」と言う動作が必要となります。
上記を含めた一般的なNFAエンジンの動きについては、次回、連載の最終会で説明します。
*1:greedy match
