Differenze tra le versioni di "Espressioni regolari"

nessun oggetto della modifica
(creazione)
=Espressioni regolari=
Un''''espressione regolare''' è un formalismo che permette di definire un insieme di [[stringa|stringhe]] che soddisfano certe condizioni.
 
==Teoria==
Le espressioni regolari sono una delle cose intorno a cui c'è più confusione. Per questo l'articolo inizia con una serie di distinguo...
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 l'articolo inizia conecco una serie di distinguo...
 
==Espressioni regolari e globbing==
vedi [[Globbing]]
 
==Tipi di espressioni regolari==
==Caratteristiche==
Ogni programma che fa uso di espressioni regolari tende a definire un insieme di [[regole|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==
===Inisieme 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 (concatenzaione di stringhe)
(e) e operatore per definire precednza
(a|b) a oppure b
a* a ripetuto 0 o più volte
a? a ripetuto 0 o una volta
====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 a 1 a tre volte
equivale a: (a|aa|aaa)
a{3,} al meno tre a
equivale a: (aaaa*)
[abc] uno qualsiasi dei '''caratteri''' a, b, o c
Nota che abc non sono espressioni ma singoli carateri
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 sono non hanno un equivalente in termini di regole base. Nota che data la riga (''\n'' indica il caratter 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 espresisoni regolari riconosce insiemi di strnghe con cardinalità infinita, per questo il più delle volte verrano elencati solo alcune delle strubghe 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.