Comment comprendre correctement le retour en arrière des expressions régulières en js

Cette fois, je vais vous montrer comment comprendre correctement le traçage des expressions régulières en js, et quelles sont les précautions pour utiliser correctement le traçage des expressions régulières en js. Voici des cas pratiques. . , jetons un coup d'oeil.

Dans l'implémentation d'expressions régulières, le backtracking est un élément fondamental du processus de correspondance, et c'est la raison pour laquelle les expressions régulières sont si utiles et puissantes. Cependant, le retour en arrière est coûteux en calcul et peut entraîner une perte de contrôle si la conception est erronée. Le retour en arrière est le seul facteur qui affecte les performances globales. Comprendre son fonctionnement et comment réduire la fréquence d'utilisation peut être la clé pour écrire des expressions régulières efficaces

Lorsqu'une expression régulière analyse la chaîne cible, à partir de Scan. les composants de l'expression régulière un par un de gauche à droite, en testant si une correspondance peut être trouvée à chaque position. Pour chaque quantificateur et branche, il faut décider comment procéder. S'il s'agit d'un quantificateur (tel que *, +? ou {2,}), alors l'expression régulière doit déterminer quand essayer de faire correspondre plus de caractères si elle rencontre une branche (via l'opérateur |), alors l'expression régulière doit ; commencez par ceux-ci Choisissez l’une des options à essayer.

Lorsque l'expression régulière prend une décision comme celle-ci, elle se souvient d'une autre option pour une utilisation ultérieure si nécessaire. Si le schéma sélectionné correspond avec succès, l'expression régulière continuera à analyser le modèle d'expression régulière et si les autres correspondances réussissent également, la correspondance se termine. Cependant, si l'option choisie ne parvient pas à trouver de correspondance, ou si les correspondances suivantes échouent, l'expression régulière reviendra au dernier point de décision et sélectionnera l'une des options restantes. Continuez ce processus jusqu'à ce qu'une correspondance soit trouvée ou que toutes les permutations possibles de quantificateurs et d'options de branchement aient été essayées, puis le processus est abandonné, puis déplacé vers le caractère suivant au début du processus, et le processus est répété.

Par exemple, le code ci-dessous montre comment ce processus gère les branches via le backtracking.

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

La ligne d'expression régulière ci-dessus est utilisée pour faire correspondre "hello hippo" ou "happy hippo". Au début du test, nous recherchions un h. La première lettre de la chaîne cible était h, et nous l'avons trouvée immédiatement. Ensuite, la sous-expression (ello|appy) propose deux options de traitement. L'expression régulière sélectionne l'option la plus à gauche (la sélection de branche s'effectue toujours de gauche à droite), vérifie si ello correspond au caractère suivant de la chaîne, c'est le cas, puis l'expression régulière correspond aux espaces suivants.

Cependant, l'expression régulière "se retrouve dans une impasse" lors du prochain match, car le h dans hippo ne peut pas correspondre à la lettre t suivante dans la chaîne. L'expression régulière ne peut pas abandonner à ce stade car elle n'a pas encore essayé toutes les options, elle revient donc au dernier point de contrôle (après avoir fait correspondre le h initial) et essaie de faire correspondre la deuxième option de branche. Mais comme la correspondance n'a pas abouti et qu'il n'y a plus d'options, l'expression régulière a estimé que la correspondance à partir du premier caractère de la chaîne ne réussirait pas, elle a donc recommencé la recherche à partir du deuxième caractère. L’expression régulière n’a pas trouvé h, elle a donc continué à regarder en arrière jusqu’à trouver la 14ème lettre, qui correspondait au h heureux. Ensuite, l'expression régulière se ramifie à nouveau, et cette fois ello ne parvient pas à correspondre, mais dans la deuxième branche après un retour en arrière, elle correspond à la chaîne entière "happy hippo" et la correspondance réussit.

Comme autre exemple, le code suivant démontre le retour en arrière avec des quantificateurs répétés.

var str = "<p>Para 1.</p>" +"<img src=&#39;smiley.jpg&#39;>" +"<p>Para 2.</p>" +"<p>p.</p>";
/<p>.*<\/p>/i.test(str);

L'expression régulière correspond d'abord aux trois lettres

au début de la chaîne, puis à .*. Le point signifie correspondre à n'importe quel caractère à l'exception des caractères de nouvelle ligne, et l'astérisque, un quantificateur « gourmand », signifie répéter zéro ou plusieurs fois pour correspondre autant de fois que possible. Comme il n'y a pas de nouvelle ligne dans la chaîne cible, l'expression régulière correspondra à la totalité de la chaîne restante ! Cependant, comme il y a plus de contenu à faire correspondre dans le modèle d'expression régulière, l'expression régulière essaie de correspondre à <. Puisque la correspondance à la fin de la chaîne échoue, nous revenons en arrière un caractère à la fois et continuons à essayer de faire correspondre < jusqu'à ce que l'expression régulière revienne à la position

Ensuite, il essaie de faire correspondre / (en évitant la barre oblique inverse), qui correspond avec succès, puis p, qui ne correspond pas. L'expression régulière continue de revenir en arrière et répète ce processus jusqu'à ce qu'elle corresponde enfin à

à la fin du deuxième paragraphe. Pour renvoyer une correspondance réussie, vous devez numériser du début du premier paragraphe à la fin du dernier paragraphe, ce qui peut ne pas être le résultat souhaité.

Changer le quantificateur « gourmand » * dans l'expression régulière par le quantificateur « paresseux » (alias « non gourmand ») * pour correspondre à un seul paragraphe. Le retour en arrière pour les quantificateurs « paresseux » fonctionne de la manière opposée. Lorsque l'expression régulière /

.*?

/ avance vers .*?, elle tente d'abord de les ignorer toutes, puis continue de faire correspondre

.

这样做是因为*?匹配零次或多次，尽可能少重复，尽可能少意味着可以重复零次。但是，当随后的<在字符串的这一点上匹配失败时，正则表达式回溯并尝试下一个最小的字符数：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中文网其它相关文章！

推荐阅读：

正则全局匹配模式g修饰符的使用详解

正则表达式小结（实战归纳）

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!