Introduzione al linguaggio delle espressioni regolari così
come definito dallo standard POSIX.
Oltre a specificare cosa sono e a cosa servono le espressioni
regolari, sono preliminarmente definiti i concetti di stringa
di input, di pattern, di carattere semplice e di
metacarattere.
Lo scritto, inoltre, tratta il significato e il funzionamento
dei principali metacaratteri secondo lo standard
considerato.
| Autore | Giacomo Mengucci |
|---|---|
| Licenza | FDL |
| Ultimo Aggiornamento | 14/10/2007 |
Le espressioni regolari nascono per soddisfare una esigenza specifica: la selezione e la modifica di parti arbitrarie di testo in relazione al tipo e alla posizione dei caratteri che le compongono.
Si supponga di dover selezionare ed elencare i termini
marcati dai tag <dfn> </dfn> presenti
su un sorgente HTML; tali termini,
utili per la creazione di un glossario, possono essere sparsi
in una qualsiasi parte del sorgente HTML.
Se, ad esempio, nel sorgente è presente una riga di testo del
tipo:
I <dfn>tag</dfn> di tipo <dfn>block-level</dfn> sono diversi e si distinguono dai tag di tipo <dfn>in-line</dfn>
i termini da selezionare ed elencare sono:
tag block-level in-line
Il testo del file HTML che contiene la riga menzionata è la così detta stringa sorgente, cioè una sequenza arbitraria di caratteri su cui ricercare e selezionare le parti volute.
Le parti da ricercare e selezionare non sono altro che sotto stringhe della stringa sorgente.
Per mezzo delle espressioni regolari è possibile ricercare e selezionare sotto stringhe di una stringa sorgente che hanno determinate caratteristiche.
le espressioni regolari, o REGEXP, sono un vero e proprio linguaggio simbolico, con una sintassi e una semantica, attraverso cui costruire un pattern, cioè un modello che descrive un insieme astratto di una o più stringhe, da confrontare con le sotto stringhe di una stringa sorgente.
Il pattern matching è l'attività di confronto fra l'insieme delle stringhe descritte con il pattern e l'insieme delle sotto stringhe ricavabili dalla stringa sorgente, al fine di verificarne le corrispondenze.
Per soddisfare l'esigenza di selezionare i termini marcati fra i tag <dfn> e </dfn>, ad esempio, è possibile utilizzerò la seguente espressione regolare:
<dfn>\([^<]\{1,\}\)</dfn>.
I programmi che utilizzano e capiscono le espressioni
regolari sono molteplici, ciascuno per un suo scopo
specifico, come ad esempio la modifica automatica della
sotto stringa selezionata.
Infatti, le espressioni regolari da sole non bastano,
occorrono anche i programmi che eseguono le manipolazioni sul
testo selezionato.
Lo storico programma, nei sistemi UNIX like, per svolgere
tale compito è SED.
Riprendendo l'esempio dei termini marcati da <dfn> </dfn>, il seguente comando SED individua detti termini, li estrae dalla stringa sorgente e li stampa sullo standard output:
sed -n -e 's/<dfn>\([^<]\{1,\}\)<\/dfn>/§\1§/g' -e 's/[^§]*§\([^§]\{1,\}\)§[^§]*/\1\n/gp' *.html
Il Pattern è una sequenza di caratteri (stringa)
costruita secondo specifiche regole sintattiche e
semantiche delle espressioni regolari.
Esso esprime un modello descrittivo di un insieme astratto
di stringhe da ricercare all'interno di un'altra sequenza
di caratteri, detta stringa di input, al fine di verificarne
una corrispondenza.
Il pattern è formato da caratteri semplici o da metacaratteri.
I caratteri semplici rappresentano, e quindi corrispondono, a se stessi.
I metacaratteri hanno un significato speciale: possono, ad esempio, rappresentare indistintamente una pluralità di caratteri semplici, oppure possono definire particolari regole di corrispondenza rispetto al carattere semplice immediatamente precedente, o rispetto a sottoespressioni regolari (altri metacaratteri possono avere altri significati che saranno comunque appositamente studiati).
Ciascun carattere semplice in un pattern può essere considerato come un elemento di base della regexp, nel senso che viene ricercato singolarmente sulla stringa di input.
I caratteri semplici non solo devono esistere nella stringa
di input, ma devono esistere secondo l'ordine sequenziale in
cui sono descritti nel pattern.
Indicare i caratteri semplici uno di seguito all'altro, vuol
dire concatenare due o più elementi di base della regexp e vuol
dire definire una regola di corrispondenza basta sull'ordine
sequenziale di quei elementi. (ciascun carattere deve esistere
singolarmente nella sequenza descritta attraverso la
concatenazione).
Il . rappresenta un
qualsiasi carattere singolo, compreso lo spazio e ogni altro
carattere non stampabile.
L'unico carattere che non è rappresentato dal . è il newline \n; in realtà alcuni programmi che fanno
uso delle regexp implementano il . in modo che rappresenti anche il
newline (AWK è uno di questi
programmi).
Anche il metacarattere .
è un elemento di base,
nel senso che realizza la corrispondenza con un singolo
carattere ed anche per esso vale il principio della concatenazione, per
cui quel qualsiasi carattere ad esclusione del newline deve
esistere secondo l'ordine sequenziale definito nel pattern.
Ovviamente il . può essere
inserito in qualsiasi posizione della sequenza che costituisce
il pattern.
Se la stringa di input fosse la parola carma, applicando i tre pattern di esempio si avrebbero le seguenti corrispondenze:
| Pattern | Corrispondenza |
|---|---|
| c... | carm |
| c..a | nessuna corrispondenza |
| ...a | arma |
Alla base della verifica delle corrispondenze fra pattern e stringa
di input, vi è un confronto carattere per
carattere fra le due sequenze di caratteri.
In pratica il motore regexp per prima cosa
risolve i significati dei metacaratteri e
poi procede al confronto del primo carattere della stringa di
input con il primo carattere del pattern.
Se questo primo confronto dà una
corrispondenza, il motore confronta il secondo
carattere della stringa di input con il secondo carattere del
pattern; se anche questo confronto da una corrispondenza, si
confrontano i due terzi caratteri e così via, nel caso di
corrispondenze successive, fino ad esaurire i caratteri del
pattern.
Ma cosa succede se uno dei confronti non realizza una corrispondenza?
Si supponga che il confronto fra il primo carattere della stringa di input ed il primo carattere del pattern abbia dato una corrispondenza; in tal caso il secondo carattere della stringa di input viene confrontato con il secondo carattere del pattern; tale confronto fallisce, cioè non dà una corrispondenza, ed allora il motore di ricerca azzera la corrispondenza rilevata fra i due primi caratteri ed incomincia un nuovo confronto, che riguarderà il primo carattere del pattern e il secondo carattere della stringa di input.
Se questo confronto dà una corrispondenza, allora il terzo
carattere della stringa di input viene confrontato con il
secondo carattere del pattern; se c'è corrispondenza si
confrontano il quarto ed il terzo rispettivamente della stringa
di input e del pattern; se invece non c'è corrispondenza si
azzerano quelle finora rilevate e si riparte con un confronto
fra il terzo carattere della stringa di input ed il primo
carattere del pattern.
Tutti i confronti, fino ad esaurimento di una delle due
stringhe, seguono questa logica.
Come esempio si spiegheranno passo passo i vari confronti implementati dal motore di ricerca nei casi definiti nella tabella "Corrispondenze per la parola carma":
Il metacarattere [] è stato definito composto perché esso in realtà è formato da una sequenza di caratteri racchiusi tra parentesi quadre. Da un punto di vista logico, però, tutto ciò che è racchiuso fra parentesi quadre è considerato come facente parte di un unico elemento base che viene valutato secondo le seguenti regole:
Le parentesi quadre servono a delimitare l'insieme dei caratteri con cui verificare la corrispondenza sulla stringa di input.
Qualora i caratteri da indicare fra parentesi quadre formano una sequenza ordinata, come ad esempio [abcdefg] oppure [0123456789], si può usare una sintassi semplificata, indicando il carattere iniziale e finale della sequenza separati da un simbolo - (meno).
[abcdefg] si può scrivere anche [a-g]
[0123456789] si può scrivere anche [0-9]
E' ammessa anche una sintassi mista: consideriamo l'elenco [a-glp-z56-9]; sono compresi in tale elenco i caratteri da a a g (a-g), il carattere l, i caratteri da p a z (p-z), il carattere 5 ed infine i caratteri da 6 a 9 (6-9).
Il simbolo -,
all'interno delle parentesi quadre, ha il significato
speciale di definire un intervallo.
Se lo stesso simbolo è indicato come primo carattere
dell'elenco, perde il suo significato speciale e
corrisponde solo a se stesso.
Il simbolo .
all'interno dell'elenco perde il suo significato
speciale (corrisponde a se stesso).
In generale tutti i simboli che all'esterno dell'elenco sono
dei metacaratteri, all'interno dell'elenco o perdono il loro
significato speciale, corrispondendo solo a se stessi, oppure
cambiano il loro significato speciale. (un esempio di tale
cambiamento si può notare nel metacarattere
^).
Se il primo carattere dopo la parentesi quadra aperta è il simbolo ^, allora la corrispondenza sarà verificata, anziché sui caratteri che fanno parte dell'elenco, sui caratteri che invece non vi fanno parte (escluso il newline).
Tutto ciò che segue il simbolo ^ all'interno dell'elenco sarà escluso
dalla corrispondenza.
Interessante è notare che, mentre il metacarattere
. corrisponde ad un
qualsiasi carattere escluso il newline, il metacarattere
[^] corrisponde ad un
qualsiasi carattere escluso il newline ed esclusi i caratteri
indicati nell'elenco che segue il simbolo ^.
Se il simbolo ^ non è il primo carattere dell'elenco, esso non ha alcun significato speciale e quindi corrisponde solo a se stesso.
Qualora la parentesi quadra chiusa (]) deve far parte dell'elenco, come
carattere per verificare una corrispondenza, è sufficiente
che essa sia indicata come primo carattere dell'elenco,
oppure, se la si vuole escludere dalla ricerca insieme a
tutti i caratteri che eventualmente seguono, è necessario
indicarla subito dopo il simbolo ^.
Se nell'elenco c'è anche il simbolo -, come carattere che deve
corrispondere a se stesso, la parentesi quadra va posta
subito dopo detto simbolo, che sarà quindi il primo carattere
dell'elenco (oppure il secondo se il primo carattere dovesse
essere il simbolo ^).
Lo standard POSIX per le regexp ha definito speciali classi di caratteri che possono essere rappresentate attraverso speciali simboli composti:
| Classe | Descrizione |
|---|---|
| [:alnum:] | L'insieme di tutti i caratteri alfanumerici (lettere e numeri) compresi gli spazi bianchi |
| [:alpha:] | L'insieme dei soli caratteri alfabetici, siano essi maiuscoli o minuscoli (corrisponde a [a-zA-Z]) |
| [:digit:] | L'insieme di tutti i caratteri numerici (corrisponde a [0-9]) |
| [:blank:] | L'insieme composto dal carattere spazio e dai caratteri di tabulazione |
| [:space:] | L'insieme di tutti i tipi di spazi visualizzabili |
| [:lower:] | L'insieme di tutti i caratteri alfabetici minuscoli |
| [:upper:] | L'insieme di tutti i caratteri alfabetici maiuscoli |
| [:punct:] | L'insieme di tutti i caratteri di punteggiatura |
| [:graph:] | L'insieme di tutti i caratteri che sono visibili a video e allo stesso tempo stampabili (tutti i tipi di spazio sono esclusi) |
| [:print:] | L'insieme di tutti i caratteri stampabili |
| [:cntrl:] | L'insieme di tutti i caratteri di controllo (di norma non stampabile e non visibili) |
| [:xdigit:] | L'insieme di tutte le cifre esadecimali |
Queste classi possono essere utilizzate nei pattern per ricercare una corrispondenza di un carattere che fa parte della classe specificata.
Da notare che i simboli di classe sono sempre racchiusi in una ulteriore coppia di parentesi quadre, cioè fanno sempre parte di un elenco, anche quando una di tali classi deve essere utilizzata da sola.
I caratteri semplici e i metacaratteri . e [], sono elementi di base di un pattern, attraverso cui ricercare, nella stringa di input, un singolo carattere in una determinata posizione.
I metacaratteri trattati qui di seguito, invece servono a definire una corrispondenza ripetuta dell'elemento di base che immediatamente lo precede nel pattern.
Il metacarattere *
specifica che l'elemento di base
che lo precede nel pattern potrà essere ripetuto 0 o più
volte nella stringa di input.
In pratica è come se dicessi al motore di regexp, che, a
partire da quella posizione, l'elemento di base a cui
l'asterisco si riferisce può esserci o può non esserci, e se
c'è può essere ripetuto più volte.
Oltre che i caratteri semplici
l'asterisco può essere posto dopo altri elementi di base,
come il metacarattere . ed il metacarattere [].
Nel primo caso, la corrispondenza sarà verificata per 0 o più
caratteri qualsiasi con esclusione del newline.
Nel secondo caso invece, la corrispondenza sarà verificata
per 0 o più caratteri fra quelli indicati nell'elenco, cioè
all'interno delle parentesi quadre.
La ripetizione di più caratteri di un elenco realizza la
corrispondenza indipendentemente da quale sia il carattere
ripetuto, purché esso faccia parte dell'elenco.
Il pattern c[st]* realizza
la corrispondenza per tutte le seguenti sotto stringhe:
cssssssssss, ctttttttttt, c, cs, ct, csst, ctsst, cstst, cttttsssts ecc.
L'espressione regolare .* utilizzata in modo isolato ricerca
0 o più caratteri qualsiasi con esclusione del newline; in
pratica corrisponde all'intera stringa di input.
Probabilmente è più utile utilizzare il costrutto
.* come parte di una
regexp più complessa, all'interno di una sequenza in cui
il costrutto precedente e quello successivo a
.* fungono da
delimitatori.
In tal caso da delimitatori fungono i caratteri di doppi apici, ma essi possono essere qualsiasi altro carattere o perfino una qualsiasi sotto stringa selezionabile attraverso un costrutto regexp.
In tal caso da delimitatore non funge un singolo carattere, ma una sotto stringa descritta dal costrutto regexp @[1-9]@.
Quando si usano i metacaratteri di
ripetizione bisogna tenere conto del fatto che il motore
di regexp ricerca la più lunga corrispondenza possibile
partendo da sinistra.
Come base della spiegazione utilizzerò il pattern
".*", mostrando i
risultati che si ottengono con diverse stringhe
di input.
La regola della più lunga corrispondenza partendo da sinistra vale per tutti i metacaratteri di ripetizione.
Per selezionare esattamente il testo della stringa di input delimitato da uno specifico carattere, o da una specifica sotto stringa, considerando la regola della più lunga corrispondenza, dobbiamo trovare una soluzione diversa da ".*" (in tal caso il carattere che funge da delimitatore è ").
Se applichiamo tale pattern alla stringa di input
hjeksl" dasda
"sdasda"ciao"dfg, otteniamo come risultato le
sotto stringhe " dasda "
e "ciao".
La sotto stringa che funge da delimitatore deve essere
esclusa dalla ripetizione: [^delimiter]*
(delimiter rappresenta la sotto stringa che funge
da delimitazione).
Tutti e tre i tipi di metacaratteri fanno parte della categoria dei metacaratteri di ripetizione dell'elemento di base che, nel pattern, li precede.
Tutti e tre consentono di specificare un determinato numero di ripetizioni dell'elemento di base precedente; n ed m sono infatti dei numeri interi che indicano quante volte l'elemento precedente deve essere ripetuto.
Il backslash \ che precede sia la parentesi aperta che quella chiusa, serve per attribuire il significato di metacarattere di ripetizione; senza il backslah le parentesi graffe sarebbero considerate caratteri semplici che corrispondono solo a se stessi.
Il metacarattere \{n\} fa si che l'elemento di base precedente deve essere ripetuto nella stringa di input esattamente n volte, ne una di più ne una di meno.
Il metacarattere \{n,\} fa si che l'elemento di base precedente deve essere ripetuto nella stringa di input almeno n volte.
Il metacarattere \{n,m\} fa si che l'elemento di base precedente deve essere ripetuto nella stringa di input almeno n volte, ma non più di m volte.
I metacaratteri qui trattati, proprio perché consentono di rilevare ripetizioni precise di uno o più caratteri, sono utili per le ricerche in file di testo che sono costruiti come record con campi a lunghezza fissa.
I metacaratteri posizionali sono tali perché ancorano la corrispondenza con il pattern in una particolare posizione della stringa di input: se la sotto stringa descritta dal pattern esiste nella stringa di input, ma in una posizione diversa da quella specificata dal metacarattere, allora la verifica di corrispondenza in realtà fallisce.
Il metacarattere ^ ancora la corrispondenza all'inizio della stringa di input; per avere tale significato il metacarattere ^ deve essere il primo carattere del pattern.
Il metacarattere $ ancora la corrispondenza alla fine della stringa di input; per avere tale significato il metacarattere $ deve essere l'ultimo carattere del pattern.
I due metacaratteri possono essere utilizzati entrambi sullo stesso pattern; in tal caso la corrispondenza deve realizzarsi per l'intera stringa di input, nel senso che l'intera stringa di input deve realizzare una corrispondenza.
L'utilizzo di entrambi i metacaratteri è utile per ricercare righe che iniziano e finiscono con particolari sotto stringhe.
Il metacarattere \(\) serve per raggruppare porzioni della sequenza di caratteri che costituisce il pattern; la sequenza raggruppata è qualificata come sottoespressione regolare in quanto idonea a descrive solo un sottoinsieme delle stringhe che complessivamente sono riferibili con l'intero pattern.
La parte raggruppata è valutata dal motore regexp prima delle parti esterne al metacarattere \(\), cioè prima delle sequenze di caratteri non raggruppate; ciò conferisce alla porzione raggruppata il valore di autonoma espressione regolare, definita, appunto, sottoespressione regolare, proprio perché essa è una espressione regolare inclusa in una più ampia espressione regolare.
La porzione di pattern raggruppata è quella racchiusa nelle parentesi tonde. Il backslash \ che precede sia la parentesi aperta che quella chiusa, serve per attribuire a tali parentesi il valore di metacarattere di raggruppamento; senza il backslah le parentesi sarebbero considerate caratteri semplici che corrispondono solo a se stessi.
Alla sottoespressione regolare, creata con il raggruppamento, si può applicare un metacarattere di ripetizione; tale ripetizione avrà effetto non su un singolo elemento di base, ma sull'intera sequenza di caratteri corrispondente alla sottoespressione regolare medesima.
I metacaratteri trattati nelle precedenti sezioni sono
parte dello standard POSIX delle espressioni regolari di
base o BRE. Successivamente tale standard è stato
ampliato con altri metacaratteri, dando vita alle cosiddette
espressioni regolari estese o ERE.
Le cose, in realtà, sono più complicate di come sembrano, in quanto gli standard BRE ed ERE sono stati ampliati nell'ambito dei programmi sviluppati dal progetto GNU, per cui abbiamo uno standard BRE del progetto GNU e uno standard ERE del progetto GNU, entrambi più estesi rispetto ai rispettivi standard POSIX.
Mentre è certo che una espressione regolare secondo lo
standard POSIX può essere capita da un programma che supporta
lo standard GNU, del contrario non si è assolutamente
sicuri.
I metacaratteri che vedremo successivamente sono implementati
nei motori regexp che supportano ERE secondo lo standard
POSIX.
Il metacarattere + fa si che l'elemento di base che lo precede deve esistere almeno una volta, ma può essere ripetuto in sequenza anche per più volte.
Il metacarattere + in realtà non determina un vero e proprio potenziamento delle BRE, in quanto lo stesso effetto poteva essere ottenuto con il seguente costrutto BRE: \{1,\}
Il metacarattere ? fa si che l'elemento di base che lo precede possa esistere o possa non esistere, ma se esiste deve esistere non più di una volta.
Il metacarattere ? in realtà non determina un vero e proprio potenziamento delle BRE, in quanto lo stesso effetto poteva essere ottenuto con il seguente costrutto BRE: \{0,1\}
Come si può vedere è cambiata la sintassi dei metacaratteri \{n\}, \{n,\}, \{n,m\}, che perdono la barra inversa posta prima delle parentesi graffe di apertura e chiusura, diventando quindi {n}, {n,}, {n,m}. Il loro significato rimane immutato; si richiama quanto già detto in: La ripetizione delle corrispondenze.
Nelle espressioni regolari estese le parentesi graffe corrispondono a se stesse se sono precedute dalla barra inversa \.
Anche in questo caso è cambiata la sintassi del metacarattere di raggruppamento \(\), che perde la barra inversa prima delle parentesi tonde di apertura e chiusura, diventando (). Il significato del metacarattere rimane immutato; si richiama quanto già detto in: il metacarattere di raggruppamento
Nelle espressioni regolari estese le parentesi tonde corrispondono a se stesse se sono precedute dalla barra inversa \.
Il metacarattere | pone una alternativa fra due o più sottoespressioni regolari, comunque queste siano formate; è sufficiente che una sola delle sottoespressioni regolari realizzi una corrispondenza affinché tutto il costrutto delle alternative abbia esito positivo.
Affermare che è sufficiente che una solo delle sottoespressioni regolari realizzi la corrispondenza, vuol dire che tale corrispondenza deve risultare o per una sola di esse, o per entrambe.
l'alternativa è sempre posta fra la sottoespressione che sta a sinistra di | e la sottoespressione che sta a destra di |, quindi il carattere semplice c non è posto in alternativa con il solo carattere semplice b, ma piuttosto con l'intera sottoespressione regolare che sta dopo il metacarattere |, cioè con bas{1,2}[ae].
In questo caso le sottoespressioni regolari sono tre a+, b+, c+[d-z], ciascuna posta in alternativa all'altra.
Per controllare al meglio le sottoespressioni regolari da porre in alternativa è necessario raggrupparle.
Consideriamo il pattern dell'esempio precedente:
a+|b+|c+[d-z], se
l'alternativa vuol essere posta solo fra le sequenze
a+, b+ e c+ è necessario far si che le tre
sottoespressioni siano autonome da ogni altra
sottoespressione.
A tal fine ci viene in aiuto il metacarattere composto
(): racchiudendo le tre
sottoespressioni in alternativa fra parentesi (a+|b+|c+), le si rendono autonome
dalle restanti sottoespressioni che eventualmente la
precedono o la seguono.
In questo caso l'alternativa è posta fra a+, b+ e c+, mentre la sottoespressione [d-z]+ è fuori dall'alternativa e quindi essa deve necessariamente esistere dopo l'ultima sequenza che corrisponda ad una delle alternative.