ホームページ > 記事 > ウェブフロントエンド > JS での正規表現のバックトラッキングを正しく理解する方法
JS での正規表現のバックトラッキングを正しく理解する方法
- php中世界最好的语言オリジナル
- 2018-03-30 13:56:481462ブラウズ
今回は、js での 正規表現 バックトラッキングを正しく理解する方法を説明します。js で正規表現バックトラッキングを正しく使用するための 注意事項 は何ですか?実際のケースを見てみましょう。
正規表現の実装では、バックトラッキングは照合プロセスの基本的な部分であり、これが正規表現が非常に便利で強力である理由です。ただし、バックトラッキングは計算コストが高く、設計が間違っている場合は制御不能につながる可能性があります。バックトラッキングは全体的なパフォーマンスに影響を与える唯一の要素であり、バックトラッキングがどのように機能するかを理解し、使用頻度を減らす方法が効率的な正規表現を作成するための重要なポイントになる可能性があります
正規表現がターゲット文字列を左から 1 つずつスキャンするとき右へ 正規表現のコンポーネントをスキャンし、各位置で一致が見つかるかどうかをテストします。量指定子と分岐ごとに、処理方法を決定する必要があります。量指定子 (*、+?、または {2,} など) の場合、正規表現は、(| 演算子を介した) 分岐に遭遇した場合、いつさらに文字と一致するかを決定する必要があります。これらから開始します。 試してみるオプションの 1 つを選択してください。
正規表現がこのような決定を下すとき、必要に応じて後で使用できるように別のオプションを記憶します。選択したスキームが正常に一致すると、正規表現は正規表現テンプレートのスキャンを続行し、残りの一致も成功すると、一致は終了します。ただし、選択したオプションで一致が見つからない場合、または後続の一致が失敗した場合、正規表現は最後の決定点までバックトラックし、残りのオプションの 1 つを選択します。一致が見つかるまで、または量指定子と分岐オプションのすべての可能な置換が試行されるまでこのプロセスを続けます。その後、プロセスは放棄され、プロセスの先頭で次の文字に移動して、プロセスが繰り返されます。
たとえば、以下のコードは、このプロセスがバックトラッキングを通じて分岐をどのように処理するかを示しています。
/h(ello|appy) hippo/.test("hello there, happy hippo");
上記の正規表現行は、「hello hippo”或“happy hippo」と一致するために使用されます。テストの開始時に、私たちは h を探していました。ターゲット文字列の最初の文字はたまたま h でした。そして、それはすぐに見つかりました。次に、部分式 (ello|appy) は 2 つの処理オプションを提供します。正規表現は一番左のオプションを選択し (分岐の選択は常に左から右に進みます)、ello が文字列の次の文字と一致するかどうかをチェックし、一致すると、正規表現は次のスペースと一致します。
ただし、hippo の h は文字列内の次の文字 t と一致できないため、正規表現は次の一致で「行き止まり」になります。正規表現は、まだすべてのオプションを試していないため、この時点で諦めることはできません。そのため、最後のチェックポイントまで戻り (最初の h を照合した後)、2 番目の分岐オプションと照合しようとします。しかし、一致が失敗し、それ以上のオプションがなかったため、正規表現は文字列の最初の文字から始まる一致は成功しないと考え、2 番目の文字から再度検索を開始しました。正規表現では h が見つからなかったため、happy h に一致する 14 番目の文字が見つかるまで遡って検索を続けました。その後、正規表現が再度分岐し、今度は ello は一致しませんでしたが、バックトラック後の 2 番目の分岐で、文字列「happy hippo」全体と一致し、一致が成功します。
別の例として、次のコードは、量指定子を繰り返した場合のバックトラックを示しています。
var str = "<p>Para 1.</p>" +"<img src='smiley.jpg'>" +"<p>Para 2.</p>" +"<p>p.</p>"; /<p>.*<\/p>/i.test(str);
この正規表現は、まず文字列の先頭の 3 文字
に一致し、次に .* に一致します。ドットは改行文字を除く任意の文字と一致することを意味し、「貪欲な」量指定子であるアスタリスクは、できるだけ多く一致させるために 0 回以上繰り返すことを意味します。ターゲット文字列には改行がないため、正規表現は残りの文字列全体と一致します。ただし、正規表現テンプレートには一致するコンテンツがさらにあるため、正規表現は < と一致しようとします。文字列の末尾の一致は失敗するため、一度に 1 文字ずつバックトラックして、正規表現が
タグの位置に戻るまで < の一致を試み続けます。次に、/ (バックスラッシュをエスケープする) との照合を試みますが、これは正常に照合され、次に p との照合が試行されますが、照合されません。正規表現は後戻りを続け、最終的に 2 番目の段落の終わりで に一致するまでこのプロセスを繰り返します。成功した一致を返すには、最初の段落の先頭から最後の段落の末尾までをスキャンする必要がありますが、これは私たちが望んでいる結果ではない可能性があります。単一の段落と一致するように、正規表現内の「貪欲な」量指定子 * を「怠惰な」(別名「非貪欲」) 量指定子 * に変更します。 「遅延」量指定子のバックトラッキングは逆に機能します。正規表現 /
.*?
/ が .*? に進むと、最初にそれらをすべてスキップしようとし、その後 との一致を続けます。这样做是因为*?匹配零次或多次，尽可能少重复，尽可能少意味着可以重复零次。但是，当随后的<在字符串的这一点上匹配失败时，正则表达式回溯并尝试下一个最小的字符数：1个。正则表达式继续像这样向前回溯到第一段的末尾，在那里量词后面的<\/p>得到完全匹配。
如果目标字符串只有一个段落，那么此正则表达式的“贪婪”版本和“懒惰”版本是等价的，但尝试匹配的过程不同。
当一个正则表达式占用浏览器几秒甚至更长时间时，问题原因很可能是回溯失控。为说明此问题，给出下面的正则表达式，它的目标是匹配整个HTML文件。此表达式被拆分成多行是为了适合页面显示。与其他正则表达式不同，JavaScript在没有选项时可使点号匹配任意字符，包括换行符，所以此例中以[\s\S]匹配任意字符。
/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head> [\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/
此正则表达式匹配在正常HTML 字符串时工作良好，但当目标字符串缺少一个或多个标签时，就会变得十分糟糕。例如