正規表現エンジンを完成させる
まず、今回までに作った部品を振り返ってみましょう。過去の連載において、以下の部品を作製してきました。
第2回で説明した通り、今回の正規表現エンジンのインタフェースは以下のようになります。
# -*- coding: utf-8 -*- import dfareg regexp = dfareg.compile(r"(p(erl|ython|hp)|ruby)") if regexp.matches("python"): print u"pythonがマッチしました" if regexp.matches("ruby") : print u"rubyがマッチしました" if regexp.matches("VB") : print u"VBがマッチしました"
compile
を呼ぶとコンパイル済みの正規表現オブジェクトが返って来て、matches
メソッドでマッチングを行います。よって、compile
メソッドの戻り値である、正規表現オブジェクトの実装が必要です。
Regexpクラス
Regexp
クラスはコンパイル済みの正規表現です。この連載では、正規表現をDFAに変換していました。よって、Regexp
クラスはDFAを内部に持ち、ラップしたようなクラスになります。コンストラクタで正規表現をコンパイルし、コンパイルの結果生成されたDFAを内部に保持します。
コンストラクタ
コンストラクタは以下のようになります。
class Regexp(object): def __init__(self, regexp): self.regexp = regexp self.dfa = None self._compile() def _compile(self): # コンパイル lexer_ = Lexer(self.regexp) parser_ = Parser(lexer_) nfa = parser_.expression() # 部分集合構成法 self.dfa = nfa2dfa(nfa)
入力された正規表現は、regexp
フィールドに念のため保存しておきます。そして、_compile
メソッドにおいてこの正規表現のコンパイルを行っています。コンパイルには、第3回で作ったコンパイラを使います。まず、字句解析機であるLexer
オブジェクトを作成し、トークンが得られるようにします。これを構文解析機であるParser
オブジェクトに渡します。最後に、文法規則の開始記号にあたるexpression
メソッドをParser
オブジェクトに対して呼び出すことで、構文木の作成とNFAへの変換を実行させます。
NFAが作成されたら、これを今回実装した部分集合構成法により、DFAに変換します。部分集合構成法に関しては、nfa2dfa
関数を呼ぶだけです。
マッチング
コンパイル済みの正規表現に対して、文字列のマッチングを指示するメソッドであるmatches
メソッドを実装します。
def matches(self, string): runtime = self.dfa.get_runtime() return runtime.does_accept(string)
第2回で実装した、DFAの動作をシミュレートさせるメソッドを利用します。まず、コンパイル済みのDFAからget_runtime
メソッドによってDFARuntime
オブジェクトを取り出します。そして、does_accept
メソッドによってstringがこのDFAに受理されるかどうか、チェックしてそのままマッチング結果として返却します。
仕上げ
これが最後の工程です。当初予定していたインタフェースに合うように、compile
メソッドを用意します。これは、以下のようにRegexp
オブジェクトを作って返すだけです。
def compile(regexp): return Regexp(regexp)
これで、正規表現エンジンが完成しました。
まとめ
今回は、以下の内容を説明しました。
- NFAからDFAを作る
- 部分集合構成法
- 正規表現エンジンの完成
次回はこの正規表現エンジンを実際に動かし、NFAエンジンと比較をしてみます。
参考資料
- 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月