Quindicesima lezione

Cambiamo ora completamente argomento, e passiamo ad analizzare alcuni temi un poco più specialistici, che però ritornano spessissimo nella pratica della programmazione.

Per esempio, nell'uso che abbiamo fatto delle funzioni di trattamento di stringhe del C, è possibile che qualcuno abbia notato una certa maggiore complicazione, rispetto per esempio al Fortran (dove però sono completamente assenti i concetti di puntatori, di allocazione dinamica della memoria, e dunque di stringhe che cambiano dimensione en route).
Si può essere d'accordo con questa affermazione, ma non bisogna dimenticare che in compenso la libreria standard C permette di accedere ad alcune librerie di trattamento delle stringhe che affrontano il problema in modo decisamente più moderno.

Uno dei problemi che spesso si presentano nella scrittura dei programmi è quello del confronto di stringhe. Può essere ad esempio necessario controllare il contenuto degli argomenti ricevuti dall'utente, oppure letti da un file. E' buono stile di programmazione che questi controlli siano fatti nel modo più robusto (il programma non deve impazzire se riceve qualcosa di strano) e tollerante (il programma deve sapere accettare anche forme diverse, ma simili dello stesso argomento) possibile.
Elaborare stringhe in C con questi criteri può essere assai tedioso, oltre che incline ad errori. Esiste tuttavia un potente algoritmo simbolico, il cui uso sta diventando sempre più standard, che permette di rappresentare intere famiglie di stringhe, semplificando dunque il confronto. Si tratta delle cosiddette regular expressions, che passiamo ora a descrivere con la dovuta attenzione.

Alcune considerazioni generali:

• Il termine espressione regolare è stato coniato nei primi anni '50 dal matematico Stephen Kleene, nel corso dello sviluppo della teoria formale dei linguaggi (vengono definite come metodi per esprimere la concatenazione di elementi di un linguaggio).
• Nell'accezione pratica le espressioni regolari sono un potente linguaggio simbolico che permette di rappresentare le caratteristiche di una stringa o di un insieme di stringhe.
• L'uso delle R.E. facilita la scrittura di qualunque applicazione nella quale sia necessario analizzare stringhe.
• Solitamente nessuno si pente di aver superato la barriera di apprendimento iniziale delle R.E.
• Qualunque utente di Dos o Unix ha già usato una forma di R.E.:

  > dir *.exe

• Esistono strumenti, disponibili quasi universalmente (e accennati nel seguito), che sfruttano al meglio le potenzialità delle R.E..

• L'occorrenza (match) di una R.E. in una stringa si verifica se tutti gli elementi della R.E. sono stati "trovati", nella posizione e sequenza indicata.
• Se nella R.E. è presente un carattere non speciale (si trova più avanti un elenco dei caratteri speciali), nella stringa analizzata deve essere presente lo stesso carattere.
  Esempio nella pratica notazione di Perl, che è uno dei più potenti e diffusi linguaggi di scripting, al quale accenneremo brevemente più avanti.

  "La Vispa Teresa" =~ /Vispa/

• Più caratteri o elementi possono essere raggruppati in parentesi tonde: questo rende possibile riutilizzarli in seguito, anche nella stessa espressione (backreference).

  "gridava, gridava: l'ho presa l'ho presa" =~
  /(gridava), \1: (l'ho presa) \2/

• Il carattere . (punto) nella R.E. viene soddisfatto da qualunque carattere nella stringa originale.

  "La Vispa Teresa" =~ /Vi..a T....a/

• Si può richiedere il valore letterale di un qualunque carattere speciale (+?.*^$(){}|\) precedendolo con \.

  "La Vispa Teresa?" =~ /Teresa\?/

• La richiesta di un carattere o di un'espressione fra parentesi può essere "moltiplicata" con l'uso di quantificatori.
• * Richiede che il carattere (o l'espressione fra parentesi) che precede sia ripetuta zero o più volte. L'equivalente della wildcard alla quale gli utenti di qualsiasi sistema operativo sono abituati è .*

  "La Vispa Teresa" =~ /La.*Teresa/

• + Richiede che il carattere (o l'espressione fra parentesi) che precede sia ripetuta una o più volte.

  "avea tra l'erbetta" =~ /erbet+a/

• ? Richiede che il carattere (o l'espressione fra parentesi) che precede sia ripetuta zero o una volta.

  "La 'Vispa Teresa'" =~ /La '?Vispa/ =~ "La Vispa Teresa"

• {M,N} Richiede che il carattere (o l'espressione fra parentesi) che precede sia ripetuta un minimo di M ed un massimo di N volte.
• Attenzione: questi quantificatori "consumano" quanti più caratteri possibili nella stringa originale (greedy matching).

• La R.E. si può anche "ancorare" ad un punto preciso della stringa alla quale viene confrontata:
• ^ Richiede che l'inizio della stringa si trovi nella posizione indicata.

  /^La Vispa/ =~ "La Vispa Teresa" !~ /^Vispa/

• $ Richiede che la fine della stringa si trovi nella posizione indicata.

  /Teresa$/ =~ "La Vispa Teresa" !~ /Vispa$/

• Anziché richiedere un carattere preciso, si può richiedere che un carattere della stringa originale sia compreso in un gruppo o una serie di caratteri con [caratteri].

  /V[ispa]{4,4} T[ersa]{5,5}/ =~
  "La Vispa Teresa" =~
  /La V[A-Za-z]{4,4} T[A-Za-z]{5,5}/

• Oppure si può chiedere che NON compaia un gruppo od una serie di caratteri con [^caratteri].

  /V[^jkwxy]+ T[^jkwxy]+/ =~
  "La Vispa Teresa" =~ /[^ ]+ Teresa/
  =~ "La Furba Teresa"

• Si può anche utilizzare il simbolo | (alternatore), assieme alle parentesi, per realizzare una funzione di OR logico:

  "La Vispa Teresa" =~
  /(Vispa|Furba) Teresa/ =~
  "La Furba Teresa"

• Ci sono poi metodi più astuti (ma non universali) per rappresentare un gruppo di caratteri. Ecco cosa offre Perl, il noto linguaggio di scripting:

Ecco un breve estratto della guida pratica di Perl, con indicate le parti che sono specifiche di Perl:

La libreria standard POSIX di R.E. è accessibile attraverso tre chiamate:

#include <regex.h>

• int regcomp(regex_t *preg, const char *regex, int cflags); viene utilizzata per compilare la R.E. in un formato che faciliti poi le operazioni di confronto. La struttura che contiene le informazioni ricavate dalla compilazione, di tipo regex_t, deve essere passata alla funzione. cflags è la combinazione in OR di alcuni parametri che determinano la funzionalità del confronto. Di solito si usa sempre REG_EXTENDED, che seleziona le funzioni estese (vedi sopra), e si può aggiungere REG_ICASE se il confronto non deve distinguere fra maiuscole e minuscole, e/o REG_NOSUB, se si desidera che non vengano identificate le posizioni della stringa dove si verifica l'occorrenza della R.E.
• int regexec(const regex_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags); esegue fisicamente il confronto della stringa string con la R.E. pre-compilata in preg. eflags non è tipicamente necessario, e può essere lasciato a zero. Se non è stato utilizzato in compilazione il flag REG_NOSUB, è possibile passare alla funzione un array di strutture di tipo regmatch_t di dimensione nmatch che conterrà le posizioni delle occorrenze trovate. Questa la definizione di regmatch_t, la struttura che contiene la posizione iniziale e finale (+1) delle occorrenze trovate sia per l'intera R.E. (pmatch[0]) che per le parti di R.E. delimitate da parentesi tonde (negli elementi successivi di pmatch):

  typedef struct
   {
    regoff_t rm_so;
    regoff_t rm_eo;
   } regmatch_t;
  

  La funzione restituisce zero se il match ha successo, altrimenti REG_NOMATCH.
• void regfree(regex_t *preg); La struttura preg è stata collegata durante la compilazione a strutture dati allocate dinamicamente: non bisogna dimenticarsi di rilasciarle con questa chiamata quando non sono più necessarie.

Questo prova a convertire in un numero da 1 a 12 il nome di un mese, scritto in italiano, inglese, francese o tedesco.

Esercizio: Provare a scrivere un programma che interpreta una data completa utilizzando una R.E.