NFA→DFA変換ルーチンをかく

きょうは正規表現とのマッチングに使用するルーチンをかきました。使用言語はC++。

正規表現ライブラリは いくつも つくられていて、Boost、GNU regex、PCREなど、たくさん あります。ただ、どれも これも わたしの したいことと すこし ずれているので、マッチング用のルーチンをかいた次第です。

• 入力を1回スキャンするだけで複数のパターンと照合し、どのパターンにマッチするか検出したい。


• マッチングで最長一致のパターンを検出するか、一致するパターンを全部検出するか、状況によって つかいわけたい。


• それぞれのパターンで部分文字列 (たとえば正規表現 a*(bc*)d における bc* の部分) を検出したい。

など、既存のライブラリと微妙に かみあいません。

部分文字列を厳密に検出できるように実装しようと すると厄介です。しかし、微妙な ばあいは正確に検出できないけれど実際には そのような微妙なパターン検出が必要なケースは ほとんど ないので実用上は問題ない、と いう程度まで検出能力を制限すれば容易に実装できそうです。今回は その方法を採用します。

きょう かいたのはNFA (非決定性有限オートマトン) をDFA (決定性有限オートマトン) に変換するルーチン。アルゴリズムは すでに確立されていて、NFAノード間のε遷移からεクロージャ (閉包) を構成し、それぞれの入力と遷移さきからDFAの状態遷移表を作成するだけです (実際には表をつくらずに分枝をのばしました)。順調にコーディングが すすんで動作確認完了。

このままでもオートマトンとして機能しますが、実行時に複数の分枝の なかから該当する分枝を検索して分岐していくのは効率が わるいです。コンパクトなジャンプテーブルをつくるルーチンだけ追加しておこうかな。

※ この記事の本文からは漢字の訓を排除しています。