Quantificatori avidi vs. riluttanti o possessivi

Ho trovato questo eccellente tutorial sulle espressioni regolari e mentre capisco intuitivamente cosa fanno i quantificatori “avidi”, “riluttanti” e “possessivi”, sembra esserci un serio buco nella mia comprensione.

Nello specifico, nell’esempio seguente:

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 sono state consumate , il matcher si è staccato , l’occorrenza più a destra di “foo” è stata rigurgitata , ecc.

Sfortunatamente, nonostante le belle metafore, continuo a non capire cosa viene mangiato da chi … Conoscete un altro tutorial che spiega (in modo conciso) come funzionano le espressioni regolari dei motori?

In alternativa, se qualcuno può spiegare in un fraseggio un po ‘diverso il seguente paragrafo, sarebbe molto apprezzato:

    Il primo esempio usa il quantificatore greedy * per trovare “qualsiasi cosa”, zero o più volte, seguito dalle lettere “f” “o” “o”. Poiché il quantificatore è avido, la porzione. * Dell’espressione mangia prima l’intera stringa di input. A questo punto, l’espressione generale non può avere successo, perché le ultime tre lettere (“f” “o” “o”) sono già state consumate ( da chi? ). Quindi l’accompagnatore si allontana lentamente ( da destra a sinistra? ) Una lettera alla volta fino a quando l’occorrenza più giusta di “pippo” è stata rigurgitata ( cosa significa? ), A quel punto la partita ha successo e la ricerca finisce.

    Il secondo esempio, tuttavia, è riluttante, quindi inizia col consumare ( da chi? ) “Niente”. Perché “foo” non appare all’inizio della stringa, è costretto a deglutire ( chi ingoia?) La prima lettera (una “x”), che triggers la prima corrispondenza a 0 e 4. La nostra imbracatura di test continua il processo fino a quando la stringa di input non è 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. * +, ( How? ) Senza lasciare nulla per soddisfare il “foo” alla fine dell’espressione. Utilizzare un quantificatore possessivo per le situazioni in cui si desidera cogliere tutto senza mai arretrare ( cosa significa back off? ); supererà il quantificatore avido equivalente nei casi in cui la partita non viene trovata immediatamente.

    Darò un colpo.

    Un quantificatore goloso prima corrisponde il più ansible. Quindi .* Corrisponde all’intera stringa. Quindi il matcher cerca di far corrispondere il f seguente, ma non ci sono caratteri rimasti. Quindi “backtracks”, rendendo il quantificatore avido abbinare una cosa in meno (lasciando la “o” alla fine della stringa ineguagliata). Ciò non corrisponde ancora alla f nella regex, quindi “backtracks” ancora una volta, rendendo il quantificatore avido abbinato di nuovo a una cosa in meno (lasciando la “oo” alla fine della stringa ineguagliata). Ciò non corrisponde ancora alla f nella regex, quindi retrocede di un altro passo (lasciando il “foo” alla fine della stringa ineguagliata). Ora, il matcher corrisponde alla f nella regex e anche la o e la successiva o sono uguali. Successo!

    Un quantificatore riluttante o “non-goloso” si confronta per prima il meno ansible. Quindi il .* corrisponde a nulla all’inizio, lasciando l’intera stringa ineguagliata. Quindi il matcher cerca di far corrispondere il f seguente, ma la porzione non corrispondente della stringa inizia con “x” in modo che non funzioni. Quindi il matcher fa il backtrack, rendendo il quantificatore non-avido che combacia con un’altra cosa (ora corrisponde alla “x”, lasciando “fooxxxxxxfoo” ineguagliata). Quindi cerca di far corrispondere il f , che ha successo, e anche il o il prossimo o nella regex match. Successo!

    Nell’esempio, avvia quindi il processo con la porzione non corrispondente rimanente della stringa, seguendo lo stesso processo.

    Un quantificatore possessivo è proprio come il quantificatore avido, ma non fa marcia indietro. Quindi inizia con .* Corrispondente all’intera stringa, senza nulla di ineguagliato. Quindi non rimane nulla che possa corrispondere alla f nella regex. Poiché il quantificatore possessivo non fa marcia indietro, la partita fallisce lì.

    È solo la mia pratica di output per visualizzare la scena-

    Immagine visiva

    Non ho mai sentito i termini esatti “rigurgitare” o “fare marcia indietro” prima; la frase che sostituirà questi è “backtracking”, ma “rigurgitare” sembra una frase buona come qualsiasi “per il contenuto che era stato provvisoriamente accettato prima che il backtracking lo buttasse via di nuovo”.

    La cosa importante da comprendere sulla maggior parte dei motori regex è che stanno facendo il backtracking : accetteranno provvisoriamente una potenziale corrispondenza parziale, mentre cercano di far corrispondere l’intero contenuto della regex. Se la regex non può essere completamente abbinata al primo tentativo, il motore regex tornerà indietro su una delle sue corrispondenze. Proverà ad abbinare * , + ? , alternanza o {n,m} ripetizione in modo diverso, e riprovare. (E sì, questo processo può richiedere molto tempo.)

    Il primo esempio usa il quantificatore greedy * per trovare “qualsiasi cosa”, zero o più volte, seguito dalle lettere “f” “o” “o”. Poiché il quantificatore è avido, la porzione. * Dell’espressione mangia prima l’intera stringa di input. A questo punto, l’espressione generale 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 o erano già state consumate dalla parte iniziale .* Della regola. Tuttavia, l’elemento successivo nella regex, f , non ha lasciato nulla nella stringa di input. Il motore sarà costretto a tornare indietro nella sua partita iniziale .* , E provare ad abbinare l’ultimo ma ultimo carattere. (Potrebbe essere intelligente e tornare indietro a tutti-ma-the-last-three, perché ha tre termini letterali, ma non sono a conoscenza dei dettagli di implementazione a questo livello.)

    Quindi l’accompagnatore si allontana lentamente ( da destra a sinistra? ) Una lettera alla volta fino a quando l’occorrenza più giusta di “pippo” è stata rigurgitata ( cosa significa? ), A cui

    Ciò significa che il foo aveva incluso provvisoriamente la corrispondenza .* . Poiché tale tentativo non è riuscito, il motore regex tenta di accettare un carattere in meno .* . Se in questo esempio ci fosse stata una partita riuscita prima di .* , Il motore probabilmente tenterebbe di accorciare il match .* (Da destra a sinistra, come hai sottolineato, perché è un qualificatore goloso), e se non è stato in grado di eguagliare tutti gli input, quindi potrebbe essere costretto a rivalutare ciò che aveva trovato prima del .* nel mio esempio ipotetico.

    punta la partita ha successo e la ricerca finisce.

    Il secondo esempio, tuttavia, è riluttante, quindi inizia col consumare ( da chi? ) “Niente”. Perché “foo”

    Il nulla iniziale viene consumato da .?* , Che consumerà la quantità più breve ansible di qualsiasi cosa che permetta di far corrispondere il resto della regex.

    non appare all’inizio della stringa, è costretto a deglutire ( chi ingoia?) il

    Di nuovo il .?* Consuma il primo personaggio, dopo aver fatto retrocedere sull’incapacità iniziale di abbinare l’intera regex con la corrispondenza più breve ansible. (In questo caso, il motore regex sta estendendo la corrispondenza per .*? Da sinistra a destra, perché .*? È riluttante.)

    prima lettera (una “x”), che triggers la prima corrispondenza a 0 e 4. Il nostro cablaggio di test 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? )

    A. .*+ Consumerà il più ansible e non tornerà indietro per trovare nuove corrispondenze quando l’espressione regolare nel suo complesso non riesce a trovare una corrispondenza. Poiché la forma possessiva non esegue il backtracking, probabilmente non vedrai molti usi con .*+ , Ma piuttosto con classi di caratteri o restrizioni simili: account: [[:digit:]]*+ phone: [[:digit:]]*+ .

    Questo può velocizzare drasticamente la corrispondenza delle espressioni regolari, perché stai dicendo al motore regex che non dovrebbe mai tornare indietro sulle potenziali corrispondenze se un input non corrisponde. (Se dovessi scrivere a mano tutto il codice corrispondente, 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. Tranne i motori regex sono molto meglio di un singolo carattere di push-back, possono riavvolgere tutto il back-to-zero e riprovare 🙂

    Ma più che i potenziali aumenti di velocità, questo ti consente anche di scrivere espressioni regolari che corrispondono esattamente a ciò che devi soddisfare. Ho difficoltà a venire con un semplice esempio 🙂 ma scrivere un’espressione regolare usando quantificatori possessivi o avidi può darti corrispondenze diverse, e l’una o l’altra potrebbe essere più appropriata.

    lasciando nulla rimasto per soddisfare il “foo” alla fine dell’espressione. Utilizzare un quantificatore possessivo per le situazioni in cui si desidera cogliere tutto senza mai arretrare ( cosa significa back off? ); supererà le prestazioni

    “Backing off” in questo contesto significa “backtracking” – buttare via una partita parziale provvisoria per provare un’altra partita parziale, che può avere o meno successo.

    l’equivalente quantificatore avido 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 tornare su di essa. Potresti voler controllare.

    Se si desidera un livello superiore (spiegazione meno dettagliata), per espressioni regolari semplici come quella che si sta guardando, un motore di espressioni regolari funziona con il backtracking. Essenzialmente, sceglie (“mangia”) una sezione della stringa e tenta di far corrispondere l’espressione regolare a quella sezione. Se corrisponde, ottimo. In caso contrario, il motore altera la sua scelta della sezione della stringa e cerca di far corrispondere la regexp a quella sezione, e così via, fino a quando non viene tentata ogni ansible scelta.

    Questo processo viene utilizzato in modo ricorsivo: nel tentativo di associare una stringa con una determinata espressione regolare, il motore suddividerà l’espressione regolare in pezzi e applicherà l’algoritmo a ciascun pezzo singolarmente.

    La differenza tra quantificatori avidi, riluttanti e possessivi entra quando il motore sta facendo le sue scelte su quale parte della stringa tenta di confrontarsi e su come modificare quella scelta se non funziona la prima volta. Le regole sono le seguenti:

    • Un quantificatore goloso indica al motore di iniziare con l’ intera stringa (o almeno, tutto ciò che non è già stato abbinato alle parti precedenti dell’espressione regolare) e controlla se corrisponde all’espressione regolare. Se è così, ottimo; il motore può continuare con il resto della regexp. Altrimenti, riprova, ma ritagliando un carattere (l’ultimo) dalla sezione della stringa da controllare. Se ciò non funziona, taglia un altro personaggio, ecc. Quindi un quantificatore avido controlla le partite possibili in ordine dal più lungo al più breve.

    • Un quantificatore riluttante dice al motore di iniziare con il pezzo più corto ansible della corda. Se corrisponde, il motore può continuare; in caso contrario, aggiunge un carattere alla sezione della stringa da verificare e lo prova, e così via fino a quando non trova una corrispondenza o l’intera stringa è stata utilizzata. Quindi un quantificatore riluttante controlla le partite possibili nell’ordine dal più breve al più lungo.

    • Un quantificatore possessivo è come un quantificatore avido al primo tentativo: dice al motore di iniziare controllando l’intera stringa. La differenza è che se non funziona, il quantificatore possessivo riferisce che la partita è fallita proprio lì e lì. Il motore non cambia la sezione della stringa che viene esaminata e non effettua ulteriori tentativi.

    Questo è il motivo per cui la corrispondenza del quantificatore possessivo fallisce nel tuo esempio: il .*+ Viene confrontato con l’intera stringa, che corrisponde, ma poi il motore continua a cercare altri caratteri foo dopo quello – ma ovviamente non trova loro, perché sei già alla fine della stringa. Se fosse un quantificatore avido, tornerebbe indietro e proverebbe a far sì che .* Corrisponda solo al penultimo carattere, quindi fino al terzo all’ultimo carattere, quindi fino al quarto all’ultimo carattere, che riesce solo perché poi è rimasto un foo dopo che .* ha “mangiato” la parte precedente della stringa.

    Ecco il mio take usando le posizioni di Cell e Index (vedi lo schema qui per distinguere una cella da un indice).

    Greedy – Abbina il più ansible il quantificatore avido e l’intera regex. Se non c’è corrispondenza, torna indietro sul quantificatore avido.

    Stringa di input: xfooxxxxxxfoo
    Regex:. * Foo

    Il Regex di cui sopra ha due parti:
    (Io e
    (Ii) ‘foo’

    Ciascuna delle fasi seguenti analizzerà le due parti. I commenti aggiuntivi per una corrispondenza a “Pass” o “Fail” sono spiegati all’interno di parentesi graffe.

    Passo 1:
    (i). * = xfooxxxxxxfoo – PASS (‘. *’ è un quantificatore avido e utilizzerà l’intera stringa di input)
    (ii) foo = Nessun personaggio rimasto da abbinare all’indice 13 – FAIL
    Partita fallita

    Passo 2:
    (i). * = xfooxxxxxxfo – PASS (Backtracking su greedy quantifier ‘. *’)
    (ii) foo = o – FAIL
    Partita fallita

    Passaggio 3:
    (i). * = xfooxxxxxxf – PASS (Backtracking su greedy quantifier ‘. *’)
    (ii) foo = oo – FAIL
    Partita fallita

    Passaggio 4:
    (i). * = xfooxxxxxx – PASS (Backtracking su greedy quantifier ‘. *’)
    (ii) foo = foo – PASS
    Segnala MATCH

    Risultato: 1 incontro / i
    Ho trovato il testo “xfooxxxxxxfoo” a partire dall’indice 0 e termina con l’indice 13.

    Riluttante: abbina il meno ansible al quantificatore riluttante e abbina l’intera espressione regolare. se non c’è corrispondenza, aggiungi caratteri al quantificatore riluttante.

    Stringa di input: xfooxxxxxxfoo
    Regex:. *? Foo

    La regex di cui sopra ha due parti:
    (io) ‘.*?’ e
    (ii) “pippo”

    Passo 1:
    . *? = ” (vuoto) – PASS (Abbina il meno ansible al quantificatore riluttante ‘. *?’. L’indice 0 che ha ” è una corrispondenza.)
    foo = xfo – FAIL (cella 0,1,2 – cioè indice tra 0 e 3)
    Partita fallita

    Passo 2:
    . *? = x – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. La cella 0 con ‘x’ è una corrispondenza.)
    foo = foo – PASS
    Segnala MATCH

    Passaggio 3:
    . *? = ” (vuoto) – PASS (Abbina il meno ansible al quantificatore riluttante ‘. *?’. L’indice 4 con ” è 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 ‘. *?’. Cell 4.)
    foo = xxx – FAIL (cella 5,6,7 – cioè indice tra 5 e 8)
    Partita fallita

    Passaggio 5:
    . *? = xx – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. Cell da 4 a 5.)
    foo = xxx – FAIL (Cella 6,7,8 – cioè indice tra 6 e 9)
    Partita fallita

    Passaggio 6:
    . *? = xxx – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. Cell 4 a 6.)
    foo = xxx – FAIL (cella 7,8,9 – cioè indice tra 7 e 10)
    Partita fallita

    Step 7:
    . *? = xxxx – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. Cell 4 a 7).
    foo = xxf – FAIL (cella 8,9,10 – cioè indice tra 8 e 11)
    Partita fallita

    Passaggio 8:
    . *? = xxxxx – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. Cell 4 a 8.)
    foo = xfo – FAIL (cella 9,10,11 – cioè indice tra 9 e 12)
    Partita fallita

    Passaggio 9:
    . *? = xxxxxx – PASS (Aggiungi caratteri al quantificatore riluttante ‘. *?’. Cell da 4 a 9.)
    foo = foo – PASS (Cella 10,11,12 – cioè indice tra 10 e 13)
    Segnala MATCH

    Passaggio 10:
    . *? = ” (vuoto) – PASS (Abbina il meno ansible al quantificatore riluttante ‘. *?’. L’indice 13 è vuoto.)
    foo = Nessun personaggio rimasto da abbinare – FAIL (Non c’è niente dopo che l’indice 13 corrisponda)
    Partita fallita

    Risultato: 2 incontro / i
    Ho trovato il testo “xfoo” a partire dall’indice 0 e termina con l’indice 4.
    Ho trovato il testo “xxxxxxfoo” a partire dall’indice 4 e termina all’indirizzo 13.

    Possessivo: abbina il più ansible al quantificatore possessivo e abbina l’intera espressione regolare. NON tornare indietro.

    Stringa di input: xfooxxxxxxfoo
    Regex:. * + Foo

    La regex di cui sopra ha due parti: ‘. * +’ E ‘foo’.

    Passo 1:
    . * + = xfooxxxxxxfoo – PASS (Abbina il più ansible al quantificatore possessivo ‘. *’)
    foo = Nessun carattere rimasto per corrispondere – FAIL (Nulla da abbinare dopo l’indice 13)
    Partita fallita

    Nota: il backtracking non è permesso.

    Risultato: 0 corrispondenza / i

    Greedy: “corrisponde alla sequenza di caratteri più lunga ansible”

    Riluttante: “corrisponde alla sequenza di personaggi più breve ansible”

    Possessivo: Questo è un po ‘strano in quanto NON (in contrasto con avido e riluttante) tenta di trovare una corrispondenza per l’intera regex.

    A proposito: nessuna implementazione di patterner di espressioni regolari utilizzerà mai il backtracking. Tutti i pattern matcher in real-life sono estremamente veloci, quasi indipendenti dalla complessità dell’espressione regolare!

    La quantificazione greedy prevede la corrispondenza del modello utilizzando tutti i rimanenti caratteri non convalidati di una stringa durante un’iterazione. I caratteri non convalidati iniziano nella sequenza triggers . Ogni volta che non si verifica una corrispondenza, il personaggio alla fine viene messo in quarantena e il controllo viene eseguito di nuovo.

    Quando solo le condizioni principali del modello regex sono soddisfatte dalla sequenza triggers, viene effettuato un tentativo di convalidare le restanti condizioni contro la quarantena. Se questa convalida ha esito positivo, i caratteri corrispondenti in quarantena vengono convalidati e i caratteri non corrispondenti residui rimangono non validati e verranno utilizzati quando il processo inizia nuovamente nella successiva iterazione.

    Il stream di caratteri proviene dalla sequenza triggers nella quarantena. Il comportamento risultante è che gran parte della sequenza originale è inclusa in una partita il più ansible.

    La quantificazione riluttante è per lo più identica alla qualifica golosa, tranne il stream di caratteri è l’opposto – cioè, iniziano nella quarantena e fluiscono nella sequenza triggers . Il comportamento risultante è che, come minimo, la sequenza originale è inclusa in una corrispondenza ansible.

    La quantificazione possessiva non ha una quarantena e include tutto in una sequenza triggers fissa.