JS での正規表現のバックトラッキングを正しく理解する方法-jsチュートリアル-php.cn

JS での正規表現のバックトラッキングを正しく理解する方法

php中世界最好的语言

リリース： 2018-03-30 13:56:48

オリジナル

1460 人が閲覧しました

今回は、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=&#39;smiley.jpg&#39;>" +"<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 字符串时工作良好，但当目标字符串缺少一个或多个标签时，就会变得十分糟糕。例如标签缺失，最后一个[\s\S]*?将扩展到字符串的末尾，因为在那里没有发现标签，然后正则表达式将查看此前的[\s\S]*?队列记录的回溯位置，使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?—用它匹配标签，就是此前匹配过正则表达式模板<\/body>的那个标签，然后继续查找第二个标签，直到字符串的末尾。当所有这些步骤都失败时，倒数第三个[\s\S]*?将被扩展，直至字符串的末尾，依此类推。

此类问题的解决办法在于尽可能具体地指出分隔符之间的字符匹配形式，如模板“.*?”用于匹配双引号包围的一个字符串。用更具体的[^"\rn]*取代过于宽泛的.*?就去除了回溯时可能发生的几种情况，如尝试用点号匹配引号，或者扩展搜索超出预期范围。

在HTML 的例子中解决办法不是那么简单。不能使用否定字符类型，如用[^<]替代[\s\S]，因为在搜索过程中可能会遇到其他类型的标签。但是，可以通过重复一个非捕获组来达到同样效果，它包含一个回溯（阻塞下一个所需的标签）和[\s\S]（任意字符）元序列。这样可以确保中间位置上查找的每个标签都会失败。然后，更重要的是，[\s\S]模板在回溯过程中阻塞的标签在被发现之前不能被扩展。应用此方法后对正则表达式的最终修改如下：

/<html>(?:(?!<head>)[\s\S])*<head>(?:(?!<title>)[\s\S])*<title>
(?:(?!<\/title>)[\s\S])*<\/title>(?:(?!<\/head>)[\s\S])*<\/head>
(?:(?!<body>)[\s\S])*<body>(?:(?!<\/body>)[\s\S])*<\/body>
(?:(?!<\/html>)[\s\S])*<\/html>/

ログイン後にコピー

虽然这样做消除了潜在的回溯失控，并允许正则表达式在匹配不完整HTML字符串失败时的使用时间与文本长度呈线性关系，但是正则表达式的效率并没有提高。像这样为每个匹配字符进行多次前瞻，缺乏效率，而且成功匹配过程也相当慢。匹配较短字符串时使用此方法相当不错，而匹配一个HTML 文件可能需要前瞻并测试上千次。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！