Perché le espressioni regolari possono avere un tempo di esecuzione esponenziale?

È ansible scrivere un Regex che necessita in alcuni casi di un tempo di esecuzione esponenziale. Tale esempio è (aa|aa)* . Se c’è un input di un numero dispari di a s ha bisogno di un tempo di esecuzione esponenziale.

È facile provarlo. Se l’input contiene solo a s e ha lunghezza 51, il Regex ha bisogno di alcuni secondi per calcolare (sulla mia macchina). Invece se la lunghezza di input è 52 il suo tempo di calcolo non è evidente (ho provato questo con il parser Regex incorporato di JavaRE).

Ho scritto un parser Regex per trovare il motivo di questo comportamento, ma non l’ho trovato. Il mio parser può creare un AST o un NFA basato su un Regex. Dopodiché può tradurre l’NFA in DFA . Per fare ciò usa l’ algoritmo di costruzione del powerset .

Quando analizzo il Rgex menzionato sopra, il parser crea un NFA con 7 stati: dopo la conversione ci sono solo 3 stati rimasti nel DFA. Il DFA rappresenta il Regex più sensato (aa)* , che può essere analizzato molto velocemente.

Quindi, non capisco perché ci siano parser che possono essere così lenti. Qual è la ragione di questo? Non traducono la NFA in DFA? Se sì, perché no? E quali sono i motivi tecnici per cui calcolano così lentamente?

Russ Cox ha un articolo molto dettagliato sul perché questo è e sulla storia delle regex ( parte 2 , parte 3 ).

La corrispondenza delle espressioni regolari può essere semplice e veloce, utilizzando tecniche basate su automi finiti noti da decenni. Al contrario, Perl, PCRE, Python, Ruby, Java e molti altri linguaggi hanno implementazioni di espressioni regolari basate sul backtracking ricorsivo che sono semplici ma possono essere terribilmente lenti. Con l’eccezione delle backriver, le funzionalità fornite dalle implementazioni di backtracking lento possono essere fornite dalle implementazioni basate su automi a velocità notevolmente più veloci e coerenti.

In gran parte, si tratta di proliferazione di funzioni non regolari in espressioni “regolari” come backreferences e ignoranza (continua) della maggior parte dei programmatori che ci sono alternative migliori per espressioni regex che non contengono tali caratteristiche (che sono molte di esse) .

Mentre scriveva l’editor di testo sam nei primi anni ’80, Rob Pike ha scritto una nuova implementazione di espressioni regolari, che Dave Presotto ha estratto in una libreria apparsa nell’ottava edizione. L’implementazione di Pike incorporava il tracciamento delle submatch in un’efficiente simulazione NFA ma, come il resto della fonte dell’Ottava edizione, non era ampiamente distribuito. Lo stesso Pike non si rese conto che la sua tecnica era qualcosa di nuovo. Henry Spencer ha reimplementato l’interfaccia della libreria Eighth Edition da zero, ma utilizzando il backtracking e ha rilasciato la sua implementazione nel pubblico dominio. È diventato molto diffuso, servendo infine come base per le implementazioni di espressioni regolari lente menzionate in precedenza: Perl, PCRE, Python e così via. (Nella sua difesa, Spencer sapeva che la routine poteva essere lenta, e non sapeva che esisteva un algoritmo più efficiente.Aveva anche avvertito nella documentazione, “Molti utenti hanno trovato la velocità perfettamente adeguata, anche se sostituendo l’interno di egrep con questo codice sarebbe un errore. “) L’implementazione delle espressioni regolari di Pike, estesa per supportare Unicode, è stata resa disponibile gratuitamente con sam alla fine del 1992, ma l’algoritmo di ricerca di espressioni regolari particolarmente efficiente è passato inosservato.

Le espressioni regolari conformi a questa definizione formale sono calcolabili in tempo lineare, poiché hanno corrispondenti automi finiti. Sono costruiti solo da parentesi, alternative | (a volte chiamato sum), stella di Kleene * e concatenazione.

L’estensione delle espressioni regolari aggiungendo, ad esempio, riferimenti a ritroso può portare anche a espressioni regolari complete di NP. Qui puoi trovare un esempio di espressione regolare che riconosce numeri non primi.

Immagino che, un’implementazione così estesa possa avere un tempo di corrispondenza non lineare anche in casi semplici.

Ho fatto un rapido esperimento in Perl e la tua espressione regolare calcola altrettanto velocemente per il numero pari e dispari di “a”.