So verstehen Sie das Backtracking regulärer Ausdrücke in js richtig

Dieses Mal zeige ich Ihnen, wie Sie das Backtracking mit regulären Ausdrücken in js richtig verstehen, welche Vorsichtsmaßnahmen es gibt, um das Backtracking mit regulären Ausdrücken in js korrekt zu verwenden, und im Folgenden finden Sie praktische Fälle , lass uns einen Blick darauf werfen. Bei der Implementierung regulärer Ausdrücke ist Backtracking eine grundlegende Komponente des Matching-Prozesses und der Grund, warum reguläre Ausdrücke so nützlich und leistungsstark sind. Allerdings ist das Zurückverfolgen rechenintensiv und kann bei fehlerhaftem Design zum Kontrollverlust führen. Backtracking ist der einzige Faktor, der sich auf die Gesamtleistung auswirkt. Der Schlüssel zum Schreiben effizienter regulärer Ausdrücke kann sein, zu verstehen, wie es funktioniert und wie man die Häufigkeit seiner Verwendung reduziert.

Wenn ein regulärer Ausdruck die Zielzeichenfolge scannt, von Scan Die Komponenten des regulären Ausdrucks werden nacheinander von links nach rechts durchsucht und geprüft, ob an jeder Position eine Übereinstimmung gefunden werden kann. Für jeden Quantor und Zweig muss festgelegt werden, wie vorzugehen ist. Wenn es sich um einen Quantifizierer handelt (z. B. *, +? oder {2,}), muss der reguläre Ausdruck bestimmen, wann versucht werden soll, weitere Zeichen abzugleichen (über den Operator |). Beginnen Sie mit diesen Wählen Sie eine der Optionen zum Ausprobieren.

Wenn die Regex eine solche Entscheidung trifft, merkt sie sich bei Bedarf eine andere Option zur späteren Verwendung. Wenn das ausgewählte Schema erfolgreich übereinstimmt, scannt der reguläre Ausdruck weiterhin die Vorlage für reguläre Ausdrücke. Wenn auch die restlichen Übereinstimmungen erfolgreich sind, wird der Abgleich beendet. Wenn die gewählte Option jedoch keine Übereinstimmung findet oder wenn nachfolgende Übereinstimmungen fehlschlagen, kehrt die Regex zum letzten Entscheidungspunkt zurück und wählt eine der verbleibenden Optionen aus. Setzen Sie diesen Vorgang fort, bis eine Übereinstimmung gefunden wird oder alle möglichen Permutationen von Quantoren und Verzweigungsoptionen ausprobiert wurden. Anschließend wird der Vorgang abgebrochen, dann zum nächsten Zeichen am Anfang des Vorgangs übergegangen und der Vorgang wiederholt.

Der folgende Code zeigt beispielsweise, wie dieser Prozess Verzweigungen durch Backtracking verarbeitet.

Die obige Zeile des regulären Ausdrucks wird verwendet, um „

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

“ oder „

“ abzugleichen. Zu Beginn des Tests suchten wir nach einem h. Der erste Buchstabe der Zielzeichenfolge war zufällig h, und wir fanden ihn sofort. Als nächstes bietet der Unterausdruck (ello|appy) zwei Verarbeitungsoptionen. Der reguläre Ausdruck wählt die Option ganz links aus (die Zweigauswahl erfolgt immer von links nach rechts), prüft, ob ello mit dem nächsten Zeichen der Zeichenfolge übereinstimmt, und dann stimmt der reguläre Ausdruck mit den folgenden Leerzeichen überein. hello hippohappy hippoAllerdings gerät der reguläre Ausdruck bei der nächsten Übereinstimmung „in eine Sackgasse“, da das h in hippo nicht mit dem nächsten Buchstaben t in der Zeichenfolge übereinstimmen kann. Der reguläre Ausdruck kann an dieser Stelle nicht aufgeben, da er noch nicht alle Optionen ausprobiert hat. Daher kehrt er zum letzten Prüfpunkt zurück (nachdem er mit dem anfänglichen h übereinstimmt) und versucht, die zweite Verzweigungsoption zu finden. Da der Abgleich jedoch nicht erfolgreich war und es keine weiteren Optionen gab, ging der reguläre Ausdruck davon aus, dass der Abgleich ab dem ersten Zeichen der Zeichenfolge nicht erfolgreich sein würde, und begann die Suche erneut ab dem zweiten Zeichen. Der reguläre Ausdruck konnte kein h finden, also suchte er weiter rückwärts, bis er den 14. Buchstaben fand, der mit dem glücklichen h übereinstimmte. Dann verzweigt der reguläre Ausdruck erneut, und dieses Mal findet ello keine Übereinstimmung, aber im zweiten Zweig nach dem Zurückverfolgen findet er eine Übereinstimmung mit der gesamten Zeichenfolge „happy hippo“, und die Übereinstimmung ist erfolgreich.

Als weiteres Beispiel demonstriert der folgende Code das Backtracking mit wiederholten Quantifizierern.

Der reguläre Ausdruck entspricht zuerst den drei Buchstaben

am Anfang der Zeichenfolge und dann .*. Der Punkt bedeutet, dass alle Zeichen außer Zeilenumbrüchen übereinstimmen, und das Sternchen, ein „gieriger“ Quantifizierer, bedeutet, dass es null oder mehrere Male wiederholt wird, um so viele Übereinstimmungen wie möglich zu erzielen. Da die Zielzeichenfolge keine Zeilenumbrüche enthält, stimmt der reguläre Ausdruck mit der gesamten verbleibenden Zeichenfolge überein! Da jedoch in der Regex-Vorlage mehr Inhalte vorhanden sind, die übereinstimmen, versucht die Regex, mit < übereinzustimmen. Da der Abgleich am Ende der Zeichenfolge fehlschlägt, gehen wir jeweils ein Zeichen zurück und versuchen, einen Abgleich mit < durchzuführen, bis der reguläre Ausdruck an die Position

zurückkehrt. Als nächstes wird versucht, eine Übereinstimmung mit / zu finden (wobei der Backslash maskiert wird), was erfolgreich zutrifft, und dann mit p, was nicht der Fall ist. Der reguläre Ausdruck geht weiter zurück und wiederholt diesen Vorgang, bis er schließlich mit

übereinstimmt. Um eine erfolgreiche Übereinstimmung zurückzugeben, muss vom Kopf des ersten Absatzes bis zum Ende des letzten Absatzes gescannt werden, was möglicherweise nicht das gewünschte Ergebnis ist.

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

Den Quantifizierer „gierig“ * im regulären Ausdruck in den Quantifizierer „faul“ (auch bekannt als „nicht gierig“) * ändern, um eine Übereinstimmung mit einem einzelnen Absatz zu erzielen. Das Backtracking für „faule“ Quantoren funktioniert umgekehrt. Wenn der reguläre Ausdruck /

.*?

/ zu .*? wechselt, versucht er zunächst, sie alle zu überspringen, und sucht dann weiterhin nach

.

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

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

Das obige ist der detaillierte Inhalt vonSo verstehen Sie das Backtracking regulärer Ausdrücke in js richtig. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!