Featured image

Il piano didattico del primo anno del corso di laurea triennale in Informatica, presso l’Università degli Studi di Milano, include l’insegnamento di Linguaggi formali e automi. Uno degli argomenti fondamentali è la grammatica formale, che trova applicazione nelle espressioni regolari di Unix. Sebbene ci siano numerosi materiali didattici online che catturano l’attenzione dei principianti, una risorsa imprescindibile, nonché testo di riferimento per il corso stesso, è “Introduction to Automata Theory, Languages and Computation” di Hopcroft e Ullman del 1979 (tradotto anche in italiano).

Gli articoli di questo blog dedicati alle espressioni regolari traggono ispirazione e fondamento dalle conoscenze acquisite durante il suddetto corso universitario e dalla lettura del testo citato. Queste basi teoriche, unite all’esperienza pratica dell’autore, si spera forniscano un solido punto di partenza per esplorare l’applicazione delle espressioni regolari nell’ambito dello sviluppo di programmi moderni.

Importanza delle espressioni regolari nell’Informatica Link to heading

Le espressioni regolari sono uno formalismo matematico largamente studiato e utilizzato nel campo dell’informatica e dell’ingegneria del software. La loro importanza risiede nella capacità di descrivere e manipolare i pattern all’interno di stringhe di testo. Sono fondamentali nei seguenti contesti

  • Validazione di input: verificare che i dati inseriti rispettino un determinato formato, come la validità di un indirizzo email o di un numero di telefono.

  • Ricerca e sostituzione di testo: identificare e modificare specifiche sequenze di caratteri, ad esempio per sostituire una parola in un documento.

  • Parsing di dati strutturati: estrarre informazioni da file di log, file di configurazione, o altri formati di testo.

  • Elaborazione del linguaggio naturale: individuare pattern ricorrenti, come date o nomi, all’interno di testi scritti in lingue naturali.

  • Compilatori e interpreti: riconoscere i token e i pattern sintattici nei linguaggi di programmazione.

Grazie alla loro versalità, le espressioni regolari sono uno strumento indispensabile per affrontare una varietà di problemi legati all’elaborazione di dati testuali e strutturati. La padronanza delle espressioni regolari è quindi una competenza chiave per sviluppatori e ingegneri del software.

Prima di introdurre la definizione di espressione regolare, è opportuno chiarire alcuni termini di base che aiutaranno a comprendere meglio il loro funzionamento e il loro utilizzo. Questa terminologia di base ricorrerà frequentemente negli articoli di questa serie e, talora, potrà trovare una trattazione più approfondita. Tuttavia una breve panoramica è utile per assicurare una comprensione completa.

Glossario di termini fondamentali Link to heading

  • Pattern. Un pattern è una sequenza di caratteri per denotare insiemi di stringhe (linguaggi). Nel contesto delle espressioni regolari, un pattern è la descrizione di una struttura ricorrente o un formato da riconoscere all’interno di una stringa di testo.

  • Alfabeto. Un insieme finito di simboli utilizzato per costruire stringhe. Ogni simbolo dell’alfabeto può essere un carattere che appare in una stringa.

  • Stringa. Una sequenza finita di simboli presi da un alfabeto. Le espressioni regolari operano su stringhe per verificarne la conformità a un determinato pattern.

  • Parola vuota (ε). Rappresenta la stringa che non contiene alcun simbolo, cioè una stringa di lunghezza zero.

  • Metacaratteri. Simboli con significato speciale all’interno delle espressioni regolari, utilizzati per descrivere pattern più complessi. Esempi comuni includono i caratteri *, +, ?, |, e ..

  • Letterale. Un carattere dell’alfabeto che corrisponde esattamente a sé stesso, senza avere alcun significato speciale.

  • Concatenazione. L’operazione di unione di due o più stringhe o espressioni regolari in sequenza. Ad esempio, concatenare a e b produce la stringa ab.

  • Alternanza. Un’operazione logica che permette di scegliere tra più pattern. L’operatore di alternanza è rappresentato dal metacarattere |, che corrisponde alla parola “oppure”.

  • Chiusura di Kleene. Un’operazione che ripete un pattern zero o più volte. Viene rappresentata con il metacarattere *.

Definizione di espressione regolare Link to heading

Detto in termini semplici, un’espressione regolare è una sequenza di caratteri che definisce un pattern di ricerca. Questo pattern può essere utilizzato per trovare, sostituire o validare parti di testo che corrispondono a determinati criteri.

Formalmente un’espressione regolare è definita in modo ricorsivo: si parte da espressioni semplici che costituiscono la struttura base e si costruisce l’espressione generale applicando induttivamente le operazioni di concatenazione, alternanza e chiusura di Kleene.

✏️ Una espressione regolare su un alfabeto Σ è definita ricorsivamente come segue:

  1. Base strutturale - L’insieme vuoto ∅, la parola vuota ε e ogni simbolo σ∈Σ sono espressioni regolari.

  2. Induzione strutturale - Se p e q sono espressioni regolari, allora:

    • l’unione p+q,
    • la concatenazione p∙q,
    • la chiusura di Kleene p*,

sono espressioni regolari complesse. Nient’altro è considerato una espressione regolare.

Nella definizione di espressione regolare viene utilizzata l’induzione strutturale, che consiste nel definire prima le strutture di base (le fondamenta: l’insieme vuoto, la parola vuota e il simbolo) e poi si costruiscono ricorsivamente le strutture più complesse applicando le operazioni di unione, concatenazione e chiusura di Kleene.

Un pattern non solo individua singole parole, ma anche occorenze ripetute e insiemi di parole. Per questo motivo, le espressioni regolari, sia semplici che complesse, denotano specifici linguaggi. Così, l’insieme vuoto ∅ denota il linguaggio vuoto, la parola vuota ε denota l’insieme formato dalla sola parola vuota {ε}, e il simbolo σ∈Σ denota il linguaggio contenente solo σ. Inoltre, se p e q sono espressioni regolari che denotano i rispettivamente i linguaggi Lp e Lq, allora le espressioni complesse p+q, p∙q e p* denotano l’unione di linguaggi Lp+Lq, la concatenazione di linguaggi Lp∙Lq e la stella di Kleene Lp*.

Esempi di espressioni regolari Link to heading

Gli indirizzi email sono così comuni che spesso si ha la necessità di cercarli all’interno di rubriche, appunti, testi e altri documenti. Rappresentano un esempio eccellente per illustrare l’uso delle espressioni regolari. La struttura generale di un indirizzo email è la seguente:

nome_utente@dominio.estensione.

L’espressione regolare proposta:

{a...z,A...Z}*∙@∙{a...z,A...Z}*∙.∙{a...z,A...Z}*

Questa espressione cattura l’idea generale, utilizzando la chiusura di Kleene e l’operatore di concatenazione, ma presenta alcune limitazioni:

  • Non include numeri, che sono comuni negli indirizzi email.

  • Non considera caratteri speciali, come ., _, - nel nome utente.

  • Non limita la lunghezza dell’estensione del dominio.

  • Usa la virgola per separare i range e le parentesi graffe per i gruppi, il che non corrisponde alla sintassi corretta delle espressioni regolari.

  • L’uso della chiusura di Kleene comporta l’accettazione di indirizzi senza nome utente, dominio ed estensione, risultando nella stringa @., che è invalida.

Una versione migliorata potrebbe essere:

[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}.

Analisi dell’espressione

  • [a-zA-Z0-9._%+-]+: Questo pattern rappresenta il linguaggio costituito da uno o più caratteri alfanumerici o dai caratteri speciali ., _, %, +, -, che sono tipicamente permessi nel nome utente di un indirizzo email.

  • @: è il simbolo @ che separa il nome utente dal dominio.

  • [a-zA-Z0-9.-]+: rappresenta il linguaggio formato da uno o più caratteri alfanumerici, punti o trattini, usati comunemente per il nome dei domini.

  • \.: Un metacarattere che rappresentare il punto letterale, per separare il dominio dall’estensione.

  • [a-zA-Z]{2,}: Rappresenta due o più caratteri alfabetici per l’estensione del dominio, assicurando una lunghezza minima.

Questa espressione è più accurata, ma è importante notare che una validazione completa degli indirizzi email secondo tutti gli standard RFC è estremamente complessa e spesso non necessaria per la maggior parte delle applicazioni pratiche.

Il pacchetto regexp Link to heading

Il pacchetto regexp è una libreria standard in Go che offre supporto per lavorare con le espressioni regolari, permettendo di cercare, confrontare e manipolarie stringhe secondo un determinato pattern. Il formato utilizzato è simile a quello comunemente adottato nelle espressioni regolari POSIX e Perl, con caratteristiche familiari come il punto (.), l’asterisco (*), il simbolo più (+), le parentesi quadre ([]) per definire gruppi, e molti altri metacaratteri.

Le funzioni principali di questo pacchetto sono le seguenti:

  • regexp.Compile(pattern string) (*Regexp, error). Compila il pattern specificato in un oggetto Regexp (una struttura). Restituisce un errore se l’espressione è invalida.

  • regexp.MustCompile(pattern string) *Regexp. Funziona come Compile, ma provoca un panic se il pattern non è valido. È utile quando si è certi che il pattern sia corretto e si desidera evitare la gestione esplicita degli errori di Go.

I metodi più comuni sono:

  • MatchString(s string) bool. Verifica se una stringa corrisponde al pattern dell’espressione regolare.

  • FindString(s string) string. Cerca la prima sottostringa che corrisponde al pattern e la restituisce.

  • FindAllString(s string, n int) []string. Restituisce tutte le sottostringhe che corrispondono al pattern. L’intero n specifica il numero massimo di occorrenze da restituire (con -1 per tutte).

  • ReplaceAllString(src, repl string) string. Sostituisce tutte le occorrenze che corrispondono al pattern con la stringa repl.

  • Split(s string, n int) []string. Divide la stringa in un massimo di n segmenti in base al pattern.

Il pacchetto regexp in Go è progettato per essere efficiente e supporta molte funzionalità delle espressioni regolari, ma non tutte le caratteristiche avanzate disponibili in altri linguaggi, come le lookahead o lookbehind assertions.

Esempio di codice con Golang Link to heading

Il seguente programma, scritto in Go, utilizza le espressioni regolari per validare una lista di indirizzi email. La regex definita verifica se gli indirizzi soddisfano una struttura comune, consentendo l’uso di caratteri alfanumerici, simboli speciali, un segno @ che separa il nome utente dal dominio, e infine una corretta estensione del dominio. Infine, il programma stampa un messaggio indicando se ogni indirizzo email è valido o meno.

    package main

    import (
        // Importa il pacchetto fmt per l'output formattato
        "fmt"
        // Importa il pacchetto regexp per lavorare con le espressioni regolari
        "regexp"
    )

    func main() {
        // Definisce un'espressione regolare per gli indirizzi email utilizzando
        // la funzione MustCompile
        emailRegex := regexp.MustCompile(`[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}`)

        // Crea una lista di indirizzi email di esempio da verificare
        testEmails := []string{
            "user@example.com",        // Email valida
            "user.name+tag@example.co.uk", // Email valida con simboli e dominio a più livelli
            "invalid.email@com",       // Email invalida (estensione di dominio troppo corta)
            "12345@domain.io",         // Email valida composta da numeri
            "adamdomain.io",               // Email invalida: manca @
            "@adam@adam.io",               // Sebbene invalida, viene accettata            
        }

        // Itera attraverso la lista di indirizzi email
        for _, email := range testEmails {
            // Verifica se l'email corrisponde all'espressione regolare
            if emailRegex.MatchString(email) {
                // Stampa se l'indirizzo email è valido
                fmt.Printf("%s è un indirizzo email valido\n", email)
            } else {
                // Stampa se l'indirizzo email non è valido
                fmt.Printf("%s non è un indirizzo email valido\n", email)
            }
        }
    }

Conclusioni Link to heading

Le espressioni regolari rappresentano un elemento fondamentale nell’informatica moderna, con applicazioni che spaziano dalla validazione di input alla manipolazione e ricerca di testo. Radicate nella teoria dei linguaggi formali, le regex offrono un potente strumento per descrivere e identificare pattern complessi all’interno di stringhe, rendendole estremamente versatili. L’articolo ha esplorato la definizione formale delle espressioni regolari, presentando concetti chiave come alfabeti, metacaratteri e le operazioni fondamentali di unione, concatenazione e chiusura di Kleene. Attraverso un esempio pratico, quale la validazione di indirizzi email, si è illustrato come le regex possano essere applicate a problemi reali per affrontare situazioni comuni in modo efficiente. Inoltre, l’introduzione al pacchetto regexp di Go, insieme a un esempio di codice concreto, ha mostrato come implementare e utilizzare le espressioni regolari in un contesto di programmazione, sottolineando l’importanza di questa competenza per gli sviluppatori e il suo ruolo nella risoluzione di sfide quotidiane.

Licenza GNU FDL