正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henry Spencer’s regex
GNU regex GNU Rx gawk、GNU grepなどで使用されている rubyの正規表現ルーチンはこれに修整を加えたものである GNU regexの置き換えを目指したもので、GNU sed(2.05)や Guile などで使われている
pcre (Perl Compatible Regular Expression) 1.5以降のPythonで使われている Perlのものと同様の正規表現演算子をサポートしている ftp://ftp.cus.cam.ac.uk/pub/software/programs/pcres Henry Spencer’s regex Tcl等で使われている Perlで使っている正規表現ルーチンの基となった ftp://ftp.zoo.toronto.edu/pub/bookregexp.shar ftp;//ftp.zoo.toronto.edu/pub/regex.shar
その他 mawk ftp://ftp.whidbey.net/pub/brennan/
正規表現エンジンの一般的動作 入力として与えられた正規表現を内部表現の「バイトコード」に変換する 変換されたバイトコードとマッチ対象文字列を使ってマッチングを行う マッチングに使用するエンジンの種類には大きくNFAとDFAの二種類がある
正規表現ルーチンの多バイト 文字対応のポイント 一文字が1バイトであると決め打ちしない 多バイト文字をまたがってマッチしたりしない 多バイト文字の一部分のみにマッチしない []の中に多バイト文字がくることを考慮する 繰り返し(* , +, ?)の対象で泣き別れを起こさない
[]の実装における違い serowさん方式 …単純列挙 t^2さん方式 …昇順に並べられた範囲のリスト ビットベクター方式 …8bit幅256文字分のビットベクターを16bit幅に拡張する
op 文字 文字指定 範囲指定の上下限 範囲指定 serowさん方式 op 下限 上限 256ビットのベクター等 範囲指定の上下限 ・一文字分でも範囲指定を使用する ・上下限のペアは常にソートされた状態にする t^2さん方式
jperlでの正規表現実装例の詳細 オペコードに対応する 引数(あれば) オペコード 次のノードへのポインタ 上の図のようなノードを組み合わせたものが「コンパイル 済み正規表現」
パターンの例 /あ*/ 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.
パターンの例その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 1..2147483647 (checking anchored) minlen 2 Omitting $` $& $' support.
jperlにおけるキャラクタークラスの実装 オリジナル op 次のノードへの ポインタ フラグ ビットベクター jperl op ビットベクターへのポインタ
今後の課題 UNICODE対応 (特にサロゲートペアの扱い) locale対応 (同一視する文字の環境による変化)