L'aphorisme "Si au début vous ne réussissez pas, essayez, réessayez" est formalisé en pattern matching dans un processus appelé retour en arrière .Le retour en arrière est la façon dont le matcher vérifie toutes les combinaisons possibles qui pourraient correspondre.Cet article utilise certaines fonctionnalités secrètes du comparateur de modèles de JMP pour exposer le processus de retour en arrière. L'instruction unique ci-dessous est une correspondance de modèle modérément compliquée.Mais même les correspondances simples (et les regex) utiliseront le backtracking.
Secret 1 : la fonction Log() sur la ligne 21 produit une sortie dans la fenêtre du journal JMP. Le >> avant de prendre le texte précédemment mis en correspondance et de l'imprimer, ainsi qu'une position de base zéro dans la source et l'étiquette de texte fournie. Cela n'a rien à voir avec le retour en arrière et tout à voir avec le débogage. Vous pouvez utiliser ce secret pour déboguer vos propres modèles.
Secret 2 : PatTest() a trois arguments, même si un seul est utilisé. Tout est question de retour en arrière. La JSL du deuxième argument est exécutée dans le sens du suivi vers l'avant et la JSL du troisième argument est exécutée dans le sens du retour en arrière.
Secret 3 : PatMatch() optimise normalement l'échec, du mieux qu'il peut. Lorsqu'il constate qu'il ne reste plus assez de texte dans la chaîne source pour correspondre à la longueur minimale restante du motif, il s'arrête. L'option FULLSCAN désactive cette optimisation. Pour cet exemple, le retour arrière semblera s'arrêter prématurément sans l'option FULLSCAN.
Secret 4 : PatFail() peut être utilisé pour trouver toutes les correspondances possibles en forçant chaque correspondance à échouer et à envisager des alternatives.
Voici le code et la sortie avec une explication ci-dessous.
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 réessayer q=A réessayer q=C réessayer q=G réessayer q=D réessayer q=E réessayer réessayer
p=D q=A réessayer q=C réessayer q=G réessayer q=D réessayer q=E
1(TROUVÉ) DACGDE
réessayer réessayer
p=Une nouvelle tentative
p=C q=G réessayer q=D
3(TROUVÉ) CGD
réessayer q=E
3(TROUVÉ) CGDE
réessayer réessayer
p=G q=D réessayer q=E réessayer réessayer
p=D q=E
5(TROUVÉ) DE
réessayer réessayer
p=E réessayer
0
Explication
Tout d'abord, le zéro final. C'est le code de retour, et il indique que la correspondance a échoué. Le match en fait TROUVÉ quatre correspondances, mais le PatFail() l'a amené à en rechercher une autre. C'est prévu.
Ensuite, les P et Q. p commence à E et le test pour > B est heureux. PatArb() est réticent et ne saute initialement rien. q obtient le D après E. Mais l'épreuve est malheureuse cette fois ; q entre p et "F" n'est pas vrai. Il est temps de revenir en arrière ! Le LEN(1) qui a mis le D dans q rend le D en retour et le PatArb() a une chance de faire quelque chose de différent. Cette fois, il prend à contrecœur un caractère, le D. Le PatLen(1) donne alors le A à q. À la fin de la première ligne, il y a deux tentatives ; le second est pour p. La ligne suivante montre p obtenant le deuxième caractère, D. Puisque la correspondance de modèle n'est pas ancrée, le début de la correspondance est autorisé à flotter vers l'avant dans le texte dans le cadre du processus de retour en arrière ; cette fois, le match avance avec le PatArb prenant de plus en plus jusqu'à ce que le premier succès se produise. Le >>Log("FOUND") enregistre le succès dans le journal, puis le PatFail() provoque la poursuite du retour en arrière.
Si ce n'est pas clair, vous pouvez essayer des tests plus simples et les instrumenter avec la méthode >>LOG("tag") pour avoir une idée de ce qui se passe.
À ce stade, il devrait être clair pourquoi ce match dure très, très longtemps :
alors que vous pouvez voir qu'il ne peut pas réussir parce que la chaîne de aaaa...aaa n'a de b nulle part, le matcher doit découvrir qu'en essayant beaucoup de combinaisons idiotes : sauter 2 caractères suivis de sauter 3... et sauter 3 suivi de sauter 2... etc, etc, etc... Le retour en arrière ne peut pas réparer un modèle mal écrit. Cette barre de progression ne signifie pas qu'il est presque terminé. (Il n'y a aucune raison de mettre le patarb dans le patrepeat, sauf pour voir cette boîte de dialogue. Patarb correspond déjà à un nombre arbitraire de caractères.)
mise à jour 1Feb2017 - formatage de réparation pour la nouvelle communauté.
