Backtracking-Definition und Nutzungsanalyse in regulären Ausdrücken [JS- und Java-Implementierung]

Dieser Artikel analysiert die Definition und Verwendung von Backtracking in regulären Ausdrücken anhand von Beispielen. Ich möchte es Ihnen als Referenz mitteilen:

Dies ist mein erster Kontakt mit „Backtracking“ und ich weiß nicht viel darüber. Jetzt werde ich zum späteren Nachschlagen aufzeichnen, was ich als geistige Tugend verstehe.

Die Übereinstimmungsbasis der von uns verwendeten regulären Ausdrücke ist grob unterteilt in: Priorität für das am weitesten links stehende (am weitesten beginnende) Übereinstimmungsergebnis und Standard-Übereinstimmungsquantifizierer (*, +, ? und {m, n}). Übereinstimmungen werden durchgeführt Vorrang.

„Bevorzugen Sie die Übereinstimmung ganz links“, wie der Name schon sagt, ist die Übereinstimmung vom Anfang der Zeichenfolge bis zum Ende der Übereinstimmung. Dies ist die Basis für die Unterteilung in „Nicht-Übereinstimmung“. „deterministischer endlicher Automat (NFA)“ kann auch als „ausdrucksgesteuert“ bezeichnet werden; der andere ist „deterministischer endlicher Automat (DFA)“, der auch als „textgesteuert“ bezeichnet werden kann. Die regulären Ausdrücke, die wir derzeit in JavaScript verwenden, sind „ausdrucksgesteuert“. Ausdrucksdominanz und Textdominanz sind etwas schwierig zu erklären. Vielleicht wird es klarer, wenn wir uns zuerst ein Beispiel ansehen.

// 使用正则表达式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

Im obigen Beispiel, dem ersten Element [t], wird es wiederholt versucht, bis 't in der Zielzeichenfolge 'until' gefunden wird. Danach prüft es, ob das folgende Zeichen mit [o] übereinstimmt, und wenn ja, prüft es das folgende Element (nite|knight|night). Seine eigentliche Bedeutung ist „Ende“, „Ritter“ oder „Nacht“. Die Engine probiert diese drei Möglichkeiten nacheinander aus. Der Prozess des Ausprobierens von [nite] besteht darin, zuerst [n], dann [i], dann [t] und schließlich [e] auszuprobieren. Wenn dieser Versuch fehlschlägt, versucht die Engine eine andere Möglichkeit usw., bis eine Übereinstimmung erfolgreich ist oder ein Fehler gemeldet wird. Die Kontrolle in einem Ausdruck wird zwischen verschiedenen Elementen übertragen, daher der Name „Ausdrucksdominanz“.

Wie im obigen Beispiel zeichnet „textgeführt“ beim Scannen der Zeichenfolge alle aktuell gültigen Übereinstimmungen auf. Wenn sich die Engine auf t bewegt, fügt sie ein Potenzial zu den aktuell verarbeiteten Übereinstimmungsmöglichkeiten hinzu:

Jedes als nächstes gescannte Zeichen aktualisiert die aktuelle mögliche Übereinstimmungssequenz. Nach dem weiteren Scannen von zwei Zeichen ist die Situation wie folgt:

Aus den gültigen möglichen Übereinstimmungen werden zwei (Ritter wird eliminiert). Wenn g gescannt wird, gibt es nur noch eine mögliche Übereinstimmung. Wenn h und t übereinstimmen, stellt die Engine fest, dass die Übereinstimmung abgeschlossen ist, und meldet den Erfolg. „Textdominiert“, weil jedes Zeichen in der gescannten Zeichenfolge die Engine steuert.

Wenn du verstehen willst, wie „Expression Leadership“ funktioniert, dann schau dir heute unser Thema „Backtracking“ an. Das Zurückfahren ist wie eine Weggabelung. Wenn Sie auf eine Weggabelung stoßen, markieren Sie zunächst jede Kreuzung. Wenn Sie in eine Sackgasse geraten, können Sie den gleichen Weg zurückgehen, den Sie gekommen sind, bis Sie auf ein Schild stoßen, das Sie zuvor gemacht haben und das eine Straße markiert, die Sie noch nicht beschritten haben. Wenn Sie diesen Weg nicht gehen können, können Sie weiter zurückgehen, die nächste Markierung suchen und den Vorgang wiederholen, bis Sie einen Ausweg gefunden haben oder bis Sie alle unerprobten Wege geschafft haben.

In vielen Fällen muss die Regex-Engine zwischen zwei (oder mehr) Optionen wählen. Wenn /…x?…/ auftritt, muss die Engine versuchen, mit X übereinzustimmen oder nicht. Für den Fall von /... Nach den ersten X-Matches ist diese Anforderung erfüllt und es muss entschieden werden, ob das nächste X versucht werden soll. Wenn Sie fortfahren möchten, müssen Sie auch entscheiden, ob das dritte X, das vierte X usw. übereinstimmen sollen. Jedes Mal, wenn Sie eine Auswahl treffen, machen Sie tatsächlich eine Markierung, um Sie daran zu erinnern, dass es hier eine weitere mögliche Auswahl gibt, die für die zukünftige Verwendung reserviert ist. Beim Backtracking-Prozess sind zwei wichtige Punkte zu beachten: Welcher Zweig sollte zuerst ausgewählt werden? Welche (oder welche) zuvor gespeicherten Zweige werden beim Backtracking verwendet?

Die erste Frage wird nach dem folgenden wichtigen Prinzip ausgewählt:

Wenn Sie zwischen „Versuch durchführen“ und „Durchlaufversuch“ wählen müssen, wird für den passenden Prioritätsquantifizierer die Engine verwendet Will wird bevorzugt „Einen Versuch machen“ gewählt, während für das Ignorieren des Vorrangquantifizierers „Vorbeigehen-Versuch“ gewählt wird.

Die zweite Frage basiert auf dem folgenden Prinzip:

Die zuletzt gespeicherte Option ist diejenige, die zurückgegeben wird, wenn ein lokaler Fehler einen Backtrace erzwingt. Das verwendete Prinzip ist LIFO (Last In First Out).

Sehen wir uns zunächst ein paar Beispiele für die Markierung von Straßen an:

1. Matching ohne Backtracking

Verwenden Sie [ab?c], um „abc“ zuzuordnen. [a] Nach dem Abgleich ist der aktuelle Status des Abgleichs wie folgt:

现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把：

添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b?]之后，字符串的c之前（也就是说当前的位置）匹配。这实际上就是跳过[b]的匹配，而问题容许这样做。引擎做好标记后，就会继续向前检查[b]。在示例中，它能够匹配，所以新的当前状态变为：

最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。

2、进行了回溯的匹配

下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。

在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。

3、不成功的匹配

现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：

[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。

例子1： 提取字符串 提取 da12bka3434bdca4343bdca234bm 提取包含在字符a和b之间的数字，但是这个a之前的字符不能是c,b后面的字符必须是d才能提取。

例如这里就只有3434这个数字满足要求。那么我们怎么提取呢？

首先我们写出提取这个字符串的表达式： (?

Java代码片段如下：

Pattern p = Pattern.compile( "(?<!c)a(//d+)bd " );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
 while (m.find()){
 System.out.println(m.group( 1 )); //我们只要捕获组1的数字即可。结果 3434
 System.out.println(m.group(0)); // 0组是整个表达式，看这里，并没有提炼出(?<!c)的字符 。结果 a3434bd
}

例子2： 将一些多位的小数截短到三位小数：\d+\.\d\d[1-9]?\d+

在这种条件下 6.625 能进行匹配，这样做没有必要，因为它本身就是三位小数。最后一个“5”本来是给 [1-9] 匹配的，但是后面还有一个 \d+ 所以，[1-9] 由于是“?”可以不匹配所以只能放弃当前的匹配，将这个“5”送给 \d+ 去匹配，如果改为：

\d+\.\d\d[1-9]?+\d+

的侵占形式，在“5”匹配到 [1-9] 时，由于是侵占式的，所以不会进行回溯，后面的 \d+ 就匹配不到任东西了，所以导致 6.625 匹配失败。

这种情况，在替换时就有效了，比如把数字截短到小数点后三位，如果正好是三位小数的，就可以不用替换了，可以提高效率，侵占量词基本上就是用来提高匹配效率的。

把 \d+\.\d\d[1-9]?+\d+ 改为 \d+\.\d\d(?>[1-9]?)\d+ 这样是一样的。

希望本文所述对大家JavaScript程序设计有所帮助。

更多Backtracking-Definition und Nutzungsanalyse in regulären Ausdrücken [JS- und Java-Implementierung]相关文章请关注PHP中文网！