Utente:LoStrangolatore/Espressioni regolari/Motore
Questa pagina illustra le caratteristiche di un motore di analisi che accetta in ingresso le regex:
- richiami alla teoria dei linguaggi formali;
- il funzionamento ideale del motore, dal punto di vista dell'utente;
- spunti per l'implementazione concreta di un motore di analisi.
Questa pagina non vuole essere esaustiva; al contrario, illustra l'argomento a grandi linee, fornendo al lettore richiami teorici e spunti di approfondimento.
TODO Contenuti da includere: w:en:ReDoS
Teoria modifica
In matematica, un insieme di stringhe viene chiamato linguaggio formale. Il set di regole che lo definiscono (cioè le regole matematiche che stabiliscono se una stringa appartiene o no all'insieme) viene chiamato grammatica formale. La branca della matematica che studia i linguaggi formali viene chiamata teoria dei linguaggi formali. È possibile classificare le grammatiche formali in base alla loro potenza espressiva, e il risultato è la cosiddetta "gerarchia di Chomsky".
Alcune grammatiche prendono il nome di grammatiche regolari. Esse permettono di esprimere le stringhe con delle regole del tipo ... . I linguaggi generati dalle grammatiche regolari si chiamano linguaggi regolari.
- Espressioni regolari e grammatiche regolari
Una espressione regolare è una notazione compatta che definisce un insieme di stringhe. Questa notazione ricorda molto quella usata per descrivere le grammatiche formali, e la somiglianza è evidente per le grammatiche regolari. Ad esempio, l'equivalente dell'asterisco delle espressioni regolari è chiamato stella di Kleene.
Le espressioni regolari hanno maggiore potenza espressiva rispetto alle grammatiche regolari, nel senso che
- tutte le grammatiche regolari possono essere convertite in espressioni regolari equivalenti,
- ma non è vero il contrario: esistono alcune regex che permettono di definire linguaggi per i quali non esiste alcuna grammatica regolare.
Il motivo è che le regex supportano alcuni costrutti che non hanno equivalenti nel mondo delle grammatiche regolari. Ad esempio i backreference.
Le regex possono esprimere solo un insieme ristretto di tutti i linguaggi formali possibili. In altre parole: non tutti gli insiemi di stringhe possono essere espressi tramite regex. Questo limite scaturisce dalla stessa natura delle espressioni regolari, a prescindere perfino dalle estensioni peculiari dei diversi ambienti di esecuzione.
- Automi
Al livello più astratto, un motore di analisi può essere visto come una macchina che accetta una stringa come input e restituisce determinati output. La macchina scorre la stringa, controllando un carattere alla volta, e cambiando il proprio stato interno o terminando con il messaggio di "stinga trovata" o "stringa non trovata". In quest'ottica, la regex è il programma che governa la macchina, e ogni simbolo nella regex è una istruzione.
Una delle caratteristiche delle grammatiche regolari (e delle espressioni regolari equivalenti) è che possono essere implementate tramite macchine semplici e facili da progettare, chiamate "automi a stati finiti". Per linguaggi non regolari, sono necessarie macchine più complesse.
- Approfondimenti su Wikipedia
Per un'introduzione al concetto di ASF e alle possibili rappresentazioni grafiche, si rimanda alle seguenti voci della Wikipedia in lingua inglese: