きょうは正規表現とのマッチングに使用するルーチンをかきました。使用言語はC++。
正規表現ライブラリは いくつも つくられていて、Boost、GNU regex、PCREなど、たくさん あります。ただ、どれも これも わたしの したいことと すこし ずれているので、マッチング用のルーチンをかいた次第です。
部分文字列を厳密に検出できるように実装しようと すると厄介です。しかし、微妙な ばあいは正確に検出できないけれど実際には そのような微妙なパターン検出が必要なケースは ほとんど ないので実用上は問題ない、と いう程度まで検出能力を制限すれば容易に実装できそうです。今回は その方法を採用します。
きょう かいたのはNFA (非決定性有限オートマトン) をDFA (決定性有限オートマトン) に変換するルーチン。アルゴリズムは すでに確立されていて、NFAノード間のε遷移からεクロージャ (閉包) を構成し、それぞれの入力と遷移さきからDFAの状態遷移表を作成するだけです (実際には表をつくらずに分枝をのばしました)。順調にコーディングが すすんで動作確認完了。
このままでもオートマトンとして機能しますが、実行時に複数の分枝の なかから該当する分枝を検索して分岐していくのは効率が わるいです。コンパクトなジャンプテーブルをつくるルーチンだけ追加しておこうかな。
※ この記事の本文からは漢字の訓を排除しています。
正規表現ライブラリは いくつも つくられていて、Boost、GNU regex、PCREなど、たくさん あります。ただ、どれも これも わたしの したいことと すこし ずれているので、マッチング用のルーチンをかいた次第です。
- 入力を1回スキャンするだけで複数のパターンと照合し、どのパターンにマッチするか検出したい。
- マッチングで最長一致のパターンを検出するか、一致するパターンを全部検出するか、状況によって つかいわけたい。
- それぞれのパターンで部分文字列 (たとえば正規表現 a*(bc*)d における bc* の部分) を検出したい。
部分文字列を厳密に検出できるように実装しようと すると厄介です。しかし、微妙な ばあいは正確に検出できないけれど実際には そのような微妙なパターン検出が必要なケースは ほとんど ないので実用上は問題ない、と いう程度まで検出能力を制限すれば容易に実装できそうです。今回は その方法を採用します。
きょう かいたのはNFA (非決定性有限オートマトン) をDFA (決定性有限オートマトン) に変換するルーチン。アルゴリズムは すでに確立されていて、NFAノード間のε遷移からεクロージャ (閉包) を構成し、それぞれの入力と遷移さきからDFAの状態遷移表を作成するだけです (実際には表をつくらずに分枝をのばしました)。順調にコーディングが すすんで動作確認完了。
このままでもオートマトンとして機能しますが、実行時に複数の分枝の なかから該当する分枝を検索して分岐していくのは効率が わるいです。コンパクトなジャンプテーブルをつくるルーチンだけ追加しておこうかな。
※ この記事の本文からは漢字の訓を排除しています。
