Der Aphorismus „Wenn es dir beim ersten Mal nicht gelingt, versuche es, versuche es noch einmal“ wird beim Mustervergleich in einem Prozess namens formalisiert zurückverfolgen .Beim Backtracking überprüft der Matcher alle möglichen Kombinationen, die übereinstimmen könnten.Dieser Beitrag verwendet einige geheime Funktionen im Musterabgleicher von JMP, um den Backtracking-Prozess aufzudecken. Die einzelne Anweisung unten ist eine mäßig komplizierte Musterübereinstimmung.Aber auch einfache Übereinstimmungen (und reguläre Ausdrücke) verwenden Backtracking.
Geheimnis 1: Die Funktion Log() in Zeile 21 erzeugt eine Ausgabe im JMP-Protokollfenster. Das >> davor nimmt den zuvor abgeglichenen Text und druckt ihn zusammen mit einer nullbasierten Position in der Quelle und dem bereitgestellten Textlabel. Das hat nichts mit Backtracking zu tun, sondern alles mit Debugging. Sie können dieses Geheimnis verwenden, um Ihre eigenen Muster zu debuggen.
Geheimnis 2: PatTest() hat drei Argumente, obwohl immer nur eines verwendet wird. Hier dreht sich alles ums Zurückverfolgen. Die JSL im zweiten Argument wird in der Vorwärtsverfolgungsrichtung ausgeführt und die JSL im dritten Argument wird in der Rückwärtsverfolgungsrichtung ausgeführt.
Geheimnis 3: PatMatch() optimiert Fehler normalerweise so gut es geht. Wenn es sieht, dass nicht genug Text in der Quellzeichenfolge verbleibt, um mit der verbleibenden Mindestlänge des Musters übereinzustimmen, stoppt es. Die Option FULLSCAN schaltet diese Optimierung aus. In diesem Beispiel scheint das Backtracking ohne die Option FULLSCAN vorzeitig zu stoppen.
Geheimnis 4: PatFail() kann verwendet werden, um alle möglichen Übereinstimmungen zu finden, indem jede Übereinstimmung zum Scheitern gezwungen wird und Alternativen in Betracht gezogen werden.
Hier ist der Code und die Ausgabe mit einer Erklärung unten.
Pat Match(
"EDACGDE", // a contrived string to exercise backtracking
(
Pat Len( 1 ) >> p // match a character, store in p
+
Pat Test(
p > "B", // test
Write( "p=", p, " " ), // advance
Write( "retry\!n" ) // backtrack
)
+
Pat Arb() // skip zero or more characters
+
Pat Len( 1 ) >> q // match another, store in q
+
Pat Test(
p < q & q < "F", // test
Write( "q=", q, " " ), // advance
Write( "retry " ) // backtrack
)
) >> Log( "FOUND" ) // a debugging tool
+
Pat Fail(), // try alternatives
NULL, // no replacement
FULLSCAN // to the bitter end
);
p=E q=D Neuversuch q=A Neuversuch q=C Neuversuch q=G Neuversuch q=D Neuversuch q=E Neuversuch Neuversuch
p=D q=A Neuversuch q=C Neuversuch q=G Neuversuch q=D Neuversuch q=E
1 (GEFUNDEN) DACGDE
erneut versuchen erneut versuchen
p=Eine Wiederholung
p=C q=G erneut versuchen q=D
3 (GEFUNDEN) CGD
Wiederholen Sie q=E
3(GEFUNDEN) CGDE
erneut versuchen erneut versuchen
p=G q=D Wiederholung q=E Wiederholung Wiederholung
p=D q=E
5(GEFUNDEN)DE
erneut versuchen erneut versuchen
p=E erneut versuchen
0
Erläuterung
Zuerst die letzte Null. Das ist der Rückgabecode, und er besagt, dass die Übereinstimmung fehlgeschlagen ist. Eigentlich das Spiel GEFUNDEN vier Übereinstimmungen, aber das PatFail() veranlasste es, nach einem anderen zu suchen. Dies wird erwartet.
Als nächstes die Ps und Qs. p beginnt bei E und der Test für >B ist glücklich. PatArb() ist zurückhaltend und überspringt zunächst nichts. q erhält das D nach E. Aber der Test ist dieses Mal unglücklich; q zwischen p und "F" ist nicht wahr. Zeit zum Rückzug! Die LEN(1), die das D in q eingefügt hat, gibt das D zurück, und PatArb() erhält die Möglichkeit, etwas anderes zu tun. Diesmal nimmt es widerwillig ein Zeichen, das D. Die PatLen(1) gibt dann das A an q. Am Ende der ersten Zeile gibt es zwei Wiederholungen; die zweite ist für p. Die nächste Zeile zeigt, wie p das zweite Zeichen D erhält. Da die Musterübereinstimmung nicht verankert ist, darf der Anfang der Übereinstimmung als Teil des Backtracking-Prozesses vorwärts durch den Text fließen; Diesmal geht das Match vorwärts, wobei der PatArb immer mehr nimmt, bis der erste Erfolg eintritt. Das >>Log("FOUND") zeichnet den Erfolg im Log auf, dann bewirkt das PatFail(), dass das Backtracking fortgesetzt wird.
Wenn es nicht klar ist, können Sie einfachere Tests ausprobieren und sie mit der >>LOG("tag")-Methode instrumentieren, um ein Gefühl dafür zu bekommen, was passiert.
An dieser Stelle sollte klar sein, warum dieses Match sehr, sehr lange läuft:
Während Sie sehen können, dass es unmöglich sein kann, weil die Zeichenfolge von aaaa ... aaa nirgendwo ein b enthält, muss der Matcher dies entdecken, indem er viele dumme Kombinationen ausprobiert: Überspringe 2 Zeichen, gefolgt von überspringe 3 ... und überspringe 3 gefolgt von überspringen 2 ... etc, etc, etc .... Backtracking kann ein schlecht geschriebenes Muster nicht reparieren. Dieser Fortschrittsbalken bedeutet nicht, dass es fast fertig ist. (Es gibt keinen Grund, das Patarb in das Patrepeat zu legen, außer um diesen Dialog zu sehen. Patarb passt bereits auf eine beliebige Anzahl von Zeichen.)
Update 1. Februar 2017 - Formatierung für neue Community reparieren.
