脳log[正規表現: 2009-09-22～]

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

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