これは過去にQiitaに投稿したもの
High Performance JavaScriptに書かれているJavaScriptにおけるregular expressionの書き方に関するメモ。
Regexpの処理に関しては他言語と共通かも判りませんが。
結論
- Backtrackingを起こさないような作りにしよう
Backtracking
解析中にある文字でマッチングに失敗した際、直近の処理の分岐点まで遡る事。
遡った後、まだマッチングが行われていない選択肢(e.g. 次の文字、|
で隔てられた右側の候補)から処理を再開する。
quantifier/alternationに関する処理の流れ
- quantifier:
*, +?, {n}
など - alternation:
|
例
/h(ello|appy) hippo/.test("hello there, happy hippo")
- 1文字目
h
がマッチする。それ以降の文字に対するマッチングを開始する。 - alternationによる候補(左の候補から順に試行を行う)
ello
とのマッチングを行う。 ello
までマッチするが次の文字(h
vst
)でfail。backtrackしてalternationの分岐に移動し次の候補appy
のa
からマッチングを始める。failなのでbacktrack。- 2文字目以降とregexp先頭の
h
とのマッチングを繰り返し、14文字目のh
がマッチ。2.と同様分岐からello
とのマッチングへ。 e
vsa
の時点でfail。backtrackして分岐に戻り、次の候補appy
とマッチング開始。- そこから先が全てマッチングに成功し、
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で単語ごとに分けるのではなく異なる部分だけ切り出す感じ。
以下例
instead of | use |
---|---|
cat | bat | [cb]at |
red | read | rea?d |
red | raw | r(?:ed|aw) |
(. | \r | \n) | [\s\S] |
補足としてcharacter class ([\s\S]
とか) を使った方がエンジンの実装的にalternation使うより速いっぽい。
ベンチマークの方法
backtracking捕捉の為、作ったregexpに対して大部分がマッチするけどマッチしないパターンを含む長い文字列を使う。
そもそも使わない
検査対象が非常に具体的な場合はString型のメソッドで処理した方が安上がりだったりする。
その他
シンプルに、具体的に、明示的に、等々