Espressioni regolari: differenze tra le versioni
Riga 39: | Riga 39: | ||
equivale a: (a|aa|aaa) |
equivale a: (a|aa|aaa) |
||
a{3,} al meno tre a |
a{3,} al meno tre a |
||
equivale a: ( |
equivale a: (aaa*) |
||
[abc] uno qualsiasi dei '''caratteri''' a, b, o c |
[abc] uno qualsiasi dei '''caratteri''' a, b, o c |
||
Nota che abc non sono espressioni ma singoli caratteri |
Nota che abc non sono espressioni ma singoli caratteri |
Versione delle 08:35, 8 set 2005
Espressioni regolari
Un'espressione regolare è un formalismo che permette di definire un insieme di stringhe che soddisfano certe condizioni.
Teoria
Le espressioni regolari sono equivalenti a grammatiche regolari destre (o sinistre). Ciò vale a dire che per ogni grammatica regolare esiste al meno un'espressione regolare equivalente e vice versa. Dato un insieme di stringhe se esiste un'espressione regolare che lo rappresenti ne esistono infinite.
Le espressioni regolari sono una delle cose intorno a cui c'è più confusione. Per questo ecco una serie di distinguo...
Espressioni regolari e globbing
vedi Globbing
Tipi di espressioni regolari
Ogni programma che fa uso di espressioni regolari tende a definire un insieme di regole con caratteristiche che variano un po'. Per questo qui si descriverà un insieme di regole abbastanza vasto da essere utile per la maggior parte degli usi.
Descrizione
Insieme base di regole
Questo è l'insieme minimo di regole accettate da tutti i programmi, ha la stessa capacità espressiva di insiemi di regole più grandi, Nota che ogni lettera può corrispondere ad un'espressione regolare. TODO definire precedenza degli operatori * | concatenzione formalmente.
espressione significato abc abc (concatenazione di stringhe) (e) e (operatore per definire precedenza) (a|b) a oppure b a* a ripetuto 0 o più volte a? a ripetuto 1 o più volte
Esempi di precedenza
espressione significato aa* (a)(a*) aa|bb (aa)|(bb) aa|bb* (aa)|((bb)*)
Estensioni delle regole
espressione significato a+ a ripetuto 1 o più volte equivale a: (aa*) a{1,3} a ripetuto da 1 a tre volte equivale a: (a|aa|aaa) a{3,} al meno tre a equivale a: (aaa*) [abc] uno qualsiasi dei caratteri a, b, o c Nota che abc non sono espressioni ma singoli caratteri equivale a: (a|b|c) [0-9] uno qualsiasi dei caratteri nell'intervallo. L'intervallo è calcolato sui codici ASCII equivalente a:(0|1|2|3|4|5|6|7|8|9) [^a-z] tutti i caratteri non compresi nell'intervallo equivalente: troppo lungo da scrivere... . tutti i caratteri (di solito è escluso l'a capo \n) equivalente: troppo lungo da scrivere... ^ inizio riga equivalente: non esiste $ fine riga equivalente: non esiste
Questi ultimi due simboli non hanno un equivalente in termini di regole base. Nota che data la riga (\n indica il carattere di a capo)
riga\n
le due espressioni sono differenti
espressione stringa riconosciuta a\n a\n a$ a
Questo è importante poichè in molte situazioni la stringa riconosciuta può essere letta da un'apposita variabile. (es vim, flex, perl)
Esempi
La maggior parte delle espressioni regolari riconosce insiemi di stringhe con cardinalità infinita, per questo il più delle volte verrano elencate solo alcune delle stringhe riconosciute
espressione stringhe riconosciute ^[^ ]* la prima parola di una riga ^.*$ una riga intera (.|\n){20,20} una stringa di esattamente 20 caratteri
(F)lex e le espressioni regolari
Bibliografia
- J.E. Hopcroft, R. Motwani, J.D. Ullman : Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001.