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

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:

• Finite-state machine
• State diagram