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

DFAエンジンとNFAエンジン

　正規表現は、特に文字列操作が中心となるWEB分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第6回は、連載の最後のまとめとして、正規表現エンジンを実際に動かして動作を確認し、より一般的なNFAエンジンとの比較を行います。

はじめに

　こんにちは。hirataraです。

　前回までの連載で、正規表現エンジンが完成しました。今回は連載の最後のまとめとして、正規表現エンジンを実際に動かして動作を確認し、より一般的なNFAエンジンとの比較を行います。

対象読者

• 正規表現をもっと知りたい方
• 情報科学分野に興味がある方
• 正規表現エンジンを実装する必要がある方

必要な環境

　サンプルはPython2.5で開発しましたが、2.4の環境でも動くはずです。

• Python2.5 が動作する環境

　また、NFAエンジンを試しに動かす場合は、以下の環境が必要です。

• gcc, makeが動作する環境

正規表現を動作させる

　完成した手作り正規表現エンジンを実際に動かしてみましょう。サンプルファイルを用意していますので、これをダウンロードし、適当なディレクトリに展開して下さい。そして、setup.pyがあるディレクトリに移動し、pythonコマンドによってインタラクティブシェルを起動して下さい。

　まず、インタラクティブシェルで以下のように入力し、正規表現エンジンをロードします。

dfaregモジュールのimport

>>> import dfareg

　次に、正規表現をコンパイルします。今回は"(ABC*|abc*)*"としてみました。

正規表現のコンパイル

>>> reg = dfareg.compile(r"(ABC*|abc*)*")

　そして、この正規表現を利用して色々な文字列をマッチングしてみます。意図した通りの動作をしているでしょうか？

マッチングさせる

>>> reg.matches("ABC")
True
>>> reg.matches("ABBC")
False
>>> reg.matches("abcccABABC")
True
>>> reg.matches("abABAb")
False
>>> reg.matches("")
True

　コンパイルした正規表現は、ABCとabcを0個以上繰り返した物にマッチします。また、Cとcだけは0個以上の繰り返しが許されています。"ABBC"は、Bが繰り返されているのでマッチしません。また、"abABAb"は、大文字と小文字が混ざっているのでマッチしません。

　なお、今回作成した正規エンジンは全文一致のマッチングを行うことに注意して下さい。これが部分一致のマッチングですと、この正規表現は空文字列""とマッチするので、任意の文字列にマッチします。

　さて、実行結果を見る限り、この正規表現エンジンは意図した通りに動作しているようです。書いたコードは、コメント部分やテストを除けば300行強程度です。今回のような簡単なエンジンであれば、この程度の分量で実装できてしまいます。

DFAエンジンの動作の様子

　次に、この正規表現エンジンが、どのようにNFA、DFAを作っているかを見てみましょう。サンプルとして用意したソースコードには、debugモードを用意してあります。これを使って、NFAとDFAをdumpしてみます。

　なお、NFAとDFAのdumpはdump.pyで実装していますが、方法はかなり力技です。遷移関数transitionはfunction型ですので、このままでは可視化できません。そこで、開始状態から全てのUnicode文字列を再帰的に渡していって、実際にどのような遷移可能性があるのかを総当たりで追いかけています。

　では、dumpをしてみましょう。compileメソッドに、debug=1を渡すことでdebugモードとなります。試しに、'XY*Z'に対してどのようなNFA、DFAが構成されるかを見てみましょう。

XY*Zのdump

>>> reg = dfareg.compile(ur'XY*Z', debug=1)
[NFA]
開始 状態 1
        'X' -> 2
状態 2
        '' -> 5
状態 5
        '' -> 3
        '' -> 6
状態 6
        'Z' -> 7
状態 3
        'Y' -> 4
状態 4
        '' -> 3
        '' -> 6
受理 状態 7
[DFA]
開始 状態 1
        'X' -> 2-3-5-6
状態 2-3-5-6
        'Y' -> 3-4-6
        'Z' -> 7
受理 状態 7
状態 3-4-6
        'Y' -> 3-4-6
        'Z' -> 7

XY*Zのコンパイル結果(NFA)

XY*Zのコンパイル結果(DFA)

　ご覧の通り、NFAに比べてDFAの方がすっきりとした構成となっています。これは、NFAの段階では構成時に追加された空文字(ε)の遷移がたくさん存在するのに対し、DFAに変換された時にはこれらがすべて吸収されてなくなるからです。

DFAのdumpで表記を省略した部分

　第1回で、DFAではすべての文字に対して必ず1つ遷移先が存在すると述べました。しかし、このdumpでは簡単のため'X'と'Y'と'Z'といったように正規表現に登場する文字の遷移しか書かれていません。他の文字が来た場合はどのような状態に遷移するのでしょうか？

　構築されたDFAにおいて、dumpで表示されていない文字が入力されると、空集合を表す状態{}に遷移します。そして、状態{}では、どの文字が入力されても状態{}に遷移します。よって、一度でも想定しない文字が入力されると、受理状態に遷移することなくずっと状態{}に留まり続けます。

　さて、次はこの正規表現が文字列"XYYYZ"をどのように受理するか見てみます。matchesメソッドにdebug=1を渡して実行します。

XYYYZのマッチ

>>> reg.matches(u"XYYYZ", debug=1)
frozenset([1])
'X' -> frozenset([2, 3, 5, 6])
'Y' -> frozenset([3, 4, 6])
'Y' -> frozenset([3, 4, 6])
'Y' -> frozenset([3, 4, 6])
'Z' -> frozenset([7])
True

　先ほどのDFAのdumpと比較しながら実行結果を見て下さい。正規表現ではY*となっているので、この正規表現はYの繰り返しを受理しますが、この部分は状態3-4-6を繰り返すことで表現されています。

　ついでに、受理されない正規表現の例も見てみましょう。コラムに書いた通り、DFAでは意図されない文字が来た時点で、状態frozenset([])に落ちてしまい、そこから抜け出すことはできません。

XYZYZYZのマッチ

>>> reg.matches(u"XYZYZYZ", debug=1)
frozenset([1])
'X' -> frozenset([2, 3, 5, 6])
'Y' -> frozenset([3, 4, 6])
'Z' -> frozenset([7])
'Y' -> frozenset([])
'Z' -> frozenset([])
'Y' -> frozenset([])
'Z' -> frozenset([])
False