Hacker News ha riportato in auge il saggio di Nikita Popov sulle regex, riaprendo una divisione cruciale

Hacker News ha riportato in auge un saggio di Nikita Popov di 14 anni fa, riaprendo un conflitto che le scorciatoie linguistiche della programmazione spesso nascondono. L'articolo sostiene che i moderni motori regex possono riconoscere linguaggi ben oltre le lingue regolari formali. La risposta su Hacker News si è concentrata sul costo di questa capacità aggiuntiva.

Popov pubblicò il saggio il 15 giugno 2012, mentre rispondeva spesso a domande su PHP su Stack Overflow. Il suo bersaglio era un divieto familiare: HTML non può essere gestito con le espressioni regolari perché HTML non è regolare.

Questa regola resta utile, ma Popov ha mostrato perché la sua spiegazione teorica può trarre in inganno. Un pattern PCRE non è limitato all'oggetto matematico chiamato espressione regolare. Ricorsione, riferimenti all'indietro, asserzioni, condizionali e chiamate a subroutine offrono ad alcuni motori una gamma molto più ampia.

Il dibattito riacceso non riguarda quindi il fatto che Popov abbia trovato un pattern ingegnoso. Riguarda ciò che gli sviluppatori intendono per regex, quali garanzie sopravvivono alle scelte implementative e quando il riconoscimento diventa un cattivo sostituto dell'analisi sintattica.

Perché Hacker News ha riportato in auge un dibattito sulle regex del 2012

Il saggio è tornato alla ribalta perché la sua distinzione centrale rimane irrisolta nel vocabolario quotidiano del software.

Il saggio del 2012 di Popov inizia separando due significati che gli sviluppatori combinano abitualmente. Le espressioni regolari formali descrivono linguaggi regolari. I motori regex di produzione spesso implementano operatori aggiuntivi che superano quella classe formale.

Un linguaggio regolare può essere riconosciuto con uno stato finito, ossia il matcher non ha bisogno di uno stack illimitato legato alla profondità dell'input. Esempi comuni includono identificatori, semplici formati numerici, pattern di token fissi e molti filtri di ricerca.

PCRE, abbreviazione di Perl-Compatible Regular Expressions, aggiunge costrutti che modificano questo quadro. Un sottopattern può chiamare sé stesso, consentendo al matcher di seguire strutture annidate. Un riferimento all'indietro può richiedere che il testo successivo sia uguale a quello catturato in precedenza.

Queste funzionalità rendono il termine “espressione regolare” storicamente familiare ma matematicamente impreciso. Gli sviluppatori usano di solito regex come nome collettivo per una famiglia di linguaggi di pattern. Gli specialisti dei linguaggi formali possono riservare il termine alle espressioni equivalenti agli automi finiti.

La distinzione ha guidato la discussione di agosto. Una parte ha sostenuto che il saggio rischia di confondere le vere espressioni regolari con il pattern matching specifico di PCRE. Altri hanno risposto che Popov dichiara esplicitamente questa distinzione prima di esaminare il significato più ampio usato dai programmatori.

Entrambe le letture individuano qualcosa di importante. Il saggio definisce attentamente il proprio ambito, eppure il suo titolo provocatorio invita i lettori a considerare motori diversi come un'unica tecnologia. Un pattern PCRE che usa la ricorsione dice poco agli sviluppatori su ciò che JavaScript, RE2, Rust, POSIX o un'altra implementazione accettano.

La discussione è andata anche oltre la teoria. I commentatori hanno sollevato questioni di leggibilità, differenze tra motori, uso della memoria, backtracking, esposizione ad attacchi denial-of-service ed espressioni generate dall'IA. Queste preoccupazioni spiegano perché un saggio del 2012 sembri ancora attuale.

I moderni assistenti di programmazione possono produrre pattern densi senza garantire che chi li mantiene ne comprenda l'esecuzione. Possono anche suggerire sintassi non supportata dal motore di destinazione. Un maggiore accesso alla generazione di regex non elimina la necessità di scegliere il matcher giusto.

L'articolo originale rimane prezioso perché mette in discussione un limite eccessivamente semplificato. La discussione rinnovata conta perché fornisce la domanda operativa mancante: quanto costa questa espressività aggiuntiva?

La potenza delle regex PCRE deriva da funzionalità esterne ai linguaggi regolari

Il risultato centrale dell'articolo riguarda i motori in stile PCRE, non ogni sistema che porta l'etichetta regex.

Popov inizia con la gerarchia di Chomsky, che raggruppa i linguaggi formali in base alla grammatica necessaria per generarli. I linguaggi regolari rientrano nei linguaggi liberi dal contesto, che a loro volta rientrano nei linguaggi sensibili al contesto.

Le espressioni regolari tradizionali occupano il gruppo più piccolo. Concatenazione, alternanza, classi di caratteri e ripetizione possono descrivere ogni linguaggio regolare. Da sole, non possono ricordare una profondità di annidamento illimitata né duplicare una sottostringa arbitraria catturata.

La ricorsione PCRE modifica il primo limite. Popov usa un gruppo ricorsivo per riconoscere stringhe che contengono uguali quantità di caratteri a seguiti da caratteri b. Quel linguaggio è libero dal contesto ma non regolare.

Il meccanismo è compatto. Un pattern consuma una a, invoca ricorsivamente il gruppo circostante e poi consuma una b. Ogni chiamata più profonda aggiunge una coppia corrispondente attorno alla corrispondenza annidata.

La documentazione attuale di PCRE2 descrive ancora la sintassi dei pattern ricorsivi. Fornisce le parentesi bilanciate come esempio diretto. Un gruppo corrisponde a una parentesi aperta, a caratteri interni ordinari o a un'altra invocazione del gruppo, e a una parentesi chiusa.

Si tratta di una capacità significativa. Il matching tradizionale a stati finiti può supportare solo un limite di annidamento predefinito. Il matching ricorsivo può seguire la profondità di annidamento dell'input, entro i limiti di risorse e il comportamento del motore.

Popov poi mappa le regole di una grammatica libera dal contesto in sottopattern PCRE con nome. Il costrutto (?(DEFINE)...) contiene definizioni senza consumare input. Le chiamate a subroutine con nome consentono a una regola di invocarne un'altra.

Il suo esempio esteso traduce in questa notazione porzioni della grammatica email RFC 5322. Il risultato assomiglia a una grammatica incorporata in un letterale regex, con spaziatura e commenti abilitati tramite la modalità estesa.

Questo sostiene l'affermazione più sorprendente del saggio: la ricorsione in stile PCRE può riconoscere linguaggi liberi dal contesto dopo la trasformazione della ricorsione sinistra incompatibile. Non significa che ogni breve regex possa elaborare ogni linguaggio libero dal contesto.

Non rende neppure il matcher un parser completo. Il riconoscimento risponde alla domanda se un input appartenga a un linguaggio. L'analisi sintattica produce un output strutturato che registra come l'input si inserisce nella grammatica.

Questa differenza diventa decisiva per HTML. Un matcher potrebbe determinare se un frammento ben formato è conforme a una grammatica. Un'applicazione di solito necessita di elementi, attributi, nodi di testo, recupero dagli errori, gestione delle entità e attraversamento del documento.

L'HTML reale aggiunge un'altra complicazione. I browser elaborano documenti malformati mediante un comportamento di recupero specificato. Il matching di un linguaggio idealizzato e ben formato non riproduce quel comportamento.

Popov riconosce entrambi i limiti. Raccomanda una libreria DOM per l'elaborazione generica di HTML e riserva le regex a situazioni circoscritte. La celebre affermazione è quindi più circoscritta di quanto suggeriscano molte rielaborazioni.

I riferimenti all'indietro introducono un ulteriore passo oltre le espressioni regolari classiche. Un riferimento all'indietro corrisponde esattamente al testo precedentemente catturato da un gruppo. Il pattern ^(.+)\1$, per esempio, riconosce una stringa formata da due metà identiche.

Un automa finito non può in generale ricordare una prima metà arbitraria e confrontarla con la seconda. Il motore deve conservare il contenuto catturato ed esplorare i possibili punti di divisione. Questo stato aggiuntivo modifica sia il campo espressivo sia il comportamento computazionale.

Popov combina inoltre ricorsione e asserzioni lookaround per riconoscere almeno alcuni linguaggi sensibili al contesto. Un lookaround controlla il testo circostante senza consumarlo in quella posizione.

Si ferma prima di affermare che PCRE riconosca ogni linguaggio sensibile al contesto. Questa cautela è importante. Il saggio distingue le costruzioni dimostrate dalle questioni senza risposta, pur usando un titolo intenzionalmente ampio.

Le regex formali e i motori di backtracking ottimizzano per promesse diverse

Il conflitto principale non è tra teoria e pratica; è tra esecuzione prevedibile e un linguaggio di pattern più ampio.

Un motore limitato ai costrutti dei linguaggi regolari può eseguire i pattern tramite automi. Tiene traccia dell'insieme di stati raggiungibili dopo ogni carattere di input anziché impegnarsi su un percorso e tornare indietro dopo un fallimento.

Un motore di backtracking segue le alternative più come una ricerca in profondità. Seleziona un ramo, prosegue e torna a una decisione precedente quando la corrispondenza successiva fallisce. Questo approccio supporta catture e comportamenti avanzati con semantiche intuitive.

Può anche ripetere il lavoro. Quantificatori annidati ambigui possono creare molti modi per dividere lo stesso input. Un suffisso quasi corrispondente può costringere il motore a esplorare quelle combinazioni prima di segnalare un fallimento.

Questo rischio non compare solo quando un pattern usa ricorsione o riferimenti all'indietro. Un'implementazione di backtracking può richiedere un tempo eccessivo su un pattern formalmente regolare. Classe sintattica e strategia di esecuzione sono correlate, ma non identiche.

Questo punto ha corretto un'eccessiva semplificazione nel dibattito online. Rimuovere le estensioni non regolari non rende automaticamente lineare ogni implementazione. Il motore deve anche usare un algoritmo che eviti l'esplorazione esponenziale dei percorsi.

Il motore a tempo lineare di Google compie un compromesso deliberato. RE2 garantisce un tempo di matching asintoticamente lineare rispetto alla lunghezza dell'input e opera entro un budget di memoria configurabile.

RE2 esclude i riferimenti all'indietro e le asserzioni lookaround perché i suoi progettisti non sanno come supportare questi costrutti preservando la stessa garanzia. Esclude anche le chiamate ricorsive a subroutine.

Il risultato è meno espressivo di PCRE2, ma più prevedibile per servizi che accettano pattern non attendibili o elaborano testo non attendibile. Questa differenza è una decisione architetturale, non la prova che un motore sostituisca universalmente l'altro.

PCRE2 offre controlli utilizzabili dai sistemi di produzione, inclusi limiti di matching, limiti di profondità, percorsi di esecuzione alternativi e un'attenta costruzione dei pattern. Questi controlli riducono l'esposizione, ma richiedono configurazione e test deliberati.

La scelta pratica dipende da chi controlla il pattern e l'input. Un'espressione controllata dallo sviluppatore su record delimitati comporta un rischio diverso da un'espressione fornita dall'utente che analizza grandi payload in un servizio condiviso.

Anche l'output richiesto conta. Un comando di ricerca può richiedere solo una corrispondenza booleana o alcune catture. Un compilatore, un elaboratore di documenti o un lettore di configurazioni necessita di risultati strutturati e posizioni di errore utili.

Ecco perché “una regex può trovarne la corrispondenza” raramente risolve una decisione ingegneristica. La capacità stabilisce la possibilità. Non stabilisce manutenibilità, limiti di risorse, qualità diagnostica o compatibilità.

Il disaccordo su Hacker News diventa più chiaro con questa prospettiva. Popov descrive ciò che motori selezionati possono esprimere. I critici chiedono a quali garanzie le applicazioni rinunciano quando si affidano a questa capacità.

Queste posizioni non sono opposte. Affrontano livelli diversi dello stesso sistema. L'errore importante consiste nel trasferire un'affermazione da un livello all'altro senza precisazioni.

La questione HTML espone il limite pratico del riconoscimento

Trovare la corrispondenza con un linguaggio non è lo stesso lavoro che costruire una rappresentazione affidabile di un documento.

Il comune avvertimento contro l'elaborazione HTML basata sulle regex combina diversi argomenti. HTML è annidato, i documenti reali sono malformati, i linguaggi incorporati complicano i confini dei token e le applicazioni necessitano di solito di output strutturato.

Solo il primo argomento riguarda direttamente l'espressività dei linguaggi formali. La ricorsione PCRE può affrontare l'annidamento. Non può, per questo solo fatto, risolvere i requisiti rimanenti.

Consideriamo un'applicazione che estrae link. Una semplice espressione può funzionare su markup controllato generato da un solo template. Può fallire quando > compare all'interno di un attributo tra virgolette o quando il testo di uno script assomiglia a un tag.

Commenti, riferimenti a caratteri, namespace, tag opzionali e regole di recupero del browser aggiungono altri casi. Ogni nuova condizione amplia il pattern, lasciando però un output meno strutturato di un DOM.

Questo non rende irresponsabile ogni regex per HTML. Un'espressione circoscritta può essere appropriata quando il contratto di input è rigoroso e le conseguenze di un errore sono limitate.

L'ambito deve essere esplicito. “Trovare un marcatore noto nel nostro frammento generato” è un'attività testuale delimitata. “Interpretare pagine web arbitrarie come farebbe un browser” è un'attività di elaborazione dei documenti.

Un parser assegna a ogni costrutto un ruolo con nome. Può associare posizioni nel sorgente, segnalare un token inatteso, recuperare dopo un errore ed esporre un albero per trasformazioni successive.

Una regex di grandi dimensioni spesso comprime queste distinzioni in gruppi e flusso di controllo. Sottopattern con nome e formattazione estesa aiutano, ma il motore restituisce comunque corrispondenze anziché un albero sintattico nativo.

Il divario di manutenzione cresce quando cambiano i requisiti. Supportare un'altra produzione grammaticale in un parser di solito significa aggiungere o modificare una regola. In una regex strettamente accoppiata, può modificare il backtracking e il comportamento delle catture altrove.

I test devono quindi coprire più di esempi validi rappresentativi. I team hanno bisogno di input non validi, casi quasi corrispondenti, input di grandi dimensioni, input annidati, casi Unicode e stringhe avversarie progettate per attivare percorsi costosi.

È anche qui che la documentazione diventa operativa anziché decorativa. Un'espressione complessa dovrebbe indicare il proprio motore, i flag, il contratto di input accettato, le catture previste, i limiti di dimensione e il motivo per cui non viene usato un parser.

I team che conservano le decisioni tecniche possono mantenere questi vincoli accanto a documenti di implementazione ricercabili. Una knowledge base ingegneristica condivisa aiuta i futuri manutentori a recuperare l'intento dietro codice di matching conciso.

La decisione chiave non è regex contro parser come identità rivali. È stabilire se l'attività richieda riconoscimento, estrazione, trasformazione, recupero o interpretazione completa.

Le regex restano eccellenti per tokenizzazione, convalida secondo regole delimitate, ricerca, filtraggio dei log e piccole estrazioni. Un parser diventa preferibile quando la struttura grammaticale è il dato di lavoro dell'applicazione.

La conclusione di Popov segue proprio questo confine. Respinge il divieto teorico assoluto, mantenendo al contempo la raccomandazione pratica di usare una libreria DOM per l'elaborazione HTML generica.

Questa sfumatura spesso scompare online. “Le regex non possono analizzare HTML” sopravvive perché previene errori comuni. “Alcuni motori regex possono riconoscere strutture context-free” resta vero perché la capacità sottostante esiste.

Una regola ingegneristica matura può sostenere entrambe le affermazioni. Non confondete un'impostazione predefinita utile con un teorema, e non confondete una costruzione teorica con un progetto di produzione.

Cosa l'argomento sulle regex continua a sottovalutare

Una maggiore espressività crea obblighi di sicurezza e manutenzione che una suite di test riuscita potrebbe non rivelare.

Il denial of service da espressioni regolari, o ReDoS, si verifica quando un matcher impiega un tempo eccessivo a esplorare alternative su input appositamente costruiti. Un aggressore può consumare capacità di elaborazione senza inviare un grande volume di traffico.

Le linee guida sul ReDoS descrivono motori che raggiungono tempi di esecuzione estremi quando pattern ambigui incontrano stringhe avversarie. Il pericolo emerge spesso in prossimità di una corrispondenza fallita.

Un validatore potrebbe elaborare rapidamente input ordinari perché il primo ramo ha successo. Un aggressore può fornire un lungo prefisso compatibile con molti percorsi, seguito da un carattere che invalida ogni percorso.

Il motore deve quindi riesaminare le scelte precedenti. Ripetizioni annidate, alternative sovrapposte e componenti opzionali possono moltiplicare lo spazio di ricerca. Un pattern conciso può nascondere questo comportamento durante la revisione del codice.

I backreference aggiungono un'altra dimensione di complessità. La ricerca sui loro limiti espressivi li considera un'estensione sostanziale supportata da molti motori diffusi. Il loro comportamento non può essere ridotto al normale matching a stati finiti.

Il saggio di Popov osserva che il matching con backreference introduce casi NP-completi. È un'affermazione sul problema generale, non una previsione che ogni pattern venga eseguito lentamente.

Molte espressioni con catture e backreference terminano rapidamente su input ordinari. I risultati sulla complessità avvertono che nessuna soluzione generale efficiente copre ogni caso, a meno che non cambino ipotesi fondamentali nella teoria della complessità.

La ricorsione introduce preoccupazioni distinte sulle risorse. Un pattern che segue input profondamente annidati consuma profondità gestita dal motore o uno stato equivalente. Le implementazioni applicano limiti e differiscono nel modo in cui la ricorsione interagisce con il backtracking.

Anche la versione del motore conta. PCRE2 ha modificato nel tempo la semantica della ricorsione per allinearsi più strettamente a Perl in determinate situazioni. Un pattern testato con una versione può comportarsi diversamente dopo una migrazione.

La portabilità è quindi limitata anche tra motori descritti come compatibili con Perl. Il supporto della sintassi, le regole Unicode, i valori delle catture, l'ordine di matching e la semantica della ricorsione possono differire.

Le regex generate dall'AI alzano la posta perché la generazione riduce l'attrito che un tempo limitava la complessità. Uno sviluppatore può richiedere un'unica espressione per una grammatica e ricevere in pochi secondi qualcosa di sintatticamente convincente.

Il pattern generato potrebbe puntare al flavor sbagliato. Potrebbe superare gli esempi nel prompt, pur non gestendo input malformati, consumando risorse eccessive o restituendo catture con semantica inattesa.

I revisori dovrebbero trattare le regex generate come codice generato. Devono identificare il motore, comprendere ogni costrutto non banale, eseguire test avversari e applicare limiti a input ed esecuzione.

La leggibilità non è qui una questione estetica. Un flusso di controllo illeggibile impedisce ai manutentori di identificare alternative sovrapposte o di accorgersi quando una piccola modifica crea backtracking catastrofico.

La modalità estesa fornisce spazi bianchi e commenti nei motori che la supportano. I gruppi con nome riducono la dipendenza da indici numerici variabili. Pattern più piccoli e composti possono chiarire le responsabilità.

Queste pratiche aiutano, ma la composizione deve rispettare la sintassi del motore. Alcuni linguaggi host interpolano stringhe prima che il compilatore regex le analizzi, producendo un ulteriore livello di escaping e possibili injection.

Frammenti non attendibili non dovrebbero mai essere inseriti in un pattern senza un escaping appropriato al motore. Gli utenti non attendibili non dovrebbero ricevere accesso senza restrizioni a un matcher con backtracking all'interno di un servizio condiviso.

La conclusione scettica è più circoscritta di “non usare mai regex avanzate”. È che ogni costrutto avanzato consuma una parte del budget di prevedibilità di un sistema.

Gli sviluppatori dovrebbero saper indicare cosa ricevono in cambio. La ricorsione può offrire un riconoscimento conciso per una struttura annidata delimitata. Un backreference può imporre un vincolo di uguaglianza che altrimenti richiederebbe codice procedurale.

Se il beneficio consiste solo nell'evitare un piccolo parser, il compromesso diventa più difficile da giustificare. I parser spesso forniscono errori migliori, un'evoluzione più chiara e output utilizzabile direttamente dal codice a valle.

Tre segnali determineranno se la lezione rimarrà

L'esito duraturo dipende dalla selezione del motore, dalla revisione del codice generato e dal fatto che i team testino il comportamento in caso di errore anziché soltanto gli esempi.

Il primo segnale è una selezione del motore più ampia ed esplicita. Gli sviluppatori dovrebbero smettere di trattare le regex come un unico linguaggio portabile e documentare se un pattern è destinato a PCRE2, RE2, JavaScript, Java, .NET, Rust o un'altra implementazione.

Se librerie e piattaforme rendono visibili le garanzie di esecuzione, l'argomento su Hacker News diventa più facile da risolvere. Gli sviluppatori possono discutere di un motore definito invece di dibattere un'etichetta sovraccarica.

Il secondo segnale riguarda il modo in cui gli assistenti di coding gestiscono le richieste di regex. I sistemi utili dovrebbero chiedere il flavor di destinazione, i limiti dell'input, le ipotesi sui dati attendibili e le catture richieste prima di generare espressioni complesse.

Dovrebbero anche spiegare i costrutti non supportati e proporre un parser quando l'output richiesto è strutturato. Se gli assistenti continueranno a produrre pattern densi senza questi controlli, aumenteranno i fallimenti di manutenzione e sicurezza.

Il terzo segnale è il testing avversario di routine. I team dovrebbero misurare le corrispondenze riuscite, i fallimenti tardivi, input lunghi e ripetuti, annidamenti profondi, confini Unicode e input modellati per massimizzare l'ambiguità.

Un pattern che supera dieci esempi amichevoli ha stabilito la correttezza solo per quegli esempi. Non ha dimostrato un comportamento accettabile nel caso peggiore né la compatibilità con i limiti di produzione.

Questi segnali rafforzano la lezione più ampia di Popov, restringendone al contempo l'applicazione. I moderni motori per pattern possono superare i limiti formali suggeriti dal loro nome. Questo fatto merita di essere compreso, non usato come approvazione universale di progettazione.

Il saggio riproposto offre anche una correzione utile a entrambi gli schieramenti. La teoria formale conta perché spiega quali garanzie sono disponibili. I dettagli di implementazione contano perché i motori distribuiti non preservano tutti tali garanzie.

Per gli sviluppatori che seguono il dibattito su Hacker News, la prossima azione è concreta. Identificate il motore dietro il vostro pattern di produzione più complesso, documentatene il contratto di input e testatene il caso di fallimento più lento. Poi chiedetevi se l'applicazione abbia bisogno di riconoscimento o di un parsing strutturato.

Se il pattern resta chiaro, delimitato e misurabile, mantenetelo. Se la sua correttezza dipende da comportamenti del flavor non documentati o da backtracking fragile, sostituite la grammatica nascosta con un parser esplicito.