 |
 |
| ホーム | 主筆 | その他ソフト | その他情報 | Syuhitu.org | English |
Windows関連
Solaris関連
画像入出力
その他アルゴリズムなど
正規表現ライブラリSRegex
俺は現在テキストエディタを開発している。結構がんばったおかげで、最近何とかなってきた感じもする。そんな中、ある機能を実装しようとして、はたと困った。
「正規表現」の機能を実装したいが、使えるライブラリがねぇぞ。
実はWindwosAPIには正規表現を実現するための物はない。
しかし、Unix系、少なくともSolarisには標準で利用できる正規表現ライブラリが添付されている。それに、ForteC++にはもっと強力（だと思う）な、RoguWaveとか言うライブラリがついている。 当然、それにも正規表現ライブラリが含まれている。 たとえ、そうでなかったとしても、世の中には有用な正規表現ライブラリが溢れているように見える。
（余談だが、ANSIの規格ではCのライブラリに正規表現ライブラリが含まれることとなっているらしい。 そのため、Borland C++ Compiler 5.5.1では使用できるようになっている。 しかし、なぜか、Visual C++ 6.0では使えないようだ。 最近の奴ではどうなんだろう？）
しかし、よく見てもらいたい。
世の中に存在する正規表現ライブラリのほとんどが「文字列は文字型の配列で実装されていること」を前提としている。つまり、検索対象の文字列とし て「const char*」を引数にとるのだ。（もっとも、BoostのRegex++なら型を指定することができるが。）
だが、それでは使えないのだ。
俺のテキストエディタの内部では、文字列は「文字配列のリスト」で管理している。 また「文字列操作」での考察のように、単純な文字配列では都合が悪い場合もある。 よって、「const char *」な文字列しか受け付けないのでは役に立たないのだ。
そもそも、俺はこう見ても国際人だから（笑）、全ての文字に「wchar_t」を使用するようにしている。 その時点で対応していない物がほとんどなのである。
そう、亜糞利加人は極度に頭が悪いため、一文字を表現するのに２〜４バイト程度必要になる、ということが理解できないのだ。
それは違うだろう。
そもそも、正規表現ライブラリたるものは、「正規表現のアルゴリズム」のみを実装すべき物であって、処理されるべきデータのデータ型には依存する べきではないはずだ。
極端なことを言えば、「文字列」が「list< wchar_t >」 で実現されていたとしても、正規表現のアルゴリズムを適応する上では何の支障も無いはずである。 それなのに、それなのに、世の中の連中は。
たとえ、「文字列」がリストで実現されていたとしても、
パターンマッチングに変化はないはずである。
それにまだ言いたいことがある。
それは、正規表現の記述法だ。何が一番最初なんだか詳しいことは知らないが、通例、以下のような表記をする。
| X | 文字X |
| . | 任意の一文字 |
| X* | ０回以上の文字Xの繰り返し |
| X+ | １回以上の文字Xの繰り返し |
| [XYZ] | 文字クラスの指定 |
| X|Y | X又はY |
| (XYZ) | 正規表現のグループ化。物によっては前方参照。 |
これを見る限りでは特に問題があるようには思われない。しかし、よくよく考えると、俺には不自然な感じがしてくる。
それは、*や+の扱いだ。
つまり、*や+の出現により指定された文字が複数回繰り返しうることを示しているのだが、それが分かるのは、繰り返され いるパターンが出現した後なのだ。
つまり、正規表現を先頭から順に処理していった場合、*や+を読んだときにはすでに当該のパターンは処理し終わっている、ということになるのだ。これに対する対処法は、適切なところまで戻って再度処理し直すか、確実に繰り返されないとはっきりするまで態度を保留するか、するしかない。
後ろから前に修飾する。
それに、繰り返す文字は常に一文字と限った事ではないと思う。通常、複数文字が繰り返す場合には()を使うのだが、それは不自然で冗長な様な気がする。
つまり、繰り返しの範囲をカッコを使って表現するべきなのではないかと思う。
と、言うことで、正規表現ライブラリも自力で実装しなくてはならなくなってしまった。
で、作ったのがこんな感じ。
で、一応、このライブラリの使用方法がこれ。
ちょっと長いし、猛烈にきたねぇコードだが、一応解説しておく。
基本的な設定方針として以下の通り、
- テンプレートにすることで、「一文字」を示すデータ型、および「文字列」を示すデータ型に依存しない構造とする。また、「正規表現のパターン」と「マッチング対象の文字列」とのデータ型が異なっていても問題ないものとする。ただし、比較する都合上「一文字」を示すデータ型は同じとさせてもらった。
- 極力簡単な構造とする。よって、機能をできるだけ削る。
- NFAを使用する。これは、DFAに変換する手間を省くためである。
という感じだ。
で、まずは、仕様の説明。
テンプレートにして、徹底的に型を抽象化する、ということはもう良いとして、今気になるのは「正規表現として受け付けるパターンの仕様」だ。それ は、だいたい以下のようにしてみた。
X 文字X (X) 演算子の優先順位の変更 (^X) 演算子の優先順位の変更＆前方参照する正規表現グループ X|Y or [X] 文字クラスの指定 [^X] 文字クラスの指定（否定） {X} 0回以上の繰り返し（怠惰なマッチ） {^X} 0回以上の繰り返し（貪欲なマッチ） \xnnnn 文字コードによる文字の指定。nは16進数（0からf）。最大4桁。 \znnnn マッチしたn番目の前方参照を行う正規表現グループ。nは16進数（0からf）。最大4桁。 機能を単純化するにしても、なぜ、上記の機能を実装することにしたかというと、
- まぁ、括弧とorと繰り返しは必要だろうと思う。
- 繰り返しには怠惰な奴と貪欲な奴があるが、これは、どちらかの演算子を使用して、もう一方を実現するというわけにはいかないから、両方とも実装する必要がある。
- 文字クラスは、括弧とorを組み合わせれば実現できるが、やはり表記しにくいのと処理効率的に気になる事から、実装することにした。
- 前方参照も、ほかの演算子を複数組み合わせて実現するのは困難なため、実装する必要がある。
というところだ。でも、こんな自己中な仕様にしちまったが、業界標準に逆らうのもどうかと思うが？という疑問も生じる。だが、それ はこうすればいいだろう。まず、業界標準に従った正規表現を受け付け、それを上述の自己中な正規表現に変換するということだ。
変換処理を施すことで、
「業界標準」な正規表現を受け入れるようにする。
必要最低限な機能を実装してさえいれば、上記の方法でうまくいくはずである。また、下記に記述するような問題を、上記の変換処理で解決する（ある いは緩和する）事も可能である。
と、言うことで、予測されうる問題について。
このライブラリは、上の方でも言ったがNFAを使用している。そのため、下記のような正規表現とテキストが入力されたときに問題が生じる。
正規表現 {^.}{^.}{^.}{^.}{^.}a テキスト bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb 詳しい挙動については記述しないが、こんな正規表現が入力されると、ライブラリは、各「{^.}」について、考えられ る全ての組み合わせを試すこととなる。よって非常に処理時間がかかることとなる。まぁ、こんな意味のないパターンを入力する方が悪いのだ が、なにぶんユーザは何を考えてんだか解ったモンじゃない、という前提に立って考えると、やはり何らかの対処をしておきたいものだ。
対処法としては、「時間がかかるようなら途中で止められるようにする」というのがある。まぁ、この機能はいずれにせよ 必須になるだろうが、ここではもう少し前向きに検討してみたい。
では、どんな対処が考えられるのだろうか。世の中の偉いおっさん連中はいろいろ考えてんだろうが、とりあえず、俺はこ う考えてみた。つまり、「問題のあるパターンを修正し、同じ挙動をする別のパターンに修正してしまえばいい」という方法だ。
で、どんなパターンが問題なのかを考えてみると、同じパターンの繰り返しが連続するのがいけないと解 る。それを元に考察を進めると、パターンを置き換える方法が見えてくる。
出現した正規表現 説明 置き換え後の正規表現 説明 {^パターン}{^パターン}{^パターン} パターンの貪欲なマッチが連続する。 {^パターン} パターンの貪欲なマッチ一つに置き換える。 {^パターン}{パターン}{^パターン} パターンの貪欲なマッチと怠惰なマッチが混ざったものが連続する。 {^パターン} パターンの貪欲なマッチ一つに置き換える。 {パターン}{パターン}{パターン} パターンの怠惰なマッチが連続する。 {パターン} パターンの怠惰なマッチ一つに置き換える。 だが、これの裏をかく方法も考えられる。たとえば、
正規表現 {^.}b{^.}b{^.}b{^.}b{^.}a テキスト bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb とされると、問題が解決できなくなってしまう。だが、この問題を単純に解決する方法は、俺のおつむには浮かばない。やはり、究極的な解決法は DFAにするしかなさそうだ。
でもまぁ、いいか。
閑話休題、使用方法
設計方針はまぁいいとして、とりあえず、ライブラリの使用方法も示した方が良いだろう。
ちょっとしたテスト用のプログラム
とりあえず、まずはヘッダファイル「SRegex.h」をインクルードする。そうすることでSRegexが使用できるようになる。
次に、このライブラリは名前空間「N_SRegex」中で定義されている。だから、どこかで「using namespace N_SRegex;」とするか、なんとかして欲しい。
で、実際に使うためにはSRegexクラスのインスタンスを生成する必要がある。その際には、テンプレートの引数を指定しなくてはならない。
SRegex< T_Char, T_Ptn, T_Text >
で、次に、正規表現のパターンを指定して、NFAを構築させる。それが、以下のメソッド
bool Initialize( T_Ptn パターン )
成功すれば真を返す。失敗すれば偽を返す。失敗した際の原因は以下のメソッドで取得できる。
SREGEX_ERR GetLastError() const;
また、エラーが発生した位置を知るには、以下のメソッドを使用する。
T_Ptn GetErrorPos() const;
で、実際のパターンマッチには、以下のメソッドを使用する。
bool FindMatchStr( T_Text pText, T_Text *ppSPos, T_Text *ppEPos ) const;
また、指定したテキストがマッチするか否かを判断するだけにしたい場合は以下のメソッドを使用する。
bool Match( T_Text pText, T_Text *ppEPos ) const;
では次に、このライブラリを応用することを考えてみる。
くどいようだが、このライブラリの最大の特徴は、データ型に依存しないことだ。 よって、T_CharやT_Ptn、T_Textに、ユーザ定義のデータ型を指定することもできる。
と、言うことで。 「大文字・小文字を同一視したマッチング」行ってみる。
#pragma warning( disable : 4786 ) #include <stdio.h> #include <locale.h> #include <wchar.h> #include <mbstring.h> #include "SRegex.h" // T_Charに指定するクラス。 // 一文字を示す。 // なお、operaotr ==で、 // 大文字・小文字に依存しない比較を行うようにする。 class tagCHAR { public: // wchar_tを受け付けるコンストラクタ tagCHAR( wchar_t argc ) : c( argc ){}; // コピーコンストラクタ tagCHAR( const tagCHAR &r ) : c( r.c ){}; // デフォルトコンストラクタ・一応必要になる。 tagCHAR() : c ( '\0' ){}; // 問題の比較演算子 bool operator ==( const tagCHAR &r ) const { return towlower( c ) == towlower( r.c ); }; // 一応必要となる。 const tagCHAR& operator =( const tagCHAR &r ) { c = r.c; return (*this); }; protected: wchar_t c; }; // wchar_t*のラッパ // tagCHAR*のポインタに見せかける。 class tagCHAR_P { public: tagCHAR_P( const wchar_t *argp ) : p( argp ){}; tagCHAR_P( const tagCHAR_P &r ) : p( r.p ){}; tagCHAR_P(): p( NULL ){}; // 一応必要となる。 tagCHAR operator *() const { return tagCHAR( *p ); }; const tagCHAR_P& operator ++() { p++; return (*this); }; bool operator ==( const tagCHAR_P& r ) const { return p == r.p; }; const tagCHAR_P& operator =( const tagCHAR_P& r ) { p = r.p; return (*this); }; // マッチング結果を表示するために必要となる。 const wchar_t* GetPtr() const { return p; }; protected: const wchar_t *p; }; int main() { setlocale( LC_ALL, "" ); // SRegexのオブジェクト N_SRegex::SRegex< tagCHAR, tagCHAR_P, tagCHAR_P > regex; // 正規表現のパターンを保持する wchar_t Pattern[1024]; // 検索対象の文字列を保持する wchar_t Text[1024]; tagCHAR_P wp1, wp2; while ( -1 ) { // 正規表現のパターンを入力する printf( "Pattern : " ); wscanf( L"%s", Pattern ); // SRegexのオブジェクトを初期化 regex.Initialize( Pattern ); if ( regex.GetLastError() != N_SRegex::SRE_NON ) { // 失敗した wprintf( L"0x%08X : \"%s\"\n", regex.GetLastError(), regex.GetErrorPos().GetPtr() ); continue; } // 検索対象のテキストを入力する printf( "Text : " ); wscanf( L"%s", Text ); // 検索する if ( !regex.FindMatchStr( Text, &wp1, &wp2 ) ) { // 見つからなかった wprintf( L"%s\n", L"Not Match" ); } else { // 見つかった wprintf( L"%.*s\n", wp2.GetPtr() - wp1.GetPtr(), wp1.GetPtr() ); } } return 0; }一応、実行結果を示すと、
となる。上記のプログラムを元に、tagCHARやtagCHAR_Pを変更すれば、もっと複雑なデータ構造の「文字列」とのマッチングを行うことも可能となる。
では、最後に、このページの最初の方で言った、リストで実現した「文字列」とのマッチングを行ってみる。
#pragma warning( disable : 4786 ) #include <stdio.h> #include <locale.h> #include <wchar.h> #include <list> // SRegexのライブラリをインクルード #include "SRegex.h" using namespace std; int main() { setlocale( LC_ALL, "" ); // SRegexのオブジェクト N_SRegex::SRegex< wchar_t, const wchar_t*, list< wchar_t >::iterator > regex; // 検索するパターン const wchar_t *Pattern = L"ABC{^.}XYZ"; // 検索対象の文字列を保持する list< wchar_t > text; list< wchar_t >::iterator wp1, wp2; // 検索対象の文字列（文字のリスト）を構築する。 text.push_back( L'O' ); text.push_back( L'P' ); text.push_back( L'A' ); text.push_back( L'B' ); text.push_back( L'C' ); text.push_back( L'Q' ); text.push_back( L'R' ); text.push_back( L'S' ); text.push_back( L'X' ); text.push_back( L'Y' ); text.push_back( L'Z' ); text.push_back( L'T' ); text.push_back( L'U' ); text.push_back( L'\0' ); // 必ず必要 // regexの初期化 if ( !regex.Initialize( Pattern ) ) return 0; // 検索する if ( !regex.FindMatchStr( text.begin(), &wp1, &wp2 ) ) return 0; // 見つかった範囲を表示する while ( wp1 != wp2 ) { putwchar( *wp1 ); wp1++; } putwchar( L'\n' ); return 0; }既存のライブラリを使った場合、たぶん、こんなトンチンカンなパターンマッチングは実現できないだろう。しかし、これをやったところで何が嬉しいのかは、正直言って俺にも判らない。