Perché i motori regex consentono/tentano automaticamente la corrispondenza alla fine della stringa di input?




system text regularexpressions regex replace (5)

Nota:
* Python è usato per illustrare i comportamenti, ma questa domanda è indipendente dalla lingua.
* Ai fini di questa discussione, supponiamo solo l' input su una sola riga , perché la presenza di newline (input multi-line) introduce variazioni nel comportamento di $ e . che sono accessori alle domande a portata di mano.

La maggior parte dei motori regex:

  • accetta una regex che tenta esplicitamente di abbinare un'espressione dopo la fine della stringa di input [1] .

    $ python -c "import re; print(re.findall('$.*', 'a'))"
    [''] # !! Matched the hypothetical empty string after the end of 'a'
  • quando si cerca / sostituisce globalmente , cioè, quando si cercano tutte le corrispondenze non sovrapposte di una determinata espressione regolare e si è raggiunta la fine della stringa , cercare in modo imprevisto di corrispondere di nuovo [2] , come spiegato in questa risposta a una domanda correlata :

    $ python -c "import re; print(re.findall('.*$', 'a'))"
    ['a', ''] # !! Matched both the full input AND the hypothetical empty string

Forse inutile dire che tali tentativi di corrispondenza hanno successo solo se la regex in questione corrisponde alla stringa vuota (e la regex di default / è configurata per riportare corrispondenze a lunghezza zero).

Questi comportamenti sono almeno a prima vista contro-intuitivi , e mi chiedo se qualcuno può fornire un motivo razionale per loro, non ultimo perché:

  • non è ovvio quale sia il vantaggio di questo comportamento.
  • al contrario, nel contesto di trovare / sostituire globalmente con modelli come .* e .*$ , il comportamento è decisamente sorprendente. [3]
    • Per porre la domanda in modo più esplicito: perché la funzionalità progettata per trovare corrispondenze multiple e non sovrapposte di una regex, ad esempio corrispondenza globale , decide di tentare un'altra corrispondenza se sa che l'intero input è già stato consumato , indipendentemente da quale regex è (anche se non vedrai mai il sintomo con un'espressione regolare che almeno non corrisponde anche alla stringa vuota)
    • I seguenti linguaggi / motori mostrano il comportamento sorprendente: .NET, Python (sia 2.x che 3.x) [2] , Perl (entrambi 5.xe 6.x), Ruby, Node.js (JavaScript)

Si noti che i motori regex variano nel comportamento rispetto a dove continuare la corrispondenza dopo una corrispondenza di lunghezza zero (stringa vuota).

Ciascuna scelta (inizia con la stessa posizione del personaggio rispetto alla partenza successiva) è difendibile - vedi il capitolo sulle partite a lunghezza zero su www.regular-expressions.info .

Al contrario, il caso .*$ Discusso qui è diverso in quanto, con qualsiasi input non vuoto, la prima corrispondenza per .*$ Non è una corrispondenza di lunghezza zero, quindi la differenza di comportamento non si applica - invece, la posizione del carattere dovrebbe avanzare incondizionatamente dopo la prima partita, che ovviamente è impossibile se sei già alla fine.
Ancora una volta, la mia sorpresa sta nel fatto che un altro match è tentato nondimeno, anche se per definizione non è rimasto nulla.

[1] Sto usando $ come marker di fine ingresso qui, anche se in alcuni motori, come .NET, può segnare la fine della fine dell'input opzionalmente seguito da una nuova riga finale . Tuttavia, il comportamento si applica ugualmente quando si utilizza il marcatore di fine ingresso non condizionale, \z .

[2] Python 2.xe 3.x fino a 3.6.x comportamento di sostituzione apparentemente speciale in questo contesto: python -c "import re; print(re.sub('.*$', '[\g<0>]', 'a'))" utilizzato per produrre solo [a] - cioè, è stata trovata e sostituita una sola corrispondenza.
Dal momento che Python 3.7, il comportamento è ora come nella maggior parte dei motori regex, in cui vengono eseguite due sostituzioni, producendo [a][] .

[3] Puoi evitare il problema (a) scegliendo un metodo di sostituzione che è progettato per trovare al massimo una corrispondenza o (b) usa ^.* Per impedire che vengano trovate corrispondenze multiple tramite l'ancoraggio di inizio dell'entrata.
(a) potrebbe non essere un'opzione, a seconda di come una determinata lingua supera la funzionalità; per esempio, l'operatore di sostituzione di PowerShell sostituisce invariabilmente tutte le occorrenze; considera il seguente tentativo di racchiudere tutti gli elementi dell'array in "..." :
'a', 'b' -replace '.*', '"$&"' . A causa della corrispondenza due volte , questo produce gli elementi "a""" e "b""" ;
l'opzione (b), 'a', 'b' -replace '^.*', '"$&"' , risolve il problema.


Nota:
* Il mio post di domande contiene due domande correlate, ma distinte , per le quali avrei dovuto creare post separati, come ora realizzo.
* Le altre risposte qui si concentrano su una delle domande ciascuna, quindi in parte questa risposta fornisce una road map a quali risposte rispondono a quale domanda .

Per quanto riguarda il motivo per cui pattern come $<expr> sono consentiti / quando hanno senso:

  • la risposta di Dawg sostiene che combinazioni prive di senso come $.+ probabilmente non sono prevenute per ragioni pragmatiche ; escluderli potrebbe non valerne la pena.

  • La risposta di Tim mostra come certe espressioni possono avere senso dopo $ , vale a dire affermazioni negative .

  • La seconda metà della risposta alla risposta di ivan_pozdeev sintetizza in modo convincente le risposte di Dawg e Tim.

Per quanto riguarda il motivo per cui la corrispondenza globale trova due corrispondenze per modelli come .* E. .*$ :

  • La risposta di revo contiene grandi informazioni di base sulla corrispondenza a lunghezza zero (stringa vuota), che è alla fine il problema.

Consentitemi di integrare la sua risposta collegandola più direttamente a come il comportamento contraddice le mie aspettative nel contesto della corrispondenza globale :

  • Da una prospettiva puramente di buon senso , è ovvio che una volta che l'input è stato completamente consumato durante l'abbinamento, non è rimasto per definizione nulla , quindi non c'è motivo di cercare ulteriori corrispondenze.

  • Al contrario, la maggior parte dei motori regex considera la posizione del carattere dopo l'ultimo carattere della stringa di input - la posizione nota come fine della stringa del soggetto in alcuni motori - una posizione di partenza valida per una corrispondenza e quindi ne tenta un'altra .

    • Se la regex a portata di mano corrisponde alla stringa vuota (produce una corrispondenza di lunghezza zero, ad esempio espressioni regolari come .* O a? ), Corrisponde a quella posizione e restituisce una corrispondenza stringa vuota.

    • Viceversa, non vedrai una corrispondenza aggiuntiva se la regex non corrisponde (anche) alla stringa vuota - mentre la corrispondenza aggiuntiva è ancora tentata in tutti i casi, in questo caso non verrà trovata alcuna corrispondenza, dato che la stringa vuota è l'unica corrispondenza possibile alla fine della stringa di soggetto.

Sebbene ciò fornisca una spiegazione tecnica del comportamento, non ci dice ancora perché è stato implementato l'abbinamento dopo l'ultimo carattere.

La cosa più vicina che abbiamo è un'ipotesi plausibile di Wiktor Stribiżew in un commento (enfasi aggiunta), che suggerisce ancora una ragione pragmatica per il comportamento:

... come quando si ottiene una corrispondenza di stringa vuota, è possibile che si corrisponda ancora al char successivo che si trova ancora nello stesso indice nella stringa. Se un motore regex non lo supporta, queste corrispondenze verranno saltate. Fare un'eccezione per la fine della stringa non era probabilmente così importante per gli autori di espressioni regolari del motore .

La prima metà della risposta di ivan_pozdeev spiega il comportamento in termini più tecnici dicendoci che il vuoto alla fine della stringa [input] è una posizione valida per la corrispondenza, proprio come qualsiasi altra posizione di confine di carattere .
Tuttavia, pur trattando tutte queste posizioni lo stesso è sicuramente coerente internamente e presumibilmente semplifica l' implementazione , il comportamento sfugge comunque al buon senso e non ha vantaggi evidenti per l' utente .

Ulteriori osservazioni re matching stringa vuota:

Nota: in tutti i frammenti di codice riportati di seguito, viene eseguita la sostituzione globale delle stringhe per evidenziare le corrispondenze risultanti: ogni corrispondenza è racchiusa tra [...] , mentre le parti non corrispondenti dell'ingresso vengono passate così come sono.

Si noti, tuttavia, che la corrispondenza alla fine della posizione della stringa di soggetto non è limitata a quei motori in cui la corrispondenza continua nella stessa posizione di carattere dopo una corrispondenza vuota .

Ad esempio, il motore regex .NET non lo fa (esempio PowerShell):

PS> 'a1' -replace '\d*|a', '[$&]'
[]a[1][]

Questo è:

  • \d* corrisponde alla stringa vuota prima di a
  • a se stesso non corrisponde, il che implica che la posizione del personaggio è stata avanzata dopo la partita vuota.
  • 1 stato abbinato da \d*
  • La posizione di fine stringa dell'oggetto è stata nuovamente abbinata a \d* , risultando in un'altra corrispondenza a stringa vuota.

Perl 5 è un esempio di motore che riprende la corrispondenza nella stessa posizione di carattere:

$ "a1" | perl -ple "s/\d*|a/[$&]/g"
[][a][1][]

Nota anche come è stato abbinato.

È interessante notare che Perl 6 non solo si comporta in modo diverso, ma esibisce ancora un'altra variante di comportamento:

$ "a1" | perl6 -pe "s:g/\d*|a/[$/]/"
[a][1][]

Apparentemente, se un'alternanza trova sia una corrispondenza vuota che una non vuota, viene riportata solo la parte non vuota - vedi il commento di revo sotto.


Ricorda diverse cose:

  1. ^ e $ sono asserzioni di larghezza zero - corrispondono a destra dopo l'inizio logico della stringa (o dopo ogni riga che termina in modalità multilinea con il flag m nella maggior parte delle implementazioni di espressioni regolari) o alla fine logica della stringa (o alla fine della riga PRIMA del carattere o caratteri di fine riga in modalità multilinea).

  2. .* è potenzialmente una corrispondenza di lunghezza zero di nessuna corrispondenza. La versione di sola lunghezza zero sarebbe $(?:end of line){0} DEMO (che è utile come commento suppongo ...)

  3. . non corrisponde \n (a meno che non si abbia il flag s ) ma combacia con \r nelle terminazioni di riga CRLF di Windows. Quindi $.{1} corrisponde solo alle terminazioni di riga di Windows, ad esempio (ma non farlo. Utilizza invece il letterale \r\n ).

Non vi è alcun vantaggio particolare oltre ai semplici casi di effetti collaterali.

  1. L'espressione regolare $ è utile;
  2. .* è utile.
  3. Le regex ^(?a lookahead) e (?a lookbehind)$ sono comuni e utili.
  4. La regex (?a lookaround)^ o $(?a lookaround) sono potenzialmente utili.
  5. L'espressione regolare $.* Non è utile e abbastanza rara da non giustificare l'implementazione dell'ottimizzazione per far sì che il motore smetta di guardare con quel caso limite. La maggior parte dei motori regex fa un buon lavoro di analisi della sintassi; un parentesi graffa mancante o una parentesi per esempio. Per fare in modo che il motore analizzi $.* Come non utile richiederebbe un significato di parsing di quell'espressione regolare diversa da $(something else)
  6. Ciò che otterrai sarà altamente dipendente dal sapore regex e dallo stato dei flag s e m .

Per esempi di sostituzioni, prendere in considerazione il seguente output di script Bash da alcuni principali sapori regex:

#!/bin/bash

echo "perl"
printf  "123\r\n" | perl -lnE 'say if s/$.*/X/mg' | od -c
echo "sed"
printf  "123\r\n" | sed -E 's/$.*/X/g' | od -c
echo "python"
printf  "123\r\n" | python -c "import re, sys; print re.sub(r'$.*', 'X', sys.stdin.read(),flags=re.M) " | od -c
echo "awk"
printf  "123\r\n" | awk '{gsub(/$.*/,"X")};1' | od -c
echo "ruby"
printf  "123\r\n" | ruby -lne 's=$_.gsub(/$.*/,"X"); print s' | od -c

stampe:

perl
0000000    X   X   2   X   3   X  \r   X  \n                            
0000011
sed
0000000    1   2   3  \r   X  \n              
0000006
python
0000000    1   2   3  \r   X  \n   X  \n                                
0000010
awk
0000000    1   2   3  \r   X  \n                                        
0000006
ruby
0000000    1   2   3   X  \n                                            
0000005

Qual è la ragione dell'uso di .* Con il modificatore globale attivo? Poiché qualcuno in qualche modo si aspetta che una stringa vuota venga restituita come corrispondenza o che non sia a conoscenza del quantificatore * , altrimenti non dovrebbe essere impostato il modificatore globale. .* senza g non restituisce due corrispondenze.

non è ovvio quale sia il vantaggio di questo comportamento.

Non dovrebbe esserci un beneficio. In realtà stai mettendo in discussione l'esistenza di corrispondenze a lunghezza zero. Ti stai chiedendo perché esiste una stringa di lunghezza zero?

Abbiamo tre posizioni valide in cui esiste una stringa di lunghezza zero:

  • Inizio della stringa dell'oggetto
  • Tra due personaggi
  • Fine della stringa dell'oggetto

Dovremmo cercare il motivo piuttosto che il beneficio di quel secondo risultato della corrispondenza di lunghezza zero usando .* Con g modificatore (o una funzione che cerca tutte le occorrenze). Quella posizione di lunghezza zero che segue una stringa di input ha alcuni usi logici. Sotto il diagramma di stato viene afferrato da debuggex rispetto a .* Ma ho aggiunto epsilon sulla transizione diretta dallo stato di avvio allo stato di accettazione per dimostrare una definizione:

Questa è una corrispondenza di lunghezza zero (leggi di più sulla transizione epsilon ).

Tutto ciò riguarda l'avidità e la non avidità. Senza posizioni di lunghezza zero una regex come .?? non avrebbe un significato Non tenta prima il punto, lo salta. Corrisponde a una stringa di lunghezza zero per questo scopo per il transito dello stato corrente in uno stato temporaneo accettabile.

Senza una posizione di lunghezza zero .?? non è mai possibile saltare un carattere nella stringa di input e questo si traduce in un sapore completamente nuovo.

La definizione di avidità / pigrizia conduce a corrispondenze di lunghezza zero.


"Vuoto alla fine della stringa" è una posizione separata per i motori regex perché un motore regex gestisce le posizioni tra i caratteri di input:

|a|b|c|   <- input line

^ ^ ^ ^
positions at which a regex engine can "currently be"

Tutte le altre posizioni possono essere descritte come "prima dell'ennesimo carattere" ma per la fine, non c'è nessun personaggio a cui fare riferimento.

Come per le corrispondenze Regex di lunghezza zero - Regular-expressions.info , è anche necessario supportare le corrispondenze di lunghezza zero (che non supportano tutte le funzioni di regex):

  • Ad esempio una regex \d* su stringa abc corrisponderebbe 4 volte: prima di ogni lettera e alla fine.

$ è consentito in qualsiasi punto della regex per uniformità: è trattato allo stesso modo di qualsiasi altro token e corrisponde a quella magica posizione "fine della stringa". Rendere "finalizzato" il lavoro regex porterebbe a un'inutile incoerenza nel lavoro del motore e impedire ad altre cose utili che possono combaciare lì, come ad esempio lookbehind o \b (in pratica, tutto ciò che può essere una corrispondenza di lunghezza zero) - vale a dire essere sia una complicazione progettuale che una limitazione funzionale senza alcun beneficio.

Infine, per rispondere al motivo per cui un motore regex può o meno provare ad abbinare "di nuovo" nella stessa posizione, facciamo riferimento a Avanzamento dopo un match Regex a lunghezza zero - Corrispondenze Regex a lunghezza zero - Regular-expressions.info :

Diciamo che abbiamo regex \d*|x , la stringa soggetto x1

La prima corrispondenza è una corrispondenza vuota all'inizio della stringa. Ora, come possiamo dare ad altri gettoni una possibilità senza rimanere bloccati in un ciclo infinito?

La soluzione più semplice, che viene utilizzata dalla maggior parte dei motori regex, è quella di iniziare il successivo tentativo di corrispondenza di un carattere dopo la fine della partita precedente

Ciò potrebbe dare risultati poco intuitivi - ad esempio, la regex precedente corrisponderà '' all'inizio, 1 e '' alla fine - ma non x .

L'altra soluzione, che è usata da Perl, è quella di iniziare sempre il successivo tentativo di corrispondenza alla fine della partita precedente, indipendentemente dal fatto che fosse a lunghezza zero o meno. Se era a lunghezza zero, il motore ne prende nota, poiché non deve consentire una corrispondenza a lunghezza zero nella stessa posizione.

Quale "salta" corrisponde meno al costo di qualche complessità in più. Ad esempio, la regex precedente produrrà '' , x , 1 e '' alla fine.

L'articolo continua a dimostrare che non ci sono buone pratiche consolidate qui e vari motori regex stanno attivamente provando nuovi approcci per provare a produrre risultati più "naturali":

Un'eccezione è il motore JGsoft. Il motore JGsoft fa avanzare un personaggio dopo una corrispondenza di lunghezza zero, come fa la maggior parte dei motori. Ma ha una regola in più per saltare le partite a lunghezza zero nella posizione in cui è terminata la partita precedente, quindi non puoi mai avere una corrispondenza di lunghezza zero immediatamente adiacente a una corrispondenza di lunghezza non pari a zero. Nel nostro esempio il motore JGsoft trova solo due corrispondenze: la corrispondenza di lunghezza zero all'inizio della stringa e 1.

Python 3.6 e anticipo precedente dopo le partite di lunghezza zero. La funzione gsub () per cercare e sostituire sostituisce le corrispondenze di lunghezza zero nella posizione in cui è terminata la precedente corrispondenza di lunghezza non pari a zero, ma la funzione finditer () restituisce tali corrispondenze. Quindi una ricerca e sostituzione in Python fornisce gli stessi risultati delle applicazioni Just Great Software, ma elencando tutte le corrispondenze aggiunge la corrispondenza di lunghezza zero alla fine della stringa.

Python 3.7 ha cambiato tutto questo. Gestisce corrispondenze di lunghezza zero come Perl. gsub () ora sostituisce le corrispondenze di lunghezza zero adiacenti a un'altra corrispondenza. Ciò significa che le espressioni regolari che possono trovare corrispondenze di lunghezza zero non sono compatibili tra Python 3.7 e versioni precedenti di Python.

PCRE 8.00 e versioni successive e PCRE2 gestiscono corrispondenze di lunghezza zero come Perl mediante backtracking. Non avanzano più un personaggio dopo che una combinazione di lunghezza zero come PCRE 7.9 è stata utilizzata.

Le funzioni regexp in R e PHP sono basate su PCRE, quindi evitano di rimanere bloccate su una corrispondenza di lunghezza zero eseguendo il backtracking come fa PCRE. Ma la funzione gsub () per cercare e sostituire in R salta anche le corrispondenze di lunghezza zero nella posizione in cui è terminata la precedente corrispondenza di lunghezza diversa da zero, come gsub () in Python 3.6 e versioni precedenti. Le altre funzioni regexp in R e tutte le funzioni in PHP consentono corrispondenze di lunghezza zero immediatamente adiacenti a corrispondenze di lunghezza diversa da zero, proprio come PCRE stesso.


Non so da dove viene la confusione.
I motori Regex sono fondamentalmente stupidi .
Sono come Mikey, mangeranno qualsiasi cosa.

$ python -c "import re; print(re.findall('$.*', 'a'))"
[''] # !! Matched the hypothetical empty string after the end of 'a'

Puoi mettere un migliaio di espressioni opzionali dopo $ e continuerà a corrispondere al
EOS. I motori sono stupidi.

$ python -c "import re; print(re.findall('.*$', 'a'))"
['a', ''] # !! Matched both the full input AND the hypothetical empty string

Pensaci in questo modo, ci sono due espressioni indipendenti qui
.* | $ Il motivo è che la prima espressione è facoltativa.
Capita semplicemente di cazzeggiare contro l'affermazione EOS.
In questo modo ottieni 2 corrispondenze su una stringa non vuota.

Perché la funzionalità progettata per trovare corrispondenze multiple e non sovrapposte di un'espressione regolare, ad esempio corrispondenza globale, decide di tentare anche un'altra corrispondenza se sa che l'intero input è già stato consumato,

Le classi di cose chiamate asserzioni non esistono nelle posizioni dei personaggi.
Esistono solo TRA posizioni di carattere.
Se sono presenti nella regex, non si sa se l'intero input è stato consumato.
Se possono essere soddisfatti come un passo indipendente, ma solo una volta, corrisponderanno
indipendentemente.

Ricorda, regex è una proposizione da left-to-right .
Ricorda anche che i motori sono stupidi .
Questo è di design.
Ogni costrutto è uno stato nel motore, è come una pipeline.
L'aggiunta di complessità lo condannerà sicuramente al fallimento.

Per inciso, fa .*a realtà inizia dall'inizio e controlla ogni personaggio?
No .* Inizia immediatamente alla fine della stringa (o linea, a seconda) e inizia
backtracking.

Un'altra cosa divertente. Vedo un sacco di novizi usando .*? alla fine del loro
regex, pensando che otterrà tutto il rimanente kruft dalla stringa.
È inutile, non abbinerà mai nulla.
Anche uno standalone .*? regex corrisponderà sempre a nessun numero di caratteri
ci sono nella stringa.

In bocca al lupo! Non preoccuparti, i motori regex sono solo ... beh, stupidi .





language-agnostic