Funzionamento delle corrispondenze
Nel modulo di espressioni regolari di .NET Framework, un matcher di espressioni regolari di backtracking, è incorporato un modulo NFA (Nondeterministic Finite Automaton) tradizionale, quale quello utilizzato da Perl, Python, Emacs e Tcl. Tale caratteristica lo distingue dai moduli di gestione di espressioni regolari DFA (Deterministic Finite Automaton) pure, più veloci ma soggetti a maggiori limitazioni, quali quelli di awk, egrep o lex. Questa caratteristica lo distingue inoltre dai POSIX NFA, standardizzati ma più lenti.
Tre tipi di moduli di espressioni regolari
In questa sezione vengono illustrati i vantaggi e gli svantaggi dei tre tipi di moduli e la ragione per cui il modulo di .NET Framework consente di implementare uno strumento per la ricerca NFA tradizionale.
I moduli di gestione DFA operano in un tempo lineare, perché non effettuano backtracking e quindi non esaminano mai due volte lo stesso carattere. Anche tali moduli possono garantire l'individuazione della stringa corrispondente più lunga. Poiché tuttavia un modulo di gestione DFA contiene solo stati finiti, non può valutare le corrispondenze relative a un criterio di ricerca che include backreference e, poiché non crea un'espansione esplicita, non può catturare sottoespressioni.
I moduli NFA tradizionali consentono di eseguire algoritmi più rigidi per la ricerca di testo con funzionalità di backtracking, verificando tutte le possibili espansioni di un'espressione regolare in un determinato ordine e accettando la prima corrispondenza. Poiché un modulo di gestione NFA tradizionale crea una specifica espansione dell'espressione regolare per una corrispondenza individuata, può catturare le corrispondenze di sottoespressioni e le corrispondenze dei backreference. Per effetto del backtracking, un modulo di gestione NFA tradizionale può tuttavia tornare sullo stesso identico stato più volte, se a questo si arriva in più modi diversi. Di conseguenza, nei casi peggiori si può assistere a rallentamenti di carattere esponenziale. Poiché inoltre un modulo di gestione NFA tradizionale accetta la prima corrispondenza trovata, è possibile che non individui altre corrispondenze, che potrebbero anche essere più lunghe.
I moduli di gestione POSIX NFA sono simili ai moduli di gestione NFA tradizionali, con la sola eccezione che continuano il backtracking fino a maturare la certezza di aver trovato la corrispondenza più lunga. Di conseguenza, un modulo di gestione POSIX NFA è più lento di un modulo di gestione NFA tradizionale e quando si utilizza un POSIX NFA non è possibile favorire l'individuazione di una corrispondenza più breve rispetto a una più lunga modificando l'ordine di ricerca del backtracking.
I programmatori preferiscono i moduli di gestione NFA tradizionali, poiché sono più "espressivi" di quelli DFA o POSIX NFA. Nel caso peggiore risulteranno più lenti ma, a dispetto di questo, potranno essere impostati in modo da trovare le corrispondenze in tempo lineare o polinomiale, utilizzando criteri che riducano le ambiguità e limitino il backtracking.
Funzionalità del modulo di .NET Framework
Oltre ai vantaggi offerti da un modulo NFA tradizionale, nel modulo di espressioni regolari di .NET Framework è incluso un set completo di costrutti che consente ai programmatori di impostare il modulo di backtracking. Tali costrutti possono essere utilizzati per velocizzare l'individuazione delle corrispondenze o per favorire specifiche espansioni rispetto ad altre.
Le altre caratteristiche includono le seguenti funzionalità:
Quantificatori non onerosi: ??, *?, +?, {n,m}?. Indicano al modulo di gestione del backtracking di cercare prima nel numero minimo di ripetizioni. Al contrario, i quantificatori onerosi ordinari cercano prima la corrispondenza nel numero massimo di ripetizioni.
Lookahead positivo. Consente al modulo di gestione del backtracking di ritornare alla stessa posizione del testo quando viene soddisfatta una sottoespressione. Risulta utile per cercare all'interno del testo verificando più criteri a partire dalla stessa posizione.
Lookahead negativo. Aggiunge la capacità di considerare soddisfatta un'espressione quando una sottoespressione non risulta soddisfatta. Risulta particolarmente utile per abbreviare una ricerca, poiché spesso è molto più semplice formulare un'espressione relativa a un caso da eliminare che non un'espressione che individua i casi da includere. È difficile, ad esempio, scrivere un'espressione per le parole che non iniziano con "non".
Valutazione condizionale. Consente al modulo di gestione di eseguire una ricerca utilizzando più criteri alternativi, in base ai risultati alle sottoespressioni precedentemente soddisfatte. In tal modo si dispone di una forma più efficace di riferimento a corrispondenze memorizzate che consente, ad esempio, di considerare soddisfatta la sottoespressione che cerca una parentesi chiusa solo quando una parentesi aperta è stata precedentemente catturata da un'altra sottoespressione.
Sottoespressioni nonbacktracking, anche note come sottoespressioni onerose. Il modulo di backtracking è così in grado di garantire che una sottoespressione corrisponda solo alla prima corrispondenza trovata per tale sottoespressione, come se l'espressione venisse eseguita indipendentemente dall'espressione che la contiene. Senza questo costrutto, le ricerche di backtracking condotte dall'espressione più grande possono modificare il comportamento di una sottoespressione.
Corrispondenza da destra verso sinistra. Risulta utile quando si effettua la ricerca da destra verso sinistra invece che da sinistra verso destra oppure nei casi in cui è più efficiente iniziare l'individuazione di una corrispondenza dalla parte destra del criterio anziché a sinistra.
Lookbehind positivo e negativo. Simile al lookahead. Poiché il modulo di gestione delle espressioni regolari consente la corrispondenza completa da destra verso sinistra, le espressioni regolari consentono lookbehind illimitati.