Tempered Greedy Token – Cosa c’è di diverso nel posizionare il punto prima del lookahead negativo

<table((?!).)* 

corrisponde a tutti i tag del mio tavolo, tuttavia,

 <table(.(?!))* 

non. Il secondo sembra avere senso se provo a scrivere l’espressione a parole, ma non riesco a dare un senso al primo.

Qualcuno può spiegarmi la differenza?

Come riferimento, ho ricevuto il termine “Tempered Greedy Token” da qui: http://www.rexegg.com/regex-quantifiers.html#tempered_greed

Dato che Google restituisce questa domanda SO in aggiunta ai risultati per il tempered greedy token , mi sento in dovere di fornire una risposta più completa.

Cos’è un token Greedy Tempered?

Il rexegg.com temperato riferimento token avido è abbastanza conciso:

In (?:(?!{END}).)* , Il quantificatore * applica a un punto, ma ora è un punto temperato . Il lookahead negativo (?!{END}) asserisce che ciò che segue la posizione corrente non è la stringa {END} . Pertanto, il punto non può mai corrispondere alla parentesi di apertura di {END} , garantendo che non salteremo oltre il delimitatore {END} .

Cioè: un token goloso temperato è un tipo di class di caratteri negata per una sequenza di caratteri (cfr. Classe di caratteri negata per un singolo carattere ).

NOTA : la differenza tra un token goloso temperato e una class di caratteri negata è che il primo non corrisponde realmente al testo diverso dalla sequenza stessa, ma un singolo carattere che non avvia quella sequenza. Cioè (?:(?!abc|xyz).)+ Non corrisponderà def in defabc , ma corrisponderà a def e bc , perché a inizia la sequenza abc vietata, e bc no.

Esso consiste in:

  • (?:...)* – un gruppo quantificato non catturante (può essere un gruppo di cattura, ma non ha senso catturare ogni singolo carattere) (un * può essere + , dipende dal fatto se una corrispondenza di stringa vuota è previsto)
  • (?!...) – un lookahead negativo che impone effettivamente una restrizione sul valore a destra della posizione corrente
  • . – (o qualsiasi carattere (solitamente singolo)) uno schema di consumo.

Tuttavia, possiamo sempre temperare ulteriormente il token usando alternanze nel lookahead negativo (es. (?!{(?:END|START|MID)}) ) o sostituendo il punto di tutto-matching con una class di caratteri negata (es (?:(?!START|END|MID)[^<>]) quando si cerca di far corrispondere il testo solo all’interno dei tag).

Consumare il posizionamento delle parti

Nota: non si fa menzione di una costruzione in cui una parte che consuma (il punto nel token goloso originale temperato) viene posizionata prima del lookahead. La risposta di Avinash sta spiegando chiaramente quella parte: (.(?!))* prima corrisponde a qualsiasi carattere (ma una nuova riga senza un modificatore DOTALL) e poi controlla se non è seguito con risultando in un errore per abbinare e in

table

. La parte che consuma (il . ) DEVE essere posizionata dopo la tempra in testa .

Quando usare il token goloso temperato?

Rexegg.com dà un’idea:

  • Quando vogliamo abbinare un blocco di testo tra Delimiter 1 e Delimitatore 2 senza Substring 3 tra (es. {START}(?:(?!{(?:MID|RESTART)}).)*?{END}
  • Quando vogliamo abbinare un blocco di testo contenente uno specifico pattern all’interno senza traboccare i blocchi successivi (ad esempio, invece del matching di punti lazy come in
    .*?chair.*?

    , useremmo qualcosa come

    (?:(?!chair|).)*chair(?:(?!
    ).)*

    ).

  • Quando vogliamo abbinare la finestra più corta ansible tra 2 stringhe. La corrispondenza pigra non aiuta quando hai bisogno di ottenere abc 2 xyz da abc 1 abc 2 xyz (vedi abc.*?xyz e abc(?:(?!abc).)*?xyz ).

Problema di prestazioni

Il token greedy temprato consuma risorse poiché viene eseguito un controllo lookahead dopo che ciascun carattere è stato abbinato al pattern di consumo. Srotolare la tecnica del loop può aumentare significativamente le prestazioni dei token golosi temperati.

Diciamo, vogliamo abbinare abc 2 xyz in abc 1 abc 2 xyz 3 xyz . Invece di controllare ogni carattere tra abc e xyz con abc(?:(?!abc|xyz).)*xyz , possiamo saltare tutti i caratteri che non sono a o x con [^ax]* , e quindi abbinare tutti a non sono seguiti con bc (con a(?!bc) ) e tutti x che non sono seguiti con yz (con x(?!yz) ): abc[^ax]*(?:a(?!bc)[^ax]*|x(?!yz)[^ax]*)*xyz .

((?!).)* controlla che quel particolare carattere che deve essere abbinato non debba essere un carattere di partenza nella stringa . Se sì, allora solo corrisponde a quel particolare carattere. * ripete lo stesso zero o più volte.

(.(?!))* corrisponde a qualsiasi carattere solo se non è seguito da , zero o più volte. Quindi questo corrisponderebbe a tutti i caratteri all’interno del tag table excpet l’ultimo carattere, poiché l’ultimo char è seguito da . E il seguente schema asserisce che alla fine della partita deve esserci un tag della tabella di chiusura. Questo fa fallire la partita.

Vedi qui

Un token goloso temperato significa davvero solo:

“match, ma solo fino a un punto”

come si fa:

metti il ​​token che non vuoi abbinare come lookahead negativo (?!notAllowedToMatch) davanti a un punto . (abbina qualsiasi cosa), poi ripeti quella cosa intera con una stella * :

((?!notAllowedToMatch).)*

come funziona:

“guarda e mangia uno” più e più volte, spostando un carattere alla volta da sinistra a destra attraverso la stringa di input, finché non viene vista la sequenza non consentita (o la fine della stringa), a quel punto la corrispondenza si interrompe.

La risposta più dettagliata di Wiktor è carina, ho solo pensato che fosse più semplice una spiegazione più semplice.