脳log[正規表現: 2009-06-28～]

最終更新: 2009-10-28T01:40+0900

♪ [正規表現][Firefox] .NETの正規表現の再帰について(20080111p01の補足)。

再帰っていっていいのかな？鬼車は明らかに再帰だったけど。

.NETの正規表現を利用した経験はありません(念のため)。想像です。

.NETの再帰に関係した部分のドキュメントがあまりにわかりにくかったので整理。(実はわかりにくさの半分は日本語のせいだった。英語の方のドキュメントを読みましょう)

 1.スタックされる名前付きキャプチャグループ: (?<name1>……), (?'name1'……)

キャプチャ内容を読み出す従来の記法が \1, \2。名前付きキャプチャの場合は \k<name1>, \k'name1'など(実装ごとに異なる)。キャプチャグループに量指定子がくっついている場合、これらで読み出せるのは最後のキャプチャ内容だけ。だけどキャプチャの記憶領域はキャプチャグループごとに一つではなくスタックになっていて、その一番上の内容を読み出していると考える(.NETだか Javaだかではプログラムからこのスタックにアクセスできたはず)。

 2.名前付きキャプチャ name1のスタックを POPする: (?<name2-name1>……)

まず、これは name2という名前付きキャプチャグループ。と同時に、name1のキャプチャスタックを POPする。name2を省略して name1を POPするだけも可能。MSDNの日本語ドキュメントを名前の部分だけこちらに合うように書きかえたのが次。

既に定義されていたグループ name1 の定義を削除し、既に定義されていた name1 グループと現在のグループの間隔をグループ name2 に格納します。

実際に name2のキャプチャ内容がどういうものになるのか(直前の name1のキャプチャ内容、name2の……にマッチした部分、その間、がそれぞれ含まれるのかどうか)は読み取れないけど、直前の name1キャプチャをなかったことにし、name1のキャプチャ部分から ……までを name2に保存するという。(覚え方: name2は直前の name1から……まで)

当然のこと、name1のキャプチャスタックが空のとき name2のキャプチャは ……のマッチ正否に関わらず失敗する。

 3.名前付きキャプチャ name1のスタックが空であることをテストするイディオム: (?(name1)(?!))

name1のキャプチャに成功しているかどうかで適用するパターンを変化させる条件分岐 (?(name1)truepattern|falsepattern) と、必ず失敗するパターン (?!) の組み合わせにより、name1のキャプチャスタックが空でないと必ず失敗する。逆に name1のキャプチャスタックが空のときは(省略された空の falsepatternが何にでもマッチして)必ず成功する(はず)。

(?(name1)(?!)) が成功する(=name1のキャプチャスタックが空である)とは、name1に含まれるパターンが開きかっこ、name2のパターンが閉じかっこにマッチし、その間のパターンが開き閉じどちらのかっこにもマッチしないとき、開きかっこと閉じかっこがバランスしている、ということ(MSDNの例がこれ)。

なんてこったい。

// Firefox 3.0.11と 3.5RC3のロケーションバーでの実行結果。
javascript:alert(/(?!)/.test("")) //=> true (falseであってほしい)
javascript:alert(/(?=)/.test("")) //=> false (trueであってほしい)
javascript:alert(/(?:)/.test("")) //=>

// Windows Vistaでの JScript(WSH)実行結果。
WScript.Echo(""+ /(?!)/.test("")) //=> false (期待通り)
WScript.Echo(""+ /(?=)/.test("")) //=> true (期待通り)
WScript.Echo(""+ /(?:)/.test("")) //=> true (期待通り)

必ず失敗するパターンを試してみたら Firefoxで真逆の結果が出てしまった。Firefoxが間違っててくれないと困るよ。(ブラウザにより逆の結果がでていることがもう困るけど)

(参考)間違いなく失敗する* > 詳説正規表現第3版 - Google ブック検索, 詳説正規表現第3版 - Google ブック検索

Internet Explorer 8.0.6001.18783 64-bit Edition、Safari 4.0.530.17、Opera 9.64、Google Chrome 2.0.172.33 でもみんな Firefoxとは逆の結果になる。Firefoxだけが 3.0から 3.5RC3になっても違っているのは悪夢だ。

Firefoxに理がないことは次の例からも判断できないか。空のパターンを空と空の選択パターンにするだけで結果がひっくり返ってる。

// Firefox 3.0.11のロケーションバーでの実行結果。
javascript:alert(/(?!)/.test("")) //=> true (下と同じであるべき)
javascript:alert(/(?!|)/.test("")) //=> false (期待通り)

javascript:alert(/(?=)/.test("")) //=> false (下と同じであるべき)
javascript:alert(/(?=|)/.test("")) //=> true (期待通り)

javascript:alert(/(?:)/.test("")) //=> true (期待通り)
javascript:alert(/(?:|)/.test("")) //=> true (期待通り)

♪ [本][正規表現] [ペーパーバック] Jan Goyvaerts, Steven Levithan【Regular Expression Cookbook】 Oreilly & Associates Inc

Regular Expression Cookbook
Jan Goyvaerts/Steven Levithan
Oreilly & Associates Inc
￥ 4,073

「XRegExp: JavaScript regex library」は、「SyntaxHighlighter(Ver.2.0)」で使われていたので知った。XRegExpの作者が、本の著者の一人、Steven Levithan。

XRegExp(Ver.0.6.1)が、Firefox 2,3、Internet Explorer 5.5-8β1、Safari 3.1、Opera 9.27の JavaScriptに付け加えて利用可能にする正規表現の機能は

•  名前付きキャプチャグループ

  後方参照も可。String.replace()での使用も可。

•  s(singleline)フラグ

  「.」が改行にもマッチ。

•  x(extended)フラグ

  ほとんどの空白を無意味なものにしたり(=パターンを自由にインデントできる)、行コメント(#から改行まで)を利用可能にする。

•  インラインコメント

  (?#ここにコメント)

•  Unicode Properties & Blocks サポート

  こんなの。\p{L}, \p{M}, \p{N}, \p{InHiragana}, \p{InKatakana}。否定は大文字のPで \P{}。

  文字集合の中で使えないという制限があるが、若干の工夫でなんとかなる。

使い所が限定されていそうだったり、使い方が難しそうな機能として

•  XRegExp.matchRecursive(string, left, right, modifiers, options)

  (独り言) 名前付きキャプチャグループをサポートしたなら、そのキャプチャ結果をスタックして、そこにパターンを繰り返し適用する書き方を用意することで、matchRecursive()なんてスペシャルメソッドは不要にできるのでは？ <何を言ってるのか自分でわかってないよ

  XRegExpのコンストラクタに「脳log[2008-01-11-p01] 鬼車すごい。正規表現で再帰ができる。」で書いたようなパターン文字列を渡して、再帰を認識するマッチングを行いたいです。

正規表現に関連するいくつかのメソッドを上書きし、ブラウザ間の差異を吸収するとともに、仕様通りの動作に統一したりもする。

•  /pattern/g.lastIndex

  IEなどが、幅0の文字にマッチしたときに lastIndexを不当にインクリメントするのを修正。

•  String.split(separator, limit)

  • 分割パターン中のキャプチャグループを戻り値の配列に挿入する。
  • マッチに参加しなかったキャプチャグループの位置に undefinedを挿入する。
  • 連続するセパレータの間などに存在する空文字列を省略せずに戻り値の配列に含める。

  (独り言) limitを指定したときに戻ってくる配列の要素数が limitと一致しない。XRegExpのバグ？ もちろん separatorにキャプチャグループは使っていない。

 再帰パターン

例えば再帰の深さの上限を 10や 20と決めてしまって、XRegExpのコンストラクタでごにょごにょパターン文字列を展開してみればどうだろう。JavaScriptで正規表現を一から実装しようというプロジェクトではないから、自ずと制限が定まってしまうのだけど、上限付きでもそれが 20もあれば十分という気がする。

 追記@2009-06-25: XRegExp 1.0がリリースされている(2009-06-24)。

驚いた。大部分がライブラリの機能紹介という退屈な(<作者本人が一番よく知っているから)文章に紛れ込んだバグ報告(とも呼べそうにないもの)を不自由な Google翻訳から見つけ出すとは。

1.0のソースも眺めてみたいけれど巨大な変更履歴にちょっと後込み。そのうちね。

♪ [正規表現] >Ruby 初心者スレッド Part 22 >>861 (http://www.kt.rim.or.jp/%7ekbk/zakkicho/08/zakkicho0811a.html#D20081109-6 経由)

if line =~ /.*Sector:<.*(Basic Materials|Conglomerates|Consumer Goods|Financial|Healthcare|Industrial Goods|Services|Technology|Utilities)/
    p $1
end 

HTMLをその場その場の正規表現で処理したくはないけど、それはそれとして、こうする。要は「Sector:HOGEHOGE」というテキストにタグがいろいろ付いていて、それらを無視してセクタ名を取り出したいということかと。

   /Sector:(?:<[^>]+>)*(Basic Materials|Conglomerates|Consumer Goods|Financial|Healthcare|Industrial Goods|Services|Technology|Utilities)/

元のパターン冒頭の .* は全く無駄。一度文字列全部を食べてしまうことに無駄以外の意味はない。(後ろから「Sector:」を探すか、前から「Sector:」を探すかという違いはあったりして)

二番目の .* が以降の文字列すべてを食べてしまうのも無駄。それにそれじゃあ「Sector:」から最も離れたセクタ名と同じ単語に一番最初にマッチしてしまう。

以上お目汚しでした。それより、この質問への最初の回答は金言。良いなあ(こんなレスがすぐに付くなんて)。

 正規表現は書き方を覚えないと駄目
 なぜなら、ほんの少し変えようと思っただけで別物になるから
 コピペでやろうとすると異常に遠回りになる

基本的に覚えることは

• 文字クラスとメタ文字(\w,\n,\s,...)
• アンカー(^,$,\b,...)と先読み(戻り読み)
• パターンのグルーピングと選択
• 量指定子(これは文字にもグループにも付けられる)

だけだもの。

♪ [正規表現] 今日やられた正規表現

/^(?=\W)/
/^(?!\w)/

二つの違いは？ (ヒント：空文字列/空行)

/^(?=\W)/  //=> 単語に使われる以外の文字から始まる行の頭にマッチ
/^(?!\w)/  //=> 単語に使われる文字から始まらない行の頭にマッチ
           //   (最初のパターンと違い、一文字もない場合(空行)にもマッチする)

♪ [Ruby][正規表現] /n, /s, /e, /u, $KCODEのもやっとを解消

正規表現リテラルの /nseuフラグは正規表現のマッチ動作に影響を与える。(/nseuフラグのいずれも指定しなかった場合は実行時の $KCODEに従う)

/nが指定されていたり $KCODE='NONE'のとき、「.」は改行を除いたり改行を含んだりする 1バイトにマッチするメタ文字だが、/seuフラグが指定されていたり $KCODEが SsEeUuのいずれかで始まる文字列のとき、「.」は日本語を含む、Shift_JIS、EUC-JP、UTF-8の一文字(1-3?バイト)にマッチする。

/nseuフラグや $KCODEは正規表現のパターンの解釈にも影響を与える。

Shift_JISで保存したスクリプトファイルに /表w/ というパターンと '表w' という文字列リテラルがあり、マッチを行った場合。実行時に $KCODE='NONE'であればパターンは /\225\w/ と解釈され、"\225"の後にメタ文字 \wにマッチする文字を探し、失敗する。$KCODE='SJIS'であればパターンは /表w/ と解釈され、"表"のあとに "w"を探し、成功する。

irb(main)> /表w/n =~ '表w'
=> nil
irb(main)> /表w/s =~ '表w'
=> 0

正規表現パターンの中のマルチバイト文字は文字列の場合と同じく、あくまでバイト列であり、/nseuフラグや $KCODEがどうであれ EUC-JPで保存されたスクリプトの中の正規表現リテラル /あ/ は Shift_JISの「あ」を表すバイト列 "\202\240" にマッチすることはない。

♪ [正規表現][javascript][大型本] Jeffrey E.F. Friedl【詳説 正規表現 第3版】 オライリージャパン

読んだ。この日記で以前書いたようなこと(20080116p01, 20080111p01)は全て書いてあった。もちろんそれ以上に知らないこと(NFAのマッチングのしかた、NFA型正規表現エンジンに適用できる正規表現のチューニングの具体例、Unicodeサポート、Perl, .NET, Java, PHPの正規表現、\Gの使い方などなど)が書かれていた。

非常に読みやすい文章で書かれているし、必要なところでは必ず前後のページへの参照先が書かれている。章の始めには Overviewがあり、その章から読み始めた読者への配慮も忘れない。当たり前のことだけど、徹底されている。「まずこの本を読め。正規表現について話すのはそれからだ。」と言い切れる良い本。正規表現を初めて学ぶ人にも、効率について考える余地ができてくるほど既に正規表現を使っている人にも役に立つ。

すごく実用的なテクニックで、でも全く想像が及ばなかったものがある。168ページの「4.5.8.1 肯定の先読みを使ったアトミックグループの模倣」がそれ。

 肯定の先読みを使ったアトミックグループの模倣

/(?>pattern)/     // アトミックグループを使ったパターン
/(?=(pattern))\1/  // 先読みでアトミックグループを模倣したパターン

高機能化する他の実装にくらべて、昔のままの JavaScriptの正規表現はバックトラックを抑制する構文を持っていない。JavaScriptでは非常に有用。

20080116p01でも書いたが、次の終わらない正規表現

/"(?:[^\\"]+|\\.)*"/       // マッチに失敗するとき死ぬほど遅い

はアトミックグループや絶対最大量指定子が使えるなら次のように書けるが JavaScriptは両方ともサポートしていない。

/"(?:[^\\"]+|\\.)*+"/      // JavaScriptでは使えない
/"(?>(?:[^\\"]+|\\.)*)"/g  // JavaScriptでは使えない
/"(?:[^\\"]++|\\.)*"/      // JavaScriptでは使えない。※上2つとは少し意味が違う

次のように先読みでアトミックグループを模倣すると組み合わせの爆発を避けることができる。

/"(?=((?:[^\\"]+|\\.)*))\1"/
/"\1"/            // 上のパターンから先読み部分を取り除いたもの。

先読みを取り除いたパターンを見ると一目瞭然だが、引用符がペアになっていなくて \1 の後ろの " のマッチに失敗したとしても戻る場所がない。あるのは " と \1 にマッチしたという結果で、どちらもオプションではないので取り消すことはできず、繰り返しでもないのでマッチした部分を少しずつ手放させることもできない。なので、ちょっとずつ後じさりしながら延々とあらゆる組み合わせのマッチを試行することなしに、マッチが失敗に終わったことが即座に判断できるようになるというわけ。本物のアトミックグループよりは劣るが効率も悪くない。同じ働きをする次の二つのパターンとかかる時間を比較してみた。

/"[^\\"]*(?:\\.[^\\"]*)*"/
/"(?:[^\\"]|\\.)*"/

 手順

バックトラックによる組み合わせの爆発が起きない 3つのパターンでかかる時間を比較。3回実行した。(3回繰り返しても一回一回の中の試行順が固定されていたら傾向は同じになるわな。無意味。あてみやむいみ)

var re = [
	/"(?:[^\\"]|\\.)*"/,
	/"(?=((?:[^\\"]+|\\.)*))\1"/,
	/"[^\\"]*(?:\\.[^\\"]*)*"/
];
var s = [
	'"'+ new Array(5000+1).join('\\"'),        //  1/100
	'"'+ new Array(500000+1).join('\\"') +'"',
	'"'+ new Array(500000+1).join("\\'"),
	'"'+ new Array(500000+1).join("\\'") +'"',
	'"'+ new Array(500000+1).join('a'),
	'"'+ new Array(500000+1).join('a') +'"'
];
var results = [];
for(var j = 0; j !== s.length; ++j) {
	var result = [];
	for(var i = 0; i !== re.length; ++i) {
		var t0 = new Date();
		var m = re[i].exec(s[j]);
		result[i] = new Date() - t0;
	}
	results[j] = result;
}
WScript.Echo(results.join("\n"));

 結果

数の単位は msec。

 みどころ

• マッチに失敗するときの、成功するときに比べた遅さ。
  • パターン2は例外
• パターン2(アトミックグループの模倣)ではしばしばマッチに失敗する方が速い。
  • \1のマッチが成功だと判断するにはキャプチャした長い長い文字列を最後までたどって比較する必要があるため、\1のマッチに失敗するほうが速くなる？
• 文字列1Fの特筆すべき遅さ。
  • 遅いとはいえ「終わらない」と形容するほど遅くはない。(これでも！)
  • 文字列長に比例したバックトラックが行われているせい？
  • 文字列2Fの結果と比較するに、\" という形で " が文字列の途中に含まれていることが最適化を阻んでいる？
• パターン3(ループ展開)は特定の場合を除いてパターン2(アトミックグループの模倣)より若干速い。
  • ループ展開は『詳説 正規表現』に載っていた言葉。
  • 特定の場合とは文字列3Fのことで、不用意なパターンを用いると処理が終わらなくなる場合のこと。
• パターン2(アトミックグループの模倣)は、(今回の眼目である)組み合わせの爆発が起こるような場合に、顕著な速さを見せる。
  • 他の文字列ではパターン3(ループ展開)に半歩譲るが。

ところで、文字列1Fがどのパターンでも一様に遅いのは文字列長に比例したバックトラックが行われているからなんだろうが、パターン2(先読みによるアトミックグループの模倣)でもそれを抑制できていないのは、なんとかできないものか。それでこそ若干のオーバーヘッドをのんででもアトミックグループの模倣を採用する理由になるのだが。

♪ [正規表現] 遅い正規表現

/\/(?:\\.|[^\n\\\/])+\/[gim]*(?!\w)/g
/\/(?:\\.|[^\n\\\/]+)+\/[gim]*(?!\w)/g // 死ぬほど遅い

どちらも同じく /regexp/i みたいな正規表現リテラルにマッチするのだが、下の方がブラウザが固まるほど遅い*。バックトラックの影響だろうか、これまで気にしてこなかったが……。原因が推測できない(無能)のがイタイ。(この日記、SHJSによるソースコードハイライトを多用していると読み込み完了直前にブラウザの反応がいっとき消えている。正規表現を最適化する余地があるならしたい)

昨日 rubyco（るびこ）の日記 (2007-06-20 正規表現の選択) 経由でウィッシュリストに入れた『詳説 正規表現 第2版』⁑がタイムリーすぎる。

 いけないバックトラックの例

 reg = /.*x|a/
 s = "a" * 11_000_000
 m = reg.match(s)

http://d.hatena.ne.jp/kkos/20060801#1154438784

最終更新: 2016-11-12T11:41+0900

♪ [正規表現][Ruby] 鬼車すごい。正規表現で再帰ができる。

Rubyの、括弧を使った %記法だって。

irb19> re = /%[Qq]?(?<brace>\{[^\{}]*(?:\g<brace>[^\{}]*)*})/
irb19> strings = %w(%{z}a %{a{b}z}c %{a{b}c{d{e}f}z}g %{{{{}}}z}a %{a{b}c %{z}a}b)
irb19> strings.each{|str| p str[re] }
"%{z}"
"%{a{b}z}"
"%{a{b}c{d{e}f}z}"
"%{{{{}}}z}"
nil
"%{z}"
=> ["%{z}a", "%{a{b}z}c", "%{a{b}c{d{e}f}z}g", "%{{{{}}}z}a", "%{a{b}c", "%{z}a}b"]

どの例も正しい範囲( %{ から z} まで)を切り取っているのがわかる。

1. この機能が使える鬼車がのってる Rubyは 1.9.0。
2. PCRE(ver 4.x)の (?P<name>...)と(?P>name)が同じものにあたるらしい。へー、そんなものが。javascript(JScript)の正規表現も新しくならんかな
3. .NETの (?<open>...)と(?<close-open>...)も同じことができるらしいが、正直わからん*⁑⁂
4. http://www.kt.rim.or.jp/~kbk/regex/regex.html < 正規表現の各種実装の違いがよくわかる。

 追記@2008-05-09: 対応する括弧にマッチする正規表現のヴァリエイション(<くどい表記だな)

/%[Qq]?(?<brace>\{(?:[^\{}]++|\g<brace>)*})/

若干速い。同じパターン( [^\{}] )の繰り返しも存在しない。http://fleur.hio.jp/perldoc/perl/5.10.0/pod/perl5100delta.mix.html#Regular_expressions を参考にした。

/%[Qq]?(?<brace>\{(?:[^\{}]+|\g<brace>)*})/

上のものの + が一つ落ちたもの。開き括弧が余分にある文字列を食わせると待てども待てども返ってこない。 http://mlog.euqset.org/archives/ruby-list/42232.html で既に書かれている。それに対する返答が http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-list/42233 。