Dettagli di implementazione di espressioni regolari

A question that I answered mi chiedo:Dettagli di implementazione di espressioni regolari

Come vengono implementate le espressioni regolari in Python? Che tipo di garanzie di efficienza ci sono? L'implementazione è "standard" o è soggetta a modifiche?

Ho pensato che le espressioni regolari sarebbero state implementate come DFA e quindi erano molto efficienti (richiedendo al massimo una scansione della stringa di input). Laurence Gonsalves ha sollevato un punto interessante che non tutte le espressioni regolari di Python sono regolari. (Il suo esempio è r "(a +) b \ 1", che corrisponde ad alcuni numeri di a, a b, e quindi lo stesso numero di a di prima. Questo chiaramente non può essere implementato con un DFA.

Quindi, per ribadire: quali sono i dettagli di implementazione e le garanzie delle espressioni regolari Python?

Sarebbe anche bello se qualcuno potesse dare una sorta di spiegazione (alla luce dell'implementazione) sul motivo per cui le espressioni regolari "cat | catdog" e "catdog | cat" portano a risultati di ricerca diversi nella stringa " catdog ", come indicato nello question that I referenced before.

fonte

2009-05-09 Tom

Le implementazioni di espressioni regolari di oggi hanno molte più funzioni di quelle descritte nella classica definizione di espressioni regolari. – Gumbo

@Gumbo: Effettivamente lo fanno ... questa è una delle ragioni della mia domanda. Sono curioso di una implementazione specifica perché non è sicuro assumere un DFA (a causa di queste funzionalità extra). – Tom

Usa la fonte, Luke (http://svn.python.org/view/python/trunk/Lib/re.py?view=markup). In realtà sembra abbastanza ben documentato. –

Il modulo re di Python era basato su PCRE, ma è passato alla propria implementazione.

Questo è il collegamento allo C code.

Sembra che la libreria si basi sul backtracking ricorsivo quando è stato eseguito un percorso errato.

alt text

regolare espressione e la dimensione del testo n
una? ⁿ un ⁿ corrispondenza di un ⁿ

Tenete a mente che questo grafico non è rappresentativo delle normali ricerche regex.

http://swtch.com/~rsc/regexp/regexp1.html

fonte

2009-05-09 23:03:17 Unknown

(mi rendo conto che questo commento è in ritardo) Mi piace la tua spiegazione, eccetto che non penso che l'ultima parte sia corretta sulla corrispondenza di "cat | catdog". Usando "cat | catdog" si ottiene "cat" come risultato e "catdog | cat" produce "catdog" come risultato. Bbasicamente l'ordine conta. Ci sono due cose in corso. Prima di tutto, 'findall' trova solo tutte le corrispondenze non sovrapposte. Quindi non dovresti aspettarti "cat" E "catdog". In secondo luogo, se dovessi implementarlo, penso sia facile dire che l'NFA può essere convertito in un DFA e quindi si dovrebbe avere "c -> a -> * t * -> d -> o -> * g *" dove gli asterischi indicano uno stato finale. – Tom

(continua ...): In pratica, la "t" è uno stato finale, e sento che la ricerca dovrebbe sempre restituire "gatto" perché è tutto ciò che serve per trovare una corrispondenza. Tuttavia, la tua risposta è stata utile e lo accetterò (mesi dopo :-). – Tom

Tuttavia, i DFA non sono un approccio perfetto. La corrispondenza con [ab] * b [ab]^n' richiede la memoria 'O (2^n)' usando un DFA, ma può essere eseguita in tempo lineare e memoria usando un NFA. –

ci sono "garanzie di efficienza" a Python ER più rispetto a qualsiasi altra parte del linguaggio (libreria standard C++ s 'è l'unico standard di lingua diffusa So che cerca di stabilire tali standard - ma non ci sono standard, nemmeno in C++, specificando che, per esempio, moltiplicare due intro deve richiedere tempo costante, o qualcosa del genere); né esiste alcuna garanzia che le grandi ottimizzazioni non vengano applicate in qualsiasi momento.

Oggi, F. Lundh (originariamente responsabile dell'implementazione dell'attuale modulo RE di Python, ecc.), Presentando Unladen Swallow in Pycon Italia, ha detto che una delle strade che esploreranno è quella di compilare le espressioni regolari direttamente al codice intermedio LLVM (piuttosto che il loro stesso codice bytecode da interpretare con un runtime ad hoc) - poiché anche il codice Python ordinario viene compilato su LLVM (in una prossima versione di Unladen Swallow), una RE e il suo codice Python circostante potrebbero quindi essere ottimizzati insieme, anche in modi abbastanza aggressivi a volte. Dubito che qualcosa del genere sarà molto vicino a "pronto alla produzione" molto presto, però ;-).

fonte

2009-05-10 21:01:56

Matching regular expressions with backreferences is NP-hard, che è almeno difficile quanto NP-Complete. Ciò significa fondamentalmente che è difficile quanto qualsiasi problema tu possa incontrare, e la maggior parte degli informatici pensa che potrebbe richiedere tempi esponenziali nel peggiore dei casi.Se potessi abbinare espressioni "regolari" (che in realtà non sono, in senso tecnico) in tempo polinomiale, potresti vincere a million bucks.

fonte

2009-10-28 04:24:21

Dettagli di implementazione di espressioni regolari

risposta

Problemi correlati