正規表現を "致命的なバックトラッキング"にしないようにするにはどうすればよいですか？

Question

javascriptで以下のコードを実行しようとすると、設計が不適切な正規表現のために無限ループする致命的なバックトラッキングが原因でブラウザがハングします。私は別の発現またはこの問題を回避するための方法のいずれかが必要になります。

string temp = "Testing robustness {parent-area-identifier Some text in between the tokens {parent-area-label}"; 
var strRegExp = new RegExp(/[{](?:[^{}]+|[{][^{}]*[}])*[}]/g); 
var arrMatch = temp.match(strRegExp); 

Answer 1

あなたの正規表現は、よりバランスの取れたペアがネストされていますが、レベルが1つしかないバランスのとれたマッチに一致するように見えます。この正規表現は、不正な入力に掛けなくても、その行います

{[^{}]*(?:{[^{}]*}[^{}]*)*} 

これはJeffrey Friedl'sアンロールループ技術の一例です。最初の[^{}]*にブレース以外の文字がなくなると、次の部分は単純なネストされていないブレースのペアとのマッチングを試み、次に中括弧以外のものを探します。その部分は、複数のネストされたブレースのペア（ただし、すべて同じレベル）を許可するためにループされています。

これは壊滅的なバックトラック（ネストされた量指定子、オプションのすべて）に対してさらに脆弱に見えるかもしれませんが、マッチが不可能であってもバックトラックする必要がないため動作します。

括弧をエスケープする必要はありませんが、限定子の一部として使用しているように見えない限りは、エスケープする必要はありません。 （いくつかのフレーバーでは、左のブレースをエスケープする必要がありますが、JavaScriptは使用しません）

また、未知の深さにネストされた中カッコをマッチングさせたい場合、あなたは不運です。いくつかの味はそれを管理することができますが、JavaScriptはあまりにも限られています。

Answer 2

あなたは中括弧なしでエリアを選択したい場合は、このメソッドを使用するようにしてください：

var temp = "{=rankedArea?metricType=3902&area={parent-area-identifier}:AdministrativeWard} {=rankedArea?metricType=3902&area={parent-area-identifier}:{ward-type-identifier}} {district-short-label} adfasdfasdfasdf asdf asdf asdf asdf {child-area-short-label} asdf asdf asdf {authority-area-short-label} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=compare?metricType=3343&greater=greater than&equal=equal to&less=less than} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=countAreas?area={ancestor-2-identifier}:{ancestor-1-type-identifier}} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=equivalent?metricDimension=[218][218_Number][Specificethnicity][Ethnicity_AsianorAsianBritish]} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf {=metricTypeMetadata?metricType=3341&returnValue=source} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=value?metricType=3284} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=percent?metricType=518} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=rank?metricType=3287} asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=rankedArea?metricType=3286} asdfasdfasdfasdf asdf"; 
var strRegExp = new RegExp(/{(?:[^{}]+|{[^{}]*})*}/g); 
var arrMatch = temp.match(strRegExp); 
console.log(arrMatch.length); 
console.log(arrMatch); 

結果：

13 
["{=rankedArea?metricType=3902&area={parent-area-identifier}:AdministrativeWard}", 
"{=rankedArea?metricType=3902&area={parent-area-identifier}:{ward-type-identifier}}", 
"{district-short-label}", 
"{child-area-short-label}", 
"{authority-area-short-label}", 
"{=compare?metricType=3343&greater=greater than&equal=equal to&less=less than}", 
"{=countAreas?area={ancestor-2-identifier}:{ancestor-1-type-identifier}}", 
"{=equivalent?metricDimension=[218][218_Number][Specificethnicity][Ethnicity_AsianorAsianBritish]}", 
"{=metricTypeMetadata?metricType=3341&returnValue=source}", "{=value?metricType=3284}", 
"{=percent?metricType=518}", 
"{=rank?metricType=3287}", 
"{=rankedArea?metricType=3286}"] 

このアルゴリズムが間違っていると、速く動作します。より多くのテストケースを提供してください。