正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henｒy Spencer’s regex.

Presentation on theme: "正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henｒy Spencer’s regex."— Presentation transcript:

1 正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henｒy Spencer’s regex

2 GNU regex GNU Rx gawk、GNU grepなどで使用されている rubyの正規表現ルーチンはこれに修整を加えたものである
GNU　regexの置き換えを目指したもので、GNU sed（2.05）や Guile　などで使われている

3 pcre (Perl Compatible Regular Expression)
1.5以降のPythonで使われている Perlのものと同様の正規表現演算子をサポートしている ftp://ftp.cus.cam.ac.uk/pub/software/programs/pcres Henｒy Spencer’s regex Tcl等で使われている Perlで使っている正規表現ルーチンの基となった ftp://ftp.zoo.toronto.edu/pub/bookregexp.shar ftp;//ftp.zoo.toronto.edu/pub/regex.shar

4 その他 mawk ftp://ftp.whidbey.net/pub/brennan/

5 正規表現エンジンの一般的動作 入力として与えられた正規表現を内部表現の「バイトコード」に変換する
変換されたバイトコードとマッチ対象文字列を使ってマッチングを行う マッチングに使用するエンジンの種類には大きくNFAとDFAの二種類がある

6 正規表現ルーチンの多バイト 文字対応のポイント
一文字が1バイトであると決め打ちしない 多バイト文字をまたがってマッチしたりしない 多バイト文字の一部分のみにマッチしない []の中に多バイト文字がくることを考慮する 繰り返し(* , +, ?)の対象で泣き別れを起こさない

7 []の実装における違い serowさん方式 …単純列挙 t^2さん方式 …昇順に並べられた範囲のリスト
ビットベクター方式 …8bit幅256文字分のビットベクターを16bit幅に拡張する

8 op 文字 文字指定 範囲指定の上下限 範囲指定 serowさん方式 op 下限 上限 256ビットのベクター等 範囲指定の上下限 ・一文字分でも範囲指定を使用する ・上下限のペアは常にソートされた状態にする t^2さん方式

9 jperlでの正規表現実装例の詳細 オペコードに対応する 引数（あれば） オペコード 次のノードへのポインタ
上の図のようなノードを組み合わせたものが「コンパイル 済み正規表現」

10 パターンの例　　 /あ*/ compiling RE `あ*' size 7 first at 1 1: CURLYX {0,32767}(6) 3: EXACT <あ>(5) 5: WHILEM(0) 6: NOTHING(7) 7: END(0) minlen 0 Omitting $` $& $' support.

11 パターンの例その2　 /ab+/ compiling RE `ab+' size 6 first at 1 rarest char b at 0 rarest char b at 1 1: EXACT <a>(3) 3: PLUS(6) 4: EXACT <b>(0) 6: END(0) anchored `ab' at 0 floating `b' at (checking anchored) minlen 2 Omitting $` $& $' support.

12 jperlにおけるキャラクタークラスの実装
オリジナル op 次のノードへの ポインタ フラグ ビットベクター jperl op ビットベクターへのポインタ

13 今後の課題 UNICODE対応 (特にサロゲートペアの扱い) locale対応 (同一視する文字の環境による変化)