$ で GREPしてみたらこういうものが無数に見つかった。だいたいが一行コメントの中に対応した state。終了条件は行末で、URLを含んでいれば sh_urlとしてマークする。
{
'exit': true,
'regex': /$/g
},
{
'regex': /(?:<?)[A-Za-z0-9_\.\/\-_]+@[A-Za-z0-9_\.\/\-_]+(?:>?)/g,
'style': 'sh_url'
},
URLが改行の直前まで続いていれば、終了条件としての行末の検出がスキップされて一行コメントが次の行まで継続する。まさしく 20080513p01の問題の繰り返し。
結局、sh_main.jsに非互換な変更を加えるのは問題大ありだと判明したので sh_javascript.jsで対応することにしましたよ、と。
[ // state 2: in "string"
{
regex: /\\[\\"]/g
},
{
next: 6,
regex: /\\$/gm
},
{
exit: true,
regex: /"|$/gm
}
],
[ // state 6: eat an end-of-line ※空行は食べられないよ
{
exit: true,
regex: /^/gm
}
]
動作確認は昨日の日記で。
例えば、JavaScriptのリテラル文字列では \ と改行のシークェンスは空文字を意味している。つまりこういうこと
var str = "空白を含まない\ ひとつながりの文字列です";
このシークェンスを認めるように、ダブルクォーテーション文字列の終了条件として次のようなものを shjs/lang/sh_javascript.js に含めてみたがうまくいかなかった。
[ // "string"
{
// \\ と \" と \(改行) を 1つのシークェンスとして
// 食べてしまう。終了位置を見誤らないためであって、
// 特に何をするということもない。/\\(.|$)/gm でも構わない。
regex: /\\(?:[\\"]|$)/gm
},
{
// エスケープされていない " に出会ったら "～" の中に
// いるという状態(state)から exitする。
// " がないまま行末に達したら、終端されていない不正な
// 文字列だと判断して、やはり exitする。
exit: true,
regex: /"|$/gm
}
],
少し前に「行末に達した時点でマッチングを打ち切っていたのが間違い。$は空文字列にもマッチする。全てのマッチに失敗するまで続ける必要があった(20080513p01)」と自分のミスを書いて、これを修正したのだが、shjs-0.4.2はもちろん正しく、全てのマッチが失敗するまで続けている。
そうすると何が起こるか。/\\$/gm にマッチした後でも /"|$/gm のマッチに成功してしまい、結果、行末に \ があろうがなかろうが exitしてしまう。
もちろん行末に達したからといってすぐにマッチングを打ち切っては 20080513p01と同じ間違いを犯すことになるので、同一 state内で*二回以上*行末にマッチすることがないように sh_main.jsを変更した。
内の方のループの、頻繁に実行される部分に if が増えたのが気に入らないものの、悪影響のある非互換でもないし、首尾は上々だし(冒頭の文字列のハイライト結果が見本)、悪くない。
var str = "終端されていない 不正な文字列です";
var str = "終端されていない\" 不正な文字列です";
*たまたま*行末にある \" にマッチしたことで、終了条件である行末の検出がスキップされて、次の行までが文字列だと判断されている*。\" とのマッチは \$ と違い行末を要求していないから、この場合は一行目で exitしてほしい。
* 20080530p01で修正したので文章とハイライト結果が食い違っているかもしれない。
例えばこのページ http://vvvvvv.sakura.ne.jp/ds14050/diary/20080112-7.html 。Endキーで末尾に移動して PageUpで戻っていくと空白の PREが目に入ると思う。その少し上にはページの内容を覆い隠す黒い領域があるはず。(そうでなければ修正されたのだろう。Firefox2で最初に確認し、Firefox3.0RC1でも直っていなかったが)
大量の PREが存在したり、一つだけでも巨大な PREが存在する場合に起こる様子。innerHTMLで PREの内容を置き換えているのも原因になっているかもしれない。
画面の末端にスクロールした状態でページをリロード(F5 or Ctrl+R)すると下方の PREが正常に表示される反面、上端付近の PREに同じ問題が生じる。遠方の PREの書き換えに問題があるのでは？
真っ白の PREの中で、右クリックしたりテキストを選択したりといったアクションを起こせば正常に表示されることが多い。
あと、PREの中から開始した選択は PREの外に出られなかったり。(これは TEXTAREAと違い PREでは Ctrl+Aで全文選択ができないために用意された代替手段だという気もする)
正規表現リテラルの /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" にマッチすることはない。
読んだ。この日記で以前書いたようなこと(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。
| パターン1 | パターン2 | パターン3 | |||
| 工夫なし | アトミックグループの模倣 | ループ展開 | |||
| /"(?:[^\\"]|\\.)*"/ | /"(?=((?:[^\\"]+|\\.)*))\1"/ | /"[^\\"]*(?:\\.[^\\"]*)*"/ | |||
|---|---|---|---|---|---|
| 文字列1 | マッチしない(F) | "\"\"......\"\" | 2910×100, 2928×100, 2914×100 | 2551×100, 2581×100, 2595×100 | 2372×100, 2387×100, 2377×100 |
| マッチする(T) | "\"\"......\"\"" | 124, 124, 124 | 138, 137, 134 | 108, 107, 108 | |
| 文字列2 | マッチしない(F) | "\'\'......\'\' | 138, 140, 151 | 125, 127, 125 | 122, 118, 118 |
| マッチする(T) | "\'\'......\'\'" | 138, 126, 126 | 140, 128, 133 | 135, 105, 106 | |
| 文字列3 | マッチしない(F) | "aa..........aa | 174, 172, 166 | 14, 11, 13 | 96, 90, 92 |
| マッチする(T) | "aa..........aa" | 155, 119, 126 | 32, 15, 14 | 15, 12, 11 | |
ところで、文字列1Fがどのパターンでも一様に遅いのは文字列長に比例したバックトラックが行われているからなんだろうが、パターン2(先読みによるアトミックグループの模倣)でもそれを抑制できていないのは、なんとかできないものか。それでこそ若干のオーバーヘッドをのんででもアトミックグループの模倣を採用する理由になるのだが。
オリジナルの sh_javascript.jsはコメントの中の URLっぽい部分とメールアドレスっぽい部分をハイパーリンクにしていた。機能が劣るのは遺憾なので sh_javascript.jsと sh_ruby.jsに、コメントと文字列の中の URLっぽい部分をハイパーリンク化する機能を追加した。
その過程で気付いた、一行コメントの終了条件などに使われている $アンカーのマッチングが行われない場合があったのを修正した。(行末に達した時点でマッチングを打ち切っていたのが間違い。$は空文字列にもマッチする。全てのマッチに失敗するまで続ける必要があった)。これは自分が 2008-02-25に持ち込んだバグでオリジナルには存在しない。
# http://vvvvvv.sakura.ne.jp/ds14050/badboy/log/ How is this line highlighted ?
最終更新: 2009-09-01T05:05+0900
このようにハイライトされます。
'%04d-%02d-%02d' % [2008, 5, 8]
(整形した)HTMLソースはこう。
<span class="sh_string">'%04d-%02d-%02d'</span> <span class="sh_string">% [2008, </span> <span class="sh_number">5</span> <span class="sh_symbol">,</span> <span class="sh_number">8</span> <span class="sh_cbracket">]</span>
「% [2008, 」が一つの文字列にされてしまっている。どういう判断なのかと調べれば、%!string! と同じものだと見なされていた。(そのルールは自分で書いたんだけども)
知っていたでしょうか？ %リテラルの区切りには空白(改行も！)が使えるのでした。(alnumと mbchar以外なら OKっぽい。変態すぎるよ)
最終更新: 2010-07-05T10:38+0900
[大型本] Jeffrey E.F. Friedl【詳説 正規表現 第3版】 オライリージャパン
この本の著者は regex派だそうな。FedExと同じように読めるからだとか。自分は気分で regexだったり regexpだったり reだったり。regexpって書く人はどう読んでんの？ だって。そうか、読み方か。考えたこともなかった。Friedlさんの疑問にお答えしましょう。regexpと書いて正規表現と読む、です。
iPodを始め、よそでは 12:00 PM が正午を意味することについて(無理矢理)理由を考えてみました。
12:00-12:59が 12:00PM-12:59PM、00:00-00:59が 12:00AM-12:59AMになる理由。日本人の(と書いてもいいよね？)感覚では 12:00PM=00:00AM=深夜となるものが正午を表してしまう理由。
時刻と AM/PMをわけて考えなければいけない。まず、時刻の部分はそのまま読み方を表している。だから 0時台は存在せず 12時台が使われる (0時何分という読み方をする人もいるでしょうが、自分は 12時何分と読みます。時計の文字盤にも 0は無いし。本当の問題は海の向こうの人がどう読むか、ですが)。そして、AM/PMは午前か午後かを付加的に表している。
こじつけすぎるか……。(AM/PMが(午前/午後と違い)時刻の後ろに付くのは確かなんだけど)
00:30と書いて 12時30分と読んだり、午後0時半と読んだり、ひょっとしたら午後12時30分と読んだりする器用さが無いのが理由なんじゃないかと思ったのだが。*
自分のケータイでこっそり⁑こんな修正が行われていた。
サブディスプレイの待受画面に表示される時計を「Digital1(12h)」にすると、0時（午前0時）台が0:xxAM、12時（午後0時）台が12:xxAMと表示される。（他の12時間表示では、正しくそれぞれ12:xxAM、12:xxPMと表示される）
午前0時台は 0:xx AMではなく 12:xx AMが正しいと書いてある。
同じく Wikipedia。日本でも海外でもいろいろあるみたいね(なにが正しいとは言い切れない)。でも日本の公の判断が理性的で良い。だから AM/PMなんて使わずに午前/午後を使うべき。一番面倒がないのは 24時間制を使うことだし、もちろん自分のデジタル時計は全てそうしてるけど。