JavaScriptのRegexとそれの効率的なコードの書き方

High Performance JavaScriptに書かれているJavaScriptにおけるregular expressionの書き方に関するメモ。
Regexpの処理に関しては他言語と共通かも判りませんが。

結論

• Backtrackingを起こさないような作りにしよう

Backtracking

解析中にある文字でマッチングに失敗した際、直近の処理の分岐点まで遡る事。
遡った後、まだマッチングが行われていない選択肢(e.g. 次の文字、|で隔てられた右側の候補)から処理を再開する。

quantifier/alternationに関する処理の流れ

quantifier: *, +?, {n}など
alternation |

例1
/h(ello|appy) hippo/.test("hello there, happy hippo")

1. 1文字目hがマッチする。それ以降の文字に対するマッチングを開始する。
2. alternationによる候補(左の候補から順に試行を行う)elloとのマッチングを行う。
3. elloまでマッチするが次の文字(h vs t)でfail。backtrackしてalternationの分岐に移動し次の候補appyのaからマッチングを始める。failなのでbacktrack。
4. 2文字目以降とregexp先頭のhとのマッチングを繰り返し、14文字目のhがマッチ。2.と同様分岐からelloとのマッチングへ。
5. e vs aの時点でfail。backtrackして分岐に戻り、次の候補appyとマッチング開始。
6. そこから先が全てマッチングに成功し、happy hippoとマッチ。

greedyとlazy (nongreedy)マッチングの処理の違い

// 例文
var example = '<p>a paragraph.</p>';

// greedy
/<p>.*<\/p>/.test(example);
// lazy
/<p>.*?<\/p>/.test(example);

greedyの場合、.*でのマッチングでa paragraph</p>まで全て検査し、その後残りの<\/p>とのマッチングの為に1文字ずつbacktrackして.*に含まれる文字を減らしながら検査していく。
lazyの場合<p>までマッチングした後、.*?と空文字がマッチした状態から<のマッチングを開始し、対象の文字列中の<にマッチするまでbacktrack->1文字.*?のマッチ対象に含めながら1文字ずつ検査を進めていく。
マッチさせたいパターンからbacktrackingの回数を求め、適切な方を選ぶ。

不要なbacktrackingを防ぐ

トークンをオーバーラップさせない

隣り合ったトークンが対象についてオーバーラップしないようにする。
例えば適当な文章から""で括られている文をマッチさせたい時に/".*?"/ではなく/"[^"\r\n]*"/を使うとか。前者では.と"による対象文字列中の"へのオーバーラップが生じ、backtrackingが起こる分岐点が発生している。後者にはオーバーラップが無い。

Lookaheadを使う

Lookaheadとは: https://developer.mozilla.org/en/docs/Web/JavaScript/Guide/Regular_Expressions#special-lookahead
JavaScriptには無いatomic groupingの機能を模倣する事が出来る。
atomic groupにマッチした文字列はbacktrackingで検査が再開されるポイントにはならないので余計な検査が行われない。
Lookaheadは通常その中に含まれるregexpをマッチ対象として扱わない(上記リンクに挙動の例があります)が、以下の様にregexpをcapturing groupに包んで、lookaheadの外にバックリファレンスを与える事でマッチした対象として扱う事が出来る。

/...(?=(pattern))\1.../

使いどころとしてはmarkup言語に対して検査を行う時。

分岐箇所を極力小さく

複数単語のマッチングに対してalternationで単語ごとに分けるのではなく異なる部分だけ切り出す感じ。
以下例¹

補足としてcharacter class ([\s\S]とか) を使った方がエンジンの実装的にalternation使うより速いっぽい。

ベンチマークの方法

backtracking捕捉の為、作ったregexpに対して大部分がマッチするけどマッチしないパターンを含む長い文字列を使う。

そもそも使わない

検査対象が非常に具体的な場合はString型のメソッドで処理した方が安上がりだったりする。

その他

シンプルに、具体的に、明示的に、等々