L'aforisma "Se all'inizio non ci riesci, prova, riprova" è formalizzato nel pattern matching in un processo chiamato tornare indietro .Il backtracking è il modo in cui il matcher controlla tutte le possibili combinazioni che potrebbero corrispondere.Questo post utilizza alcune funzionalità segrete nel pattern matcher di JMP per esporre il processo di backtracking. La singola affermazione di seguito è una corrispondenza di pattern moderatamente complicata.Ma anche le partite semplici (e le espressioni regolari) utilizzeranno il backtracking.
Segreto 1: la funzione Log() alla riga 21 produce l'output nella finestra del registro di JMP. Il >> prima di prendere il testo precedentemente abbinato e stamparlo, insieme a una posizione in base zero nella fonte e all'etichetta di testo fornita. Questo non ha nulla a che fare con il backtracking e tutto a che fare con il debug. Puoi usare questo segreto per eseguire il debug dei tuoi schemi.
Segreto 2: PatTest() ha tre argomenti, anche se solo uno viene utilizzato. Si tratta di tornare indietro. La JSL nel secondo argomento viene eseguita nella direzione di forward-tracking e la JSL nel terzo argomento viene eseguita nella direzione di backtracking.
Segreto 3: PatMatch() normalmente ottimizza il fallimento, nel miglior modo possibile. Quando vede che non ci sarà abbastanza testo rimanente nella stringa di origine per corrispondere alla lunghezza minima rimanente del modello, si interrompe. L'opzione FULLSCAN disattiva tale ottimizzazione. Per questo esempio, il backtracking sembrerà interrompersi prematuramente senza l'opzione FULLSCAN.
Segreto 4: PatFail() può essere utilizzato per trovare tutte le possibili corrispondenze forzando ogni corrispondenza a fallire e le alternative da considerare.
Ecco il codice e l'output con una spiegazione di seguito.
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 riprova q=A riprova q=C riprova q=G riprova q=D riprova q=E riprova riprova
p=D q=Riprova A q=Riprova C q=Riprova G q=Riprova D q=E
1(TROVATO) DACGDE
riprova riprova
p=Un nuovo tentativo
p=C q=G riprovare q=D
3(TROVATO) CGD
riprovare q=E
3(TROVATO) CGDE
riprova riprova
p=G q=D riprova q=E riprova riprova
p=Dq=E
5(TROVATO) DE
riprova riprova
p=E riprova
0
Spiegazione
Primo, lo zero finale. Questo è il codice di ritorno e dice che la corrispondenza non è riuscita. La partita in realtà FONDARE quattro corrispondenze, ma PatFail() ne ha cercato un'altra. Questo è previsto.
Successivamente, Ps e Qs. p inizia da E e il test per >B è felice. PatArb() è riluttante e inizialmente non salta nulla. q ottiene la D dopo la E. Ma questa volta la prova è infelice; q tra p e "F" non è vero. È ora di tornare indietro! La LEN(1) che mette la D in q restituisce la D e a PatArb() viene data la possibilità di fare qualcosa di diverso. Questa volta prende a malincuore un personaggio, il D. Il PatLen(1) fornisce quindi A a q. Alla fine della prima riga, ci sono due tentativi; il secondo è per p. La riga successiva mostra p che ottiene il secondo carattere, D. Poiché la corrispondenza del modello non è ancorata, l'inizio della corrispondenza può scorrere in avanti nel testo come parte del processo di backtracking; questa volta il match va avanti con il PatArb che prende sempre di più fino al primo successo. >>Log("TROVATO") registra l'esito positivo nel registro, quindi PatFail() fa sì che il backtracking continui.
Se non è chiaro, puoi provare test più semplici e strumentali con il metodo >>LOG("tag") per avere un'idea di cosa sta succedendo.
A questo punto dovrebbe essere chiaro perché questa partita durerà per molto, molto tempo:
mentre puoi vedere che non può avere successo perché la stringa di aaaa...aaa non ha b da nessuna parte, il matcher deve scoprirlo provando molte combinazioni sciocche: salta 2 caratteri seguiti da salta 3... e salta 3 seguito da skip 2... etc, etc, etc.... Il backtracking non può correggere uno schema scritto male. Quella barra di avanzamento non significa che sia quasi finita. (Non c'è motivo per mettere il patarb all'interno del patrepeat, tranne per vedere questa finestra di dialogo. Patarb corrisponde già a un numero arbitrario di caratteri.)
aggiornamento 1 febbraio 2017 - ripara la formattazione per la nuova comunità.
