脳log[正規表現: 2010-07-09～]

最終更新: 2014-01-02T18:04+0900

♪ [SakuraEditor][正規表現] 「鬼車と bregonigに hitEnd(20100531p01)機能が搭載されることを願う他力本願日記」

なんてことをこの日記の冒頭に掲げたもんだから自分でやってみた(どういうこと？)。

 更新履歴

rev3 (2010-09-05, そのうち書く)

(サクラエディタ) 複数行検索を利用した複数行置換を実装。(複数行全置換はまだ。似たようなコードだし必要なのは手間だけだけど)

rev2.1 (2011-01-29)

(サクラエディタ) バグ修正。複数行検索モードでマッチ位置をバッファ内インデックスから(行,桁)に変換する際にミス。誤った検索結果が表示されることがあった。

rev2 (2010-08-27)

(サクラエディタ) 複数行検索モード実装。(正規表現を使った下検索のみ。50MiB制限あり。制限による探索打ち切り・マッチ範囲切り上げの通知なし)

テストバイナリ+変更点(test_multiine_search.zip)

rev1

(鬼車) 普通のマッチなしと、入力次第でマッチする可能性のあるマッチなしに異なる戻り値を割り当てた。

(bregonig) 入力不足のときに BMatchの戻り値を 0(正常終了,マッチなし)にして、エラーメッセージで入力延長によるマッチ成功の可能性を伝えている。

(サクラエディタ) 下検索での入力不足によるマッチ失敗をステータスバーで通知。

 bregonig

既存アプリに影響があるので良くないけど、bregonigへの暫定的な変更はこう。

 regexec_onig(bregonig.cpp)

	} else {
		/* ERROR */
		onig_err_to_bregexp_msg(err_code, NULL, msg);
-		return -1;
+		return err_code == ONIG_MISMATCH_INPUTSHORTAGE ? 0 : -1;
	}

入力が足りなくてマッチしなかったときは、エラーメッセージをセットするけど戻り値は負数(エラー)ではなく 0(マッチなし)。

 鬼車

鬼車(5.9.2)に「K.Takata's software : bregonig.dll」で手に入る onig-5.9.2-mod.diffを適用したものをさらに変更。マッチに失敗したときのエラーの種類で hitendしたかどうかを伝える。ちゃんと動くのか非常にあやしい代物。TODOもいっぱいある。

• 特定のパターンのパターンに向けた最適化を無効にしている。(そこまで手が回らない)
• backward searchに対していつ hitendフラグを立てていいのかわからない。(ので未対応)
• "aaaaa\n" という文字列から [a\r\n]+a というパターンを検索したときにバックトラックにより "aaaaa" がマッチするわけだが、その次の行にも "aaaa.." という文字が続いていた場合は……。一応マッチは見つかっているが hitendフラグも立てたい。
• [\w\W\s\S] というようなパターンで、メタ文字の登場順([\W\S\w\s]とか)に 依存しておかしな結果になる。(もちろん俺のミス。原因は解らない)

やっぱり鬼車は手に負えないかも。

 サクラエディタ

なんのことはない、影響を受ける既存アプリにはサクラエディタが含まれている。正規表現のコンパイルエラーと入力不足によるマッチなしを区別するためにちょっと変更した。

 複数行検索モード

一行検索(従来動作)してみて、マッチが行末まで続いていたり次の行の内容次第でマッチが成功に変わりそうなときはとりあえず二行ぶん検索してみる。それでも状況が同じなら 50MiBのバッファを埋めてから三度目の検索を行う。50MiBって大きすぎるだろうか。大きさの問題だろうか。かかか。

実装は CSearchAgent::SearchWord()に。これって単語検索専用のメソッドではなかったのですよ。CGrepAgentもこれを利用したらよかった。

バッファの実体は std::wstringで。文字列を比較するにも wmemcmpなりを使おうとして結局 std::wstring("hoge") == L"hoge" を使ったへたれなので、str系のライブラリ関数は恐ろしくて毎回すぐに投げ出します。(あれを使いこなせる人は VBや PHPも使いこなせると思うんですよ)

 TODO

• 上検索。
• 検索語ハイライトの処理がたぶん一行ごとに行われている。一行ずつ進みながら複数行を対象に検索を行ってるってわけ。無駄だし目に見えて遅い。
• バッファ長の制限により、マッチ範囲が途中で切られたりマッチの探索が打ち切られたりしても何も言わないのをなんとか。(制限をなくすかメッセージでも)
• 「SourceForge.net: Sakura Editor: Detail: 2309002 - 正規表現による複数行検索対応（簡易版）」のコメントを見ると、検索語ハイライトのほかに「すべて置換」にもパッチが必要そう。パッチを流し読みしてたら BookmarkManager(::MarkSearchWord)までが GrepAgentが持ってたような検索の勝手実装を持ってるらし。SearchAgentを使ってよね。(あ、いや、SearchAgentは当時なかったんだっけ)
• (複数行)検索にマッチしたなかでも、最初の行がマッチに含まれているか含まれていないかというのは区別する価値がある。サクラエディタの既存の実装は行指向が強いだろうから、「マッチした(ただし先のほうの行で)」ということを勘違いしかねない。(SearchAgentや選択範囲にはそういう指向がないから運良く複数行検索が自然に実装できただけ)
• (@2011-08-01) [\s\S]*$ というパターン。最後の行の末尾までマッチして欲しいのに一行目の改行直前で止まってしまう。マッチに成功したときの hitEndフラグの扱い。

 @2010-07-12 「鬼車 for Java」

hitEnd()の実装の参考になるか？と思ったけどそうもいかなそう。

Revision  74 hitEnd()の実装（但し仕様は満たしていない）。
Revision  85 useAnchoringBounds()及びuseTransparentBounds()に対応。→hitEnd()の実装を修正。
Revision 103 hitEnd()に@Deprecatedを追加。

    /**
     * This method is experimentation phase, and implementation has not been completed yet.
     * @return
     * @deprecated
     */
    @Deprecated
    public boolean hitEnd() {
        return (hasAnchoringBounds ? (range == region.end(0)) : (input.length() == end()));
    }

hasAnchoringBoundsが設定されてる場合は無視するとして、そうでないときは入力の長さとマッチの末尾(end())が一致してることをテストしてるだけに見える。それって hitEnd()とは違うよね。5月31日の日記で文字列 aa に対してパターン aa を適用したときに hitEnd()が falseになった事例を引用した。

そうそう。これこそが hitEnd()の使い道 >Check if string is a prefix of a Javascript RegExp - Stack Overflow コメントの最後に見たことのある名前が☺

 @2010-07-12 PCRE

PCRE(現在 ver. 8.10)は戻り読みも再帰も(パターンのコンパイル時の)改行指定オプションもスキャナー的に使うための hitEnd()のような機能(read pcrepartial)も、およそ欲しいものをすべて備えている。悪名高いスタックオーバーフローにも、1.スタック使用量を減らす。2.代替メモリ確保関数を使う(汎用ゆえに遅いmalloc/freeか自作)。3.pcre_exec()の代わりに pcre_dfa_exec()を使う。みたいな各種対策があるらしい。

最終更新: 2010-07-10T01:01+0900

♪ [正規表現] requireEnd(), hitEnd()

hitEnd

public boolean hitEnd()

このマッチャーが行なった最前のマッチング操作によって、入力シーケンスの終わりに達していたら、trueを返します。

このメソッドがtrueを返したときは、さらに新たな入力を加えると最後のマッチの結果が変わる可能性があります。

requireEnd

public boolean requireEnd()

入力を新たに増やすことによって、それまでのマッチが不成功に変わるならtrueを返します。

マッチが見つかっていたときにこのメソッドがtrueを返したら、さら入力を増やすとそのマッチがなくなることを意味します。マッチが見つかっていたときにこのメソッドがfalseを返したら、さらに入力を増やすとマッチが変わるかもしれないが、マッチがなくなることはないことを意味します。マッチが見つかっていないときにrequireEndを呼ぶことは、無意味です。

まず 1.5 で導入された hitEnd メソッドと requireEnd メソッドですが、 hitEnd メソッドはドキュメントでは入力の末尾がヒットした場合にtrueを返すとありますが、入力というのは領域を指しているようなのですが、末尾というのが最後の文字なのか末尾の位置なのかよく分かりませんでした。例えば aa をマッチング対象の入力シーケンスとして正規表現 aa でマッチングを行った場合、入力シーケンス全体にマッチしますが、この場合に hitEnd は false を返します。つまり最後の文字がマッチしていても true にはならないようです。ところが正規表現 a+ や a* でマッチングを行うと aa と同様に入力シーケンス全体にマッチしますが、この場合は hitEnd は true となります。つまりマッチした部分だけでなく正規表現パターン自体も hitEnd の返す値に影響するようです。

どちらも入力が一つの文字列におさまっていないときに役に立つメソッド。

1. 二番目の引用内容と、
2. requireEnd()が trueを返した場合と hitEnd()が trueを返した場合の対比と、
3. 自分が行文字列のリストを対象に鬼車でマッチングを行うときに欲しい機能から、

hitEnd()について想像するなら、

search engineが遷移先を残したまま入力を消費し尽くしたときに hitEnd()が trueになる。それの意味することは、直前のマッチが成功していたのなら、さらなる入力によりマッチの範囲が延長される可能性があるということ。直前のマッチが失敗していたのなら、さらなる入力によりマッチが成功するかもしれないということ。

ところで、hitEnd()が trueかつ requireEnd()が trueの場合って存在するだろうか。あるとして、どんな入力とパターンになるだろう。

requireEnd()はなくても困りはしない。マッチの範囲が入力の末尾まで続いていれば無条件に入力を増やしてリトライすることで requireEnd()が trueだったのか falseだったのかは確かめられる。

hitEnd()も、マッチが成功していたときは重要ではない。真価は、マッチが不成功だったときに hitEnd()が falseを返した場合は、さらなる入力をつなげてもマッチが成功に変わることがないと確かにいえること。hitEnd()がなければすべての入力を連結せずにはマッチが存在しないことを断定できない。

そうそうこれこれ。>http://www.mail-archive.com/classpath-patches@gnu.org/msg08501.html

さらに、こっちのドキュメントは詳細だしバグにも触れてある。上のスレッドで報告されてるのとは別のバグみたいだけど。

boolean hitEnd()

(This method is unreliable in Java 1.5; a workaround is presented on page 392.)

This method indicates whether the regex engine tried to inspect beyond the trailing end of the input during the previous match attempt (regardless of whether that attempt was ultimately successful). This includes the inspection done by boundaries such as \b and $.

If hitEnd returns true, more input could have changed the result (changed failure to success, changed success to failure, or changed the span of text matched). On the other hand, false means that the results from the previous attempt were derived solely from the input the regex engine had to work with, and, as such, appending additional text could not have changed the result.

The common application is that if you have a successful match after which hitEnd is true, you need to wait for more input before committing to a decision. If you have a failed match attempt and hitEnd is true, you'll want to allow more input to come in, rather than aborting with a syntax error.

最終更新: 2010-05-19T16:21+0900

♪ [正規表現] 鬼車。条件付き選択。

348 nobodyさん 2008/07/27(日) 01:11:32 ID:sEx2Pn85
    質問させてください。

    サクラエディタに鬼車5.9.1を搭載して正規表現の勉強をしているのですが、手元にある詳説正規表現には

    (<)?\w+(?(1)>)

    このような例があり、<があれば>のマッチを試みる?ということができるみたいです。

    ただ、鬼車はこの表現をサポートしていないみたいです。
    http://www.geocities.jp/kosako3/oniguruma/doc/RE.ja.txt

    同様のことを鬼車でも実現する方法ってあるのでしょうか？ 

鬼車は条件付き選択をサポートしていないのが玉に瑕だと、以前から思っている。なんとかできないかと上の例で考えてみたら、こうなった。

(<|)\w+(\1{100}|>)

せこい。姑息だ。100ってなんだよ。こんなの( <abc<<<...(94個の<を省略)...<<<> )にもマッチするじゃねーか。

最終更新: 2010-04-04T07:43+0900

♪ [正規表現] 正規表現の空の文字クラスのブラウザ実装 > 文字クラス(suika.fam.cx)

まとめはリンク先に任せるとして、最新の Opera(10.51)ではどうかね、と思ってアドレスバーに javascript……と打ち込んだら空の文字クラスのテストスクリプトと思しき、まさに今打ち込もうとしていたものが補完された。笑える(他に Operaの使い道はないのか)。このときの履歴だろう。さておき、結果は

// Opera10.51
/[]/.test("a") //=> false
/[^]/.test("a") //=> true

9.61のときとは違って一般に期待される結果になっているよう。次いで IE8の結果は……どちらもスクリプトエラー。

// IE8
/[]/.test("a") //=> "正規表現の中に ']' を指定してください。" (Perlと同じ。だけど IEのバージョンももう 8だよ)
/[^]/.test("a") //=> "正規表現の中に ']' を指定してください。" (Perlと同じ。だけど IEのバージョンももう 8だよ)

// このエラーが導くのは、パターンのこういう解釈と結果。
/[]]/.test("]") //=> true
/[^]]/.test("]") //=> false

変わっていない。ECMAScript3に準拠するならマッチ結果の食い違いはともかくエラーはないはずだけど。

ちょっと前にニュースになった IE9 Preview版(IEBlog : About the Platform Preview)もせっかくだしインストールして試してみた。「IEBlog : The New JavaScript Engine in Internet Explorer 9」なんて記事も見つけたし。結果は /[]/.test("a") も /[^]/.test("a") もクラッシュ。残念至極。

最終更新: 2016-03-05T00:30+0900

♪ [SakuraEditor][正規表現] 正規表現を使った検索・置換で、改行の意味を LFのみから CRも含むように。

経緯 > サクラエディタBBS[r7030]

差分 > fix_cr_handling_of_regex(下に修正版がある)

お試し > sakuraW.zip (547KiB)(下に修正版がある) (正規表現検索・置換を試すには bregonig.dll(Unicode対応版)が別途必要)

検索、置換を数度試したが機能しているみたい。ただ、$ が本当に改行の手前でマッチする関係で

^.*$

を空文字列に置換するという最初に提起されたケースでは、置換後の空行までが置換対象になってしまう(置換回数が 2倍)。目的に適う、より適切なパターンは

^.+$

あるいは、エディタの行置換機能を使っているのだから、もっと単純に

.+

で良い。

 @2009-09-24

「正規表現 - SakuraEditorWiki」を見ていて気付いた。\c[、\c]、\c$、\c. という制御文字のひとつを表すパターンが存在する。「鬼車 正規表現 Version 5.9.1」によれば \C-[、\C-]、\C-$、\C-.、\M-[、\M-]、\M-$、\M-. も存在しうる。\M-\C-[ なども存在しそうに思ったけど、これはこういう結果になった。

irb(main):001:0> /\M-\C-[/
SyntaxError: (irb):1: too short escaped multibyte character: /\M-\C-[/
        from c:/Program Files (x86)/ActiveScriptRuby-1.9.1/bin/irb.bat:20:in `<main>'
irb(main):002:0

制御文字なんて扱ったことがないからなあ(もはや relicだという認識)。対処の必要性がさっぱり感じられないけど……。

 @2009-09-25

一括置換で $ が CRLFの CR直前、LF直前、LF直後(正規表現DLLに与えた文字列末尾)の三カ所にマッチしてしまうとの指摘 >サクラエディタBBS[r7039]。

逐一、置換を実行した場合は問題ないことを確認していたのだが、一括置換はライブラリに全部お任せで、検索開始位置を調整することもできないから動作が違っていたのだろう。$ が CRと LFの間にマッチするのはわかっていたが、明示的に \r を食べた場合にだけ影響があると思っていた。一括置換なんてありふれた操作でそれが明るみに出るとは思いもせず。

急いで修正 > fix_cr_handling_of_regex.rev2、sakuraW.rev2.zip (547KiB)(さらなる修正版 rev3が下に)

初めて戻り読みを使った。なんとなく反則的な手段の気がして、使わないですむ方法をいつも考えるのだけど無理だった。これで bregonig.dll依存が決定的になった。[] の入れ子のことだけなら ] が見つかったときに charset_levelを一気に 0 にするだけで BREGEXP.DLL対応もできたのだが。

\C-X、\M-X というのは Ruby向けなのかも。サクラエディタ(+bregonig.dll)で \C-[ を検索しようとすると「premature end of char-class」というメッセージが出る。となれば、\cX だけが引っかかった小骨ということになる。

対処 > fix_cr_handling_of_regex.rev3、sakuraW.rev3.zip

<追記>bregonig.dllでは \c\X が \cX の意味になるとか。もう知らねー。</追記>

個人プロジェクトでもないと色々大変そう。ドッグフードでも食べながら様子見します。とりあえず反応だけ。

 ２．非対応となっているBREGEXP.DLL(ANSI版)への対処方法
 ANSI版とUNICODE版は別仕様としてしまうのか？

使用できる正規表現自体が別物なので BREGEXP.DLLは CBregexp::MakePattern()でよいかと。ユーザーを驚かさないための変更なので、. が \r にマッチすることを期待していた人以外に影響はないつもりでいる。

<追記>ANSI版+bregonig.dll向けのパッチを用意したので、別仕様は ANSI版+(BREGEXP.DLL/bregonig.dll)と Unicode版+bregonig.dllの間、または、 ANSI版+BREGEXP.dllと (ANSI版/Unicode版)+bregonig.dllの間のどちらでも選べる。BREGEXP.DLLのサポートするオーソドックスな(戻り読みをサポートしない)正規表現で、$を改行直後の行文字列終端にマッチさせない方法が見つからない限り BREGEXP.DLL対応は無理。</追記>

<追記>BREGEXP.DLL版も用意した。>_ANSI.rev2 >_ANSI.rev3</追記>

 ３．$ が改行なし最終行のEOF手前ともマッチするように改善すること
 $ を (?=\r\n?|(?<!\r)\n|(?<[^\r\n])$) に置き換える方法を試してみたけどエラーで動きませんでした。

肯定の戻り読みは (?<=) でした(なにせ使用経験がないもので)。気を取り直して、パターンを (?=\r\n?|(?<!\r)\n|(?<=[^\r\n])$)* に置き換えたところ、検索は予想通り、最終行がEOFのみの場合を除いて文書末にマッチするようになったのだけど、置換が行われない。(以前は行われていたのだろうか？ マッチのインデックスが文書の長さと同じ(=1つはみ出した状態)になっているはずだから特別な対処が必要なのだろう)

「以前は行われていたのだろうか？」< 行われていなかった。なら、(間違ってるけど)おいておこう。

 ４．検索強調表示が検索時の選択反転表示と一致すること
 $ を (?=\r\n?|(?<!\r)\n) に置き換えた版で $ を検索すると、改行文字自体は選択反転表示にはならない（マッチしない）のに検索強調表示されている。
 また、なぜか上方向検索では改行文字自体にマッチしたかのように選択反転表示になる。

$で検索したときに改行文字が強調表示されるのは、幅0のハイライトには意味がないので、実用面から今のように最低でも幅 1を保つべきだと思っていた。

上検索で改行が選択されてしまうのは間違いなので修正したい。これまでが、知らず $ が改行にマッチする仕様に依存していたのかもしれず、こういう修正は正しい方向に向かうためのものだと考えている。

修正した(rev4)。無限ループを避けるためにマッチ幅が 0のときに検索開始位置を特別にインクリメントするんだけど、そのタイミングが悪くて検索開始位置だけでなくマッチの範囲までがインクリメントされていたのが原因。

 ５．正規表現キーワードでの $, . 指定も検索・置換と挙動が一致すること
 現状、正規表現キーワードには $, . に検索・置換でやっているような細工が入っておらず、素の正規表現ライブラリ挙動になっている模様。
 検索・置換時の . の細工（[^\r\n]への置換）が追加されると、今よりも差異が大きくなって混乱しそう。

すでに書いたように、. が \r にマッチすること、$ が CRLF の真ん中にマッチすることを期待していた人(いるのか？)以外は違いに気付かないだろう。

\r\n$ みたいな書き方をしていた場合にマッチしなくなる。このケースはなくはないかも。

 ６．検索・置換や正規表現キーワードの複数行対応への順応性

ノーチェック。sフラグが含まれる( . があらゆる文字にマッチするようになる)ときには . を置き換えないようにする、mフラグが含まれない( ^、$ が行頭、行末にマッチしなくなる)ときには $ を置き換えないようにする、とか？

>fix_cr_handling_of_regex.rev4、sakuraW.rev4.zip

2ch民は 1.6.5.0をつかうのね。♥マークはいらないんだ。Consolasも使いたくない⁑んだ。(これは俺の理由だけど) r1663を使おうぜ。

 @2009-09-28

Unicode版Revision1662>http://sakura-editor.svn.sourceforge.net/viewvc/sakura-editor?view=rev&sortby=date&revision=1662

Ansi版Patch>http://sourceforge.net/tracker/?func=detail&aid=2869238&group_id=12488&atid=312488

勘違いしていた。Unicode版のサクラエディタで使用できる正規表現ライブラリは bregonig.dll(Unicode版)だけだ、という事実がいつの間にか、bregonig.dllは Unicode版専用だ、という思い込みにすり替わっていた。

だったら、採用の可否はともかく、Ansi版(trunk2の (Release|Debug)_Ansiビルドのことでなく trunkのビルド産物のこと、だろう)向けのパッチを作成する意味はあるわけだ。CBregexpのインスタンスがその寿命を通じて 1つの DLLだけを扱うのであれば、コストを初回に払うだけで、処理の振り分けを行うことができる。どっちかな？

>>> DLL初期化時に呼ばれる仮想関数がありました。(そのたびにチェックを行えばいい。実際は 1回しか呼ばれないだろう)

CheckRegexpSyntax() は癌だ。検索ボタンを押すたびに DLLのロードからはじめて、文法をチェックしたら使い捨てるって何事。文法チェックは Compile()で十分。その後の Match()のための準備にもなってちょうどいい。もろもろの手順を共通化したいのなら引数として CBregexpを受け取るべきだ。正規表現のチェックをしたい(=正規表現を利用したい)部分ではもちろん CBregexpなりなんなりをすでに持っているだろう。CheckRegexpSyntax()がこんな重量級のローカル変数をもつ必要はない。無効な検索パターンを履歴に追加したくないがために、検索の主体でない検索ダイアログが利用しているのかもしれないけど。

 @2009-09-29

やっつけで一応。これで昨日書いた「コストを初回に払うだけで、処理の振り分けを行うことができる」が事実になった。昨日の段階では、検索ボタンを押すたびに DLLがサポートする文法をチェックする関数が実行されていた(初回どころではない)。これでもまだ、検索ボタンを押すたびに Compile()が 2回走るのは変わっていない。

• stop_abusing_cbregexp
• stop_abusing_cbregexp_ANSI

おまけとして、bregexp.dllだけが sakura.exeの隣にある状態でエディタを起動し、その後 bregonig.dllを配置したとき、検索ダイアログでは 「bregonig.dll Ver....」と表示され、bregonig.dllしかサポートしない戻り読みを使用しても正規表現エラーにはならないものの、実際の検索には bregexp.dllが使用されるためだろう、戻り読みが機能していればマッチするはずの条件でもマッチ無しになってしまう、こういう、説明もややこしい起こりづらい状況が起こらなくなる。(文法チェックと実際の検索が CBregexpの同じインスタンスによって行われるようになるから)

本当は CBregexpが CDllHandlerを継承するのをやめて分離して、1つの CDllHandler(DLLインスタンス)を多数の CBregexp(BREGEXP構造体)から参照するのがいいのかも。もっといえば、BREGEXP構造体もコンパイル済みパターンとマッチ結果に分離したい。サポートする文法の情報はもちろん DLL付きの情報。CDllHandlerは汎用的すぎるから、その任には、CDllHandlerを継承したいまの CBregexpから BREGEXP構造体だけを追い出したものを充てればいい。

いまの CBregexpは InitDll()を呼び出されて、途中で違う正規表現ライブラリを読み込まされたとき、コンパイル済みの BREGEXP構造体を正しく解放できるのだろうか？

 @2009-10-01

BREGEXP.DLLでも . と $ を置き換えるようにしてみた > fix_cr_handling_of_regex_ANSI.rev2(下に rev3)

副作用があって、XYZ(CR)(LF) という行に対して XYZを検索すると XYZ(CR)(LF) がマッチする。マッチ結果が改行に隣接しているとき、改行がマッチに含められます。$を検索すると (CR)(LF) がマッチするのは以前からの通り。ここが変わらないのは、一括置換での過剰な置換を防ぐ手立てがこれしか BREGEXP.DLLからは与えられていない、ということ。

ついでに気になった、\r\n を検索したときステータスバーに 1 bytes selected. と表示されるのを修正。>fix_selection_area_and_selected_byte_count_ANSI 選択領域が中途半端なサイズだったのも直った。それもこれも CLayoutが EOLの長さを常に 1とカウントしていたせい。マッチ範囲が勝手に 1切り詰められていた。

表示としては ↵ も ⇠ も ⇣ も同じ一字だから CLayoutのすることにも一理あるのかもしれない。それなら改行文字の部分の選択領域をせめて全角幅にして検索結果のハイライト部分と大きさをそろえよう。

ANSI版の View関連のソースを見てたら気が遠くなる。Unicode版で

• CRLFを全角幅で表示
• CRLFの CR、LFのみハイライト、選択
• LF、CRの全角表示、全角幅選択(or半角幅ハイライト)
• 行頭マッチ(^)でキャレット描画

あたり、なんとかならんかな。検索結果の選択範囲とハイライト領域のずれが気になる。

 @2009-10-03

ANSI版を BREGEXP.DLLと組み合わせているときに、不必要に改行が検索結果に含まれてしまう場合を rev2より大幅に減らした。意地悪なパターンを与えられたときにどうなるかは把握しきれていない。

> fix_cr_handling_of_regex_ANSI.rev3(rev2と rev3にバグ発覚。rev4へ)

fix_cr_handling_of_regex_ANSI.rev4

どういうバグだったかというと、一括置換をしたときに改行や行文字列末尾付近で過剰に置換が行われないように、戻り読みが使えない BREGEXP.DLLのときは検索パターンと置換文字列に細工を施すのだけど、検索パターンの置き換え方がまずかった。

 誤: /A|B/ -> /A|B((?:\r\n?|\n\r?)?)/
 正: /A|B/ -> /(?:A|B)((?:\r\n?|\n\r?)?)/

選択 | の結合順位は一番低いのでした。

バグは CBregexp.cppを好き勝手にいじっていた結果をテストしている最中にたまたま見つかった。

• メンバ関数に constをつけたり
• 正規表現フラグを指定する引数の型を intから専用のものに変えたり
• CBregexp::IsLookAhead(const char *pattern)が内部状態を変更して、CBregexp::Match()の結果に意図しない影響を与える可能性を排除したり

していた。これは単なる自己満足。

 @2009-10-04

不必要に選択範囲が改行にかかっていたケースををさらに減少。> fix_cr_handling_of_regex_ANSI.rev5 検索パターンが LF直前や文字列末尾に幅0マッチしそうなときにだけ細工を行うことにした。なんというか、盆栽趣味？

バイナリ>sakura.zip

 @2009-11-25

AINI版では LFCRの LFと CRの間に幅0マッチしそうなときも細工を行わないといけないだろうな。やらないけど。(LFCR？なにそれ？という立場)

最終更新: 2009-08-25T02:45+0900

♪ [正規表現][Firefox] XRegExp-1.0.1と Firefoxの /(?!)/

20090628p01で書いた Firefoxのバグっぽいものが XRegExpに影響するみたい。

// Firefox 3.0.11 + XRegExp 1.0.1 での実行結果
alert( XRegExp("[]").test("a") ); //=> true
alert(  RegExp("[]").test("a") ); //=> false

[] と [^] の意味するところってなんでしょうね。[] は空の文字集合だから「どれでもない一文字」とマッチする(=空文字列にもマッチせず必ず失敗する)。[^] は空の文字集合の補集合だから「任意の一文字」だろうか。

参考ページを見つけた > 文字クラス(http://suika.fam.cx)

結局、こういうことだ。

• 主要 4ブラウザのうち [] と [^] が使えないのは IEだけ。
• Opera(9.61)は [] と [^] がおかしい(他と違う)。
• Firefox(3.0.11, 3.5RC3)は (?!) と (?=) がおかしい(他と違うし、自分自身の (?!|)、(?=|) とも違う)。

(IEの件を除いて)どのパターンも規格上の正解やデファクトスタンダードがなくて混乱してんじゃないかなあ。こういうのには近づかないに限る。

 追記@2009-07-04 04:44: 内容確認。

正しくコメントが読めてるといいんだけど……。

IEが空の文字セット [] を処理しないのは(ECMAScriptの仕様をすっとばして) Perlその他、JavaScript以外の多くの実装にならっているもので、[ に続く最初の文字を文字通りの文字 ] だとしているから。だから []] は [\]] と同じ意味になる。

Firefoxで (?!) の代わりに (?!|)、(?=) の代わりに (?=|) を使うのは良くなくて、つまりこれらの結果は同じになるべきだけど、どちらになるかは将来の Firefox次第だから。バックトラックの発生にもつながって効率的にも不利。だから (?!) の代わりは \b\B。(?=) の代わりは (?:) が良い。

\b\B というのは覚えておこう。

 追記@2009-07-04: はずしてた。

冒頭の指摘ははずしてる。考える前に、気付いたことをただ書いたせいだ。

XRegExpの目的の一つは、ブラウザごとにまちまちな挙動を見せる JavaScriptの正規表現に関するメソッドを仕様に準拠させることだったと思う(String.split()とか RegExp.lastIndexとか)。

だから空の文字セット( [] と [^] )を提供する第一の目的は 5ブラウザ(IE, Fx, Opera, Safari, Google Chrome)のうち不当にこれを受け付けない IEにおいて、仕様で許された正規表現パターンを利用可能にすること、かもしれない。

その過程で、Firefoxがネイティブに処理する空の文字セットと、XRegExpの提供する空の文字セットの挙動が食い違ってしまっている(1行目 1、2列)、というのが冒頭の指摘。でもこれは重要ではないし、同様の指摘を Operaについても行うことができる(3行目 1、2列と 3、4列)。

そうではなくて、ライブラリ利用者として「仕様に準拠した」「ブラウザ間で統一された」機能を望む視点から、XRegExpの提供する空の文字セットが Firefoxにおいてのみ違う意味になること(2列目)をこそ指摘すべきだった。(実際そうしたんだけど、日記の内容だけが古かったのでこうして追記している)

 すごくおかしな Firefox(3.0.11)の (?!)

全てのパターンに (?!) が含まれているから、本当は全て falseになってほしい。

/(?!)/.test("abc")     //=> true！
/(?!)(?!)/.test("abc") //=> false

/^(?!)/.test("abc")    //=> false
/(?!)$/.test("abc")    //=> true！

/a(?!)/.test("abc")    //=> false
/(?!)a/.test("abc")    //=> true！

/\b(?!)/.test("abc")   //=> false
/(?!)\b/.test("abc")   //=> true！

/(?:)(?!)/.test("abc") //=> true！
/(?!)(?:)/.test("abc") //=> true！

(?!) が実質的にパターンの先頭にあるときだけ、存在しないかのように振る舞っているような。すごく限定された状況でのみ発動するんだったんだ。

ここまで書いてなかったことに気付いたけど、これが XRegExp("[]") に影響するのはこのパターンが内部的に (?!) に書き換えられるから。XRegExp (1.1.0, 2009-07-04)では \b\B に置き換えられるようになっていて、Firefoxのおかしな挙動に影響されて他のブラウザと違う結果になることはなくなっている。

もう書かれてた！ > http://blog.stevenlevithan.com/archives/xregexp-1-0/comment-page-1#comment-37653

 追記@2009-07-05 04:40: XRegExp-1.0の設計の良さを示す好例 > 20090703c02

自身の機能を XRegExp.addToken()で提供しており、ユーザーも同じ方法で拡張できる。トークンの有効範囲が文字セット [……] の内か外か、その両方かは addToken()の第3引数のビットフラグ( XRegExp.INSIDE_CLASS, XRegExp.OUTSIDE_CLASS )で指定できるし、エスケープシークェンスは予め処理されているので \(?!) を \\b\B に置き換えてしまう心配もない。簡単でしょう。

でも鬼車の \g を追加しようとして、名前付きキャプチャ内部のパターンを手に入れられず、中断。

 追記@2009-07-05 04:40: \gの実装サンプルを見てみた。

その \gの利用例が次。

XRegExp("(?<any_backref>\\3|\\4){0}     \
         (?<smiles>(?::-[D)])+){0}      \
         ([ab]) ([12]) \\g<any_backref>+\
         \\g<smiles>                    ", "x").test("a22aaa:-):-D"); // true

解説すると、まず名前付きキャプチャを使って再利用を前提としたパターンを定義する(any_backrefと smiles)。ポイントは量指定子{0}の存在で、現状ではこれが必ず必要になる。これによりこの名前付きキャプチャはマッチに参加せず、一文字も消費せずに成功する。その存在意義は \g<smiles> のように、後で名前を使ってパターンを再利用できること。

上の例で、実際に文字を消費するパターンは後半分、次の部分だけ。

    /([ab])([12])\g<any_backref>+\g<smiles>/

Rubyで同じ意図を持って書くとこういうふうになる。

irb> any_backref = /\1|\2/
=> /\1|\2/
irb> smiles = /(?::-[D)])+/
=> /(?::-[D)])+/
irb> re = /([ab])([12])#{any_backref}+#{smiles}/
=> /([ab])([12])(?-mix:\1|\2)+(?-mix:(?::-[D)])+)/
irb> re.match( "a22aaa:-):-D" ).to_a
=> ["a22aaa:-):-D", "a", "2"]

さて、パターンの再利用が \g の利用法だけど、個人的にそれが最大の効果を発揮するのは、パターン定義の中でパターンを呼び出したとき、再帰的なパターンを定義できることだと思っている。20080111p01で既に書いているが、

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

名前付きキャプチャ (?<brace>……) の中に \g<brace> がある。こういう GNUの命名のような再帰的定義ができてこそ \g を利用する価値があると個人的には思う。

addToken()で \g を定義する方法として考えていたのは「パターン文字列を、上限を決めて再帰的に展開する」というもの。このように。

1. (?<brace>{\g<brace>})
2. (?<brace>{(?:{\g<brace>})})
3. (?<brace>{(?:{(?:{(?:{\g<brace>})}))})
4. (?<brace>{(?:{(?:{(?:{(?:)})}))})

実際の手順は addTokenの第二引数が文字列を返す代わりに toString()を定義したオブジェクトを返し、xregexp.jsの下の引用部分、output.join("") の時点で、名前付きキャプチャ内のパターンを参照してパターン文字列を返そうというもの。

            regex = RegExp(output.join(""), real.replace.call(flags, /[^gimy]+/g, ""));
            regex._xregexp = {
                source:       pattern,

コードの枠組みはこんなの。もちろんこのままでは動かない。

function PatternOfNamedCapture(name) {
	this.name = name;
}
PatternOfNamedCapture.prototype.toString = function(){
	// ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
	if(MAX_RECURSION < count++) {
		return "(?:)";
	} else {
		return output.slice(
			defs[this.name].start,
			defs[this.name].end
		).join("");
	}
	// ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
};
XRegExp.addToken(
	/\\g<([$\w]+)>/,
	function(match) {
		return new PatternOfNamedCapture(match[1]);
	}
);

最終更新: 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