Avidi contro riluttanti contro quantificatori possessivi
Ho trovato questo eccellente tutorial sulle espressioni regolari e mentre capisco intuitivamente cosa fanno i quantificatori "avidi", "riluttanti" e "possessivi", sembra esserci un grave buco nella mia comprensione.
In particolare, nel seguente esempio:
Enter your regex: .*foo // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.
Enter your regex: .*?foo // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.
Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.
La spiegazione menziona il consumo dell'intera stringa di input, le lettere consumate , il ritiro del matcher , l'occorrenza più a destra di "foo" è stata rigurgitata , ecc.
Purtroppo, nonostante le simpatiche metafore, non riesco ancora a capire cosa viene mangiato da chi ... Conosci un altro tutorial che spiega (sinteticamente) come funzionano i motori delle espressioni regolari?
In alternativa, se qualcuno può spiegare in una frase un po 'diversa il seguente paragrafo, sarebbe molto apprezzato:
Il primo esempio utilizza il quantificatore avido. * Per trovare "qualsiasi cosa", zero o più volte, seguito dalle lettere "f" "o" "o". Poiché il quantificatore è avido, la parte. * Dell'espressione mangia prima l'intera stringa di input. A questo punto, l'espressione complessiva non può avere successo, perché le ultime tre lettere ("f" "o" "o") sono già state consumate ( da chi? ). Quindi il matcher indietreggia lentamente ( da destra a sinistra? ) Una lettera alla volta fino a quando l'occorrenza più a destra di "foo" è stata rigurgitata ( cosa significa? ), A quel punto la corrispondenza ha successo e la ricerca termina.
Il secondo esempio, tuttavia, è riluttante, quindi inizia prima consumando ( da chi? ) "Niente". Poiché "pippo" non appare all'inizio della stringa, è costretto a ingoiare ( chi ingoia?) La prima lettera (una "x"), che attiva la prima corrispondenza a 0 e 4. Il nostro test harness continua il processo fino all'esaurimento della stringa di input. Trova un'altra corrispondenza a 4 e 13.
Il terzo esempio non riesce a trovare una corrispondenza perché il quantificatore è possessivo. In questo caso, l'intera stringa di input viene consumata da. * +, ( Come? ) Senza lasciare nulla per soddisfare il "foo" alla fine dell'espressione. Usa un quantificatore possessivo per le situazioni in cui vuoi cogliere tutto qualcosa senza mai tirarti indietro ( cosa significa fare marcia indietro? ); supererà il quantificatore avido equivalente nei casi in cui la corrispondenza non viene trovata immediatamente.
Risposte
Ci proverò.
Un quantificatore avido corrisponde prima il più possibile. Quindi .*corrisponde all'intera stringa. Quindi il matcher cerca di abbinare quanto fsegue, ma non ci sono caratteri rimasti. Quindi "torna indietro", facendo corrispondere al quantificatore avido un carattere in meno (lasciando la "o" alla fine della stringa senza corrispondenza). Questo ancora non corrisponde alla fregex, quindi torna indietro di un altro passaggio, facendo sì che il quantificatore avido corrisponda di nuovo a un carattere in meno (lasciando la "oo" alla fine della stringa senza corrispondenza). Questo ancora non corrisponde alla fregex, quindi torna indietro di un altro passaggio (lasciando il "pippo" alla fine della stringa senza corrispondenza). Ora, il matcher alla fine corrisponde fa nella regex, e anche il oe il successivo osono abbinati. Successo!
Un quantificatore riluttante o "non avido" corrisponde prima il meno possibile. Quindi all'inizio .*non corrisponde nulla, lasciando l'intera stringa senza corrispondenza. Quindi il matcher cerca di trovare la corrispondenza con quanto fsegue, ma la parte non corrispondente della stringa inizia con "x", quindi non funziona. Quindi il matcher torna indietro, facendo corrispondere al quantificatore non avido un carattere in più (ora corrisponde alla "x", lasciando "fooxxxxxxfoo" senza corrispondenza). Quindi cerca di abbinare il f, che riesce, e anche il oe il successivo onella corrispondenza regex. Successo!
Nel tuo esempio, inizia quindi il processo con la parte rimanente senza corrispondenza della stringa, "xxxxxxfoo", seguendo lo stesso processo.
Un quantificatore possessivo è proprio come il quantificatore avido, ma non torna indietro. Quindi inizia con la .*corrispondenza dell'intera stringa, senza lasciare nulla di ineguagliato. Quindi non c'è più niente da abbinare falla regex. Poiché il quantificatore possessivo non torna indietro, la corrispondenza fallisce lì.
È solo il mio output di pratica per visualizzare la scena-
Non ho mai sentito i termini esatti "rigurgitare" o "fare marcia indietro"; la frase che li sostituirà è "backtracking", ma "rigurgitate" sembra una frase buona quanto qualsiasi per "il contenuto che era stato provvisoriamente accettato prima che il backtracking lo gettasse di nuovo via".
La cosa importante da realizzare sulla maggior parte dei motori di regex è che stanno tornando indietro : accetteranno provvisoriamente una potenziale corrispondenza parziale, mentre cercano di abbinare l'intero contenuto della regex. Se la regex non può essere completamente abbinata al primo tentativo, il motore di regex tornerà indietro su una delle sue corrispondenze. Sarà provare la corrispondenza *, +, ?, alternanza, o {n,m}ripetizione diverso e riprovare. (E sì, questo processo può richiedere molto tempo.)
Il primo esempio utilizza il quantificatore avido. * Per trovare "qualsiasi cosa", zero o più volte, seguito dalle lettere "f" "o" "o". Poiché il quantificatore è avido, la parte. * Dell'espressione mangia prima l'intera stringa di input. A questo punto, l'espressione complessiva non può avere successo, perché le ultime tre lettere ("f" "o" "o") sono già state consumate ( da chi? ).
Le ultime tre lettere, f, o, e osono stati già consumati dalla prima .*parte della regola. Tuttavia, l'elemento successivo della regex,, fnon ha più nulla nella stringa di input. Il motore sarà costretto a tornare indietro sulla sua .*corrispondenza iniziale e provare a far corrispondere tutti i caratteri tranne l'ultimo. (Potrebbe essere intelligente e tornare indietro a tutti tranne gli ultimi tre, perché ha tre termini letterali, ma non sono a conoscenza dei dettagli di implementazione a questo livello.)
Quindi il matcher indietreggia lentamente ( da destra a sinistra? ) Una lettera alla volta finché l'occorrenza più a destra di "foo" è stata rigurgitata ( cosa significa? ), In cui
Ciò significa che fooera stato provvisoriamente incluso durante la corrispondenza .*. Poiché il tentativo non è riuscito, il motore regex tenta di accettare un carattere in meno in .*. Se ci fosse stata una partita riuscita prima del .*in questo esempio, allora il motore probabilmente proverebbe ad accorciare la .*corrispondenza (da destra a sinistra, come hai sottolineato, perché è un qualificatore avido), e se non fosse in grado di abbinare l'intero ingressi, allora potrebbe essere costretto a rivalutare ciò che aveva abbinato prima che il .*mio esempio ipotetico.
punto la corrispondenza ha successo e la ricerca finisce.
Il secondo esempio, tuttavia, è riluttante, quindi inizia prima consumando ( da chi? ) "Niente". Perché "foo"
Il nulla iniziale viene consumato da .?*, che consumerà la quantità più breve possibile di qualsiasi cosa che consenta al resto della regex di corrispondere.
non compare all'inizio della stringa, è costretto ad ingoiare ( chi ingoia?) il
Ancora una volta .?*consuma il primo carattere, dopo essere tornato indietro sull'errore iniziale di abbinare l'intera regex con la corrispondenza più breve possibile. (In questo caso, il motore regex sta estendendo la corrispondenza per .*?da sinistra a destra, perché .*?è riluttante.)
prima lettera (una "x"), che attiva la prima corrispondenza a 0 e 4. Il nostro test harness continua il processo fino a quando la stringa di input è esaurita. Trova un'altra corrispondenza a 4 e 13.
Il terzo esempio non riesce a trovare una corrispondenza perché il quantificatore è possessivo. In questo caso, l'intera stringa di input viene consumata da. * +, ( Come? )
A .*+consumerà il più possibile e non tornerà indietro per trovare nuove corrispondenze quando l'espressione regolare nel suo complesso non riesce a trovare una corrispondenza. Perché la forma possessiva non esegue il backtracking, probabilmente non vedrete molti usi con .*+, ma piuttosto con classi di personaggi o restrizioni simili: account: [[:digit:]]*+ phone: [[:digit:]]*+.
Questo può accelerare drasticamente la corrispondenza delle espressioni regolari, perché stai dicendo al motore di regex che non dovrebbe mai tornare indietro sulle potenziali corrispondenze se un input non corrisponde. (Se dovessi scrivere tutto il codice corrispondente a mano, sarebbe simile a non usare mai putc(3)per "respingere" un carattere di input. Sarebbe molto simile al codice ingenuo che si potrebbe scrivere al primo tentativo. Ad eccezione dei motori regex sono molto meglio di un singolo carattere di push-back, possono riavvolgere tutto il back fino a zero e riprovare. :)
Ma più che potenziali aumenti di velocità, questo può anche permetterti di scrivere regex che corrispondono esattamente a ciò che devi abbinare. Ho problemi a trovare un semplice esempio :) ma scrivere una regex usando quantificatori possessivi o avidi può darti corrispondenze diverse e l'una o l'altra potrebbe essere più appropriata.
non lasciare nulla per soddisfare il "foo" alla fine dell'espressione. Usa un quantificatore possessivo per le situazioni in cui vuoi cogliere tutto qualcosa senza mai tirarti indietro ( cosa significa fare marcia indietro? ); supererà
"Fare marcia indietro" in questo contesto significa "tornare indietro" - buttare via una partita parziale provvisoria per provare un'altra partita parziale, che può o non può avere successo.
il quantificatore avido equivalente nei casi in cui la corrispondenza non viene trovata immediatamente.
http://swtch.com/~rsc/regexp/regexp1.html
Non sono sicuro che sia la migliore spiegazione su Internet, ma è ragionevolmente ben scritta e adeguatamente dettagliata, e continuo a tornarci sopra. Potresti volerlo controllare.
Se vuoi un livello più alto (spiegazione meno dettagliata), per espressioni regolari semplici come quella che stai guardando, un motore di espressioni regolari funziona con il backtracking. Essenzialmente, sceglie ("mangia") una sezione della stringa e cerca di far corrispondere l'espressione regolare a quella sezione. Se corrisponde, bene. In caso contrario, il motore modifica la scelta della sezione della stringa e cerca di far corrispondere la regexp a quella sezione, e così via, fino a quando non ha provato ogni scelta possibile.
Questo processo viene utilizzato in modo ricorsivo: nel tentativo di abbinare una stringa con una data espressione regolare, il motore suddividerà l'espressione regolare in parti e applicherà l'algoritmo a ciascuna parte individualmente.
La differenza tra quantificatori avidi, riluttanti e possessivi entra in gioco quando il motore sta facendo le sue scelte su quale parte della stringa cercare di confrontarsi e come modificare quella scelta se non funziona la prima volta. Le regole sono le seguenti:
Un quantificatore avido dice al motore di iniziare con l' intera stringa (o almeno, tutto ciò che non è già stato trovato nelle parti precedenti dell'espressione regolare) e controlla se corrisponde all'espressione regolare. Se è così, fantastico; il motore può continuare con il resto dell'espressione regolare. In caso contrario, riprova, ma tagliando un carattere (l'ultimo) dalla sezione della stringa da controllare. Se non funziona, taglia un altro personaggio, ecc. Quindi un quantificatore avido controlla le possibili corrispondenze in ordine dal più lungo al più breve.
Un quantificatore riluttante dice al motore di iniziare con il pezzo più corto possibile della corda. Se corrisponde, il motore può continuare; in caso contrario, aggiunge un carattere alla sezione della stringa da controllare e lo prova, e così via finché non trova una corrispondenza o l'intera stringa è stata utilizzata. Quindi un quantificatore riluttante controlla le possibili corrispondenze in ordine dal più breve al più lungo.
Un quantificatore possessivo è come un quantificatore avido al primo tentativo: dice al motore di avviarsi controllando l'intera stringa. La differenza è che se non funziona, il quantificatore possessivo segnala che la corrispondenza è fallita in quel momento. Il motore non cambia la sezione della stringa che si sta guardando e non fa più tentativi.
Questo è il motivo per cui la corrispondenza del quantificatore possessivo fallisce nel tuo esempio: .*+viene controllata l'intera stringa, che corrisponde, ma poi il motore continua a cercare caratteri aggiuntivi foodopo di che - ma ovviamente non li trova, perché tu sei già alla fine della stringa. Se fosse un quantificatore avido, tornerebbe indietro e proverebbe a fare l' .*unica corrispondenza fino al penultimo carattere, poi fino al terzultimo carattere, quindi fino al quartultimo carattere, il che riesce perché solo allora è c'è una foosinistra dopo che .*ha "mangiato" la parte precedente della stringa.
Ecco la mia opinione usando le posizioni delle celle e dell'indice (vedere il diagramma qui per distinguere una cella da un indice).
Greedy: abbina il più possibile al quantificatore avido e all'intera regex. Se non c'è corrispondenza, torna indietro sul quantificatore avido.
Stringa di input: xfooxxxxxxfoo
Regex:. * Foo
Il precedente Regex ha due parti:
(i) '. *' E
(ii) 'foo'
Ciascuno dei passaggi seguenti analizzerà le due parti. Ulteriori commenti per una corrispondenza con "Pass" o "Fail" sono spiegati tra parentesi graffe.
Passaggio 1:
(i). * = Xfooxxxxxxfoo - PASS ('. *' È un quantificatore avido e utilizzerà l'intera stringa di input)
(ii) foo = Nessun carattere rimasto per la corrispondenza dopo l'indice 13 - FAIL
Match non riuscito.
Passaggio 2:
(i). * = Xfooxxxxxxfo - PASS (Backtracking on the greedy quantificier '. *')
(Ii) foo = o - FAIL
Match failed.
Passaggio 3:
(i). * = Xfooxxxxxxf - PASS (Backtracking on the greedy quantificier '. *')
(Ii) foo = oo - FAIL
Match failed.
Passaggio 4:
(i). * = Xfooxxxxxx - PASS (Backtracking on the greedy quantificier '. *')
(Ii) foo = foo - PASS
Report MATCH
Risultato: 1 corrispondenza / e
Ho trovato il testo "xfooxxxxxxfoo" che inizia con l'indice 0 e termina con l'indice 13.
Riluttante: abbina il meno possibile al quantificatore riluttante e abbina l'intera regex. se non c'è corrispondenza, aggiungi caratteri al quantificatore riluttante.
Stringa di input: xfooxxxxxxfoo
Regex:. *? Foo
L'espressione regolare precedente ha due parti:
(i) '. *?' e
(ii) "foo"
Passaggio 1:.
*? = '' (vuoto) - PASS (Abbina il meno possibile al quantificatore riluttante '. *?'. L'indice 0 che ha '' è una corrispondenza.)
foo = xfo - FAIL (Cella 0,1,2 - cioè indice tra 0 e 3)
Match fallito.
Passaggio 2:.
*? = x - PASS (Aggiungi caratteri al quantificatore riluttante ". *?". La cella 0 con "x" corrisponde.)
foo = foo - PASSO
Report MATCH
Passaggio 3:.
*? = '' (vuoto) - PASS (Trova la corrispondenza il meno possibile con il quantificatore riluttante '. *?'. L'indice 4 che ha '' è una corrispondenza.)
foo = xxx - FAIL (Cella 4,5,6 - cioè indice tra 4 e 7)
Partita fallita.
Passaggio 4:.
*? = x - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella 4.)
foo = xxx - FAIL (Cella 5,6,7 - cioè indice tra 5 e 8)
Corrispondenza non riuscita.
Passaggio 5:.
*? = xx - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella da 4 a 5.)
foo = xxx - FAIL (Cella 6,7,8 - cioè indice tra 6 e 9)
Corrispondenza non riuscita.
Passaggio 6:.
*? = xxx - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella da 4 a 6.)
foo = xxx - FAIL (Cella 7,8,9 - cioè indice tra 7 e 10)
Corrispondenza non riuscita.
Passaggio 7:.
*? = xxxx - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella da 4 a 7.)
foo = xxf - FAIL (Cella 8,9,10 - cioè indice tra 8 e 11)
Corrispondenza non riuscita.
Passaggio 8:.
*? = xxxxx - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella da 4 a 8.)
foo = xfo - FAIL (Cella 9,10,11 - cioè indice tra 9 e 12)
Corrispondenza non riuscita.
Passaggio 9:.
*? = xxxxxx - PASS (Aggiungi caratteri al quantificatore riluttante '. *?'. Cella da 4 a 9.)
foo = foo - PASS (Cella 10,11,12 - cioè indice tra 10 e 13)
Report MATCH
Passaggio 10:.
*? = '' (Vuoto) - PASS (partita il meno possibile al quantificatore riluttante '*' indice 13 è vuota.?..)
Foo = Nessun personaggio ha lasciato per abbinare - FAIL (Non v'è nulla dopo indice 13 per abbinare)
Partita fallito.
Risultato: 2 corrispondenze
Ho trovato il testo "xfoo" che inizia con l'indice 0 e termina con l'indice 4.
Ho trovato il testo "xxxxxxfoo" che inizia con l'indice 4 e termina con l'indice 13.
Possessivo: abbina il più possibile al quantificatore possessivo e abbina l'intera regex. NON tornare indietro.
Stringa di input: xfooxxxxxxfoo
Regex:. * + Foo
L'espressione regolare precedente ha due parti: '. * +' E 'foo'.
Passaggio 1:.
* + = Xfooxxxxxxfoo - PASS (Corrisponde il più possibile al quantificatore possessivo '. *')
Foo = Nessun carattere da corrispondere - FAIL (Niente da corrispondere dopo l'indice 13)
Corrispondenza non riuscita.
Nota: il backtracking non è consentito.
Risultato: 0 corrispondenze
Avido: "abbina la sequenza di caratteri più lunga possibile"
Riluttante: "trova la sequenza di caratteri più breve possibile"
Possessivo: questo è un po 'strano in quanto NON (al contrario di avido e riluttante) cerca di trovare una corrispondenza per l'intera regex.
A proposito: nessuna implementazione del pattern matcher regex utilizzerà mai il backtracking. Tutti i pattern matcher nella vita reale sono estremamente veloci, quasi indipendenti dalla complessità dell'espressione regolare!
Greedy Quantification implica la corrispondenza di modelli utilizzando tutti i caratteri non convalidati rimanenti di una stringa durante un'iterazione. I caratteri non convalidati iniziano nella sequenza attiva . Ogni volta che non si verifica una corrispondenza, il personaggio alla fine viene messo in quarantena e il controllo viene eseguito nuovamente.
Quando solo le condizioni iniziali del pattern regex sono soddisfatte dalla sequenza attiva, viene effettuato un tentativo di convalidare le condizioni rimanenti rispetto alla quarantena. Se la convalida ha esito positivo, i caratteri corrispondenti nella quarantena vengono convalidati ei caratteri non corrispondenti residui rimangono non convalidati e verranno utilizzati quando il processo ricomincia da capo nell'iterazione successiva.
Il flusso di caratteri va dalla sequenza attiva alla quarantena. Il comportamento risultante è che la maggior parte possibile della sequenza originale viene inclusa in una corrispondenza.
La quantificazione riluttante è per lo più la stessa della qualificazione avida, tranne per il fatto che il flusso di personaggi è l'opposto, cioè iniziano in quarantena e fluiscono nella sequenza attiva . Il comportamento risultante è che in una corrispondenza viene inclusa la minima parte possibile della sequenza originale.
La quantificazione possessiva non ha una quarantena e include tutto in una sequenza attiva fissa .