Testo di corrispondenza tra delimitatori: espressione regolare avida o pigra?

Question

Per il problema comune di testo corrispondente tra delimitatori (ad esempio < e >), ci sono due modelli comuni:

• utilizzando la avido * o + quantificatore in forma START [^END]* END, ad esempio <[^>]*> o
• utilizzando il pigro *? o +? quantificatore nel formato START .*? END, ad es. <.*?>.

C'è una ragione particolare per favorire l'uno rispetto all'altro?

Answer 1

Alcuni vantaggi:

[^>]*:

• più espressivo.
• Cattura newlines indipendentemente dal flag /s.
• Considerato più veloce, perché il motore non deve tornare indietro per trovare una corrispondenza riuscita (con il [^>] il motore non effettua le scelte - gli diamo solo un modo per abbinare il modello alla stringa).

.*?

• No "duplicazione del codice" - il carattere di fine appare solo una volta.
• Più semplice nei casi in cui il delimitatore di fine è più lungo di un carattere. (una classe di caratteri non funzionerebbe in questo caso) Un'alternativa comune è (?:(?!END).)*. Questo è ancora peggio se il delimitatore END è un altro modello.

Answer 2

Il primo è più esplicito, i. e. esclude definitivamente il delimitatore di chiusura dall'essere parte del testo abbinato. Questo non è garantito nel secondo caso (se l'espressione regolare è estesa per corrispondere più di questo tag).

Esempio: Se si tenta di abbinare <tag1><tag2>Hello! con <.*?>Hello!, l'espressione regolare corrisponderà

<tag1><tag2>Hello! 

mentre <[^>]*>Hello! corrisponderà

<tag2>Hello! 

Answer 3

Ciò che la maggior parte delle persone non riescono a prendere in considerazione quando si avvicina domande come questo è ciò che succede quando la regex non è in grado di trovare una corrispondenza. Questo è quando è probabile che le buche per le prestazioni dell'assassino siano visualizzate. Ad esempio, prendi l'esempio di Tim, dove stai cercando qualcosa come <tag>Hello!. Considerate ciò che accade con:

<.*?>Hello! 

Il motore regex trova una < e trova rapidamente una chiusura >, ma non >Hello!. Quindi lo .*? continua a cercare > che è seguito da Hello!.Se non ce n'è uno, andrà fino alla fine del documento prima che si arrenda. Quindi il motore regex riprende la scansione finché non trova un altro < e ci riprova. sappiamo già come andrà a finire, ma il motore regex, in genere, non lo fa; passa attraverso lo stesso rigamarole con ogni < nel documento. Consideriamo ora l'altra espressione regolare:

<[^>]*>Hello! 

Come prima, corrisponde rapidamente dal < al >, ma non riesce a corrispondere Hello!. Tornerà indietro allo <, quindi uscirà e inizierà la scansione per un altro <. Controllerà comunque ogni < come la prima espressione regolare, ma non cercherà fino alla fine del documento ogni volta che ne trova una.

Ma è anche peggio di così. Se ci pensi, lo .*? equivale effettivamente a un lookahead negativo. Sta dicendo "Prima di consumare il prossimo personaggio, assicurati che il resto della regex non possa corrispondere in questa posizione." In altre parole,

/<.*?>Hello!/ 

... è equivalente a:

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/ 

Così in ogni posizione che si sta eseguendo, non solo un normale tentativo partita, ma un lookahead molto più costoso. (È ad almeno due volte più costosa, perché il lookahead deve esaminare almeno un carattere, quindi il . va avanti e consuma un carattere.)

((*FAIL) è uno dei backtracking-control verbs (supportati anche in PHP). |\z(*FAIL) mezzi di Perl "o raggiungere la fine del documento e rinunciare".)

Infine, c'è un altro vantaggio dell'approccio di classe carattere negato. Anche se non lo fa (come @Bart sottolineato) agire come il quantificatore è possessivo, non c'è nulla che impedisca di fare è possessiva, se il sapore lo supporta:

/<[^>]*+>Hello!/ 

... o avvolgerlo in un gruppo atomica:

/(?><[^>]*>)Hello!/ 

non solo queste espressioni regolari mai marcia indietro inutilmente, non hanno per salvare le informazioni sullo stato che rende backtracking possibile.