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

NFAをDFAに変換し、正規表現エンジンを完成させる

正規表現エンジンを完成させる

　まず、今回までに作った部品を振り返ってみましょう。過去の連載において、以下の部品を作製してきました。

• DFAとNFA（第2回）
• NFAを作るコンパイラ
  • 字句解析（第3回）
  • 構文解析（第3回）
  • 構文木（第4回）
• 部分集合構成法（dfa2nfa関数）（今回）

　第2回で説明した通り、今回の正規表現エンジンのインタフェースは以下のようになります。

dfaregモジュールのインタフェース（再掲）

# -*- 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を内部に保持します。

コンストラクタ

　コンストラクタは以下のようになります。

Regexpクラス（1）

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メソッドを実装します。

Regexpクラス（2）

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オブジェクトを作って返すだけです。

dfareg/__init__.py

def compile(regexp):
    return Regexp(regexp)

　これで、正規表現エンジンが完成しました。

まとめ

　今回は、以下の内容を説明しました。

• NFAからDFAを作る
• 部分集合構成法
• 正規表現エンジンの完成

　次回はこの正規表現エンジンを実際に動かし、NFAエンジンと比較をしてみます。

参考資料

1. 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月