View Full Version : [C/C++] Espressioni regolari
ciao,
sto sviluppando un progetto che tira in ballo l'acquisizione di alcuni dati da file; questi però devono essere formati in un certo modo come ad esempio potrebbe essero un indirizzo IP 192.168.1.100 oppure dati in ingresso del tipo A0.3, B10.5 e così via.
Come effettuo un controllo del genere?
Mi sonon venute in mente le espressioni regolari ma non so nulla a riguardo.
grazie
ciao,
sto sviluppando un progetto che tira in ballo l'acquisizione di alcuni dati da file; questi però devono essere formati in un certo modo come ad esempio potrebbe essero un indirizzo IP 192.168.1.100 oppure dati in ingresso del tipo A0.3, B10.5 e così via.
Come effettuo un controllo del genere?
Mi sonon venute in mente le espressioni regolari ma non so nulla a riguardo.
grazie
Il formato del file è semplice testo?
I dati possono cambiare, ma il formato è comune?
Ad esempio, se usi un formato CSV:
file
1, nome, cognome, telefono
2, nome, cognome, telefono
..
A questo punto potresti usare un file per definire i vari campi (ad esempio uno su ogni linea):
integer
text(30)
text(30)
text(12)
All'avvio del tuo programma leggi il file di configurazione e configuri il programma opportunamente: così facendo conosci il numero di campi, quindi sai già cosa e quanto devi leggere.
Dunque se il formato è comune puoi creare una piccola applicazione in cui passi eventualmente dall'esterno cosa rappresentano quei dati.
ciao,
è un comune file ASCII ma ad esempio un utente potrebbe scrivere erroneamente un indirizzo IP errato
I92.168.1.298
Quindi, una I in luodo di 1 e un valore 298 che fuoriesce dal campo di indirizzamento degli indirizzi IP
Le espressioi regolari mi sembravano una valida soluzione in quanto stabilita una regola poi deve essere verificata.
Sto usando Borland C++ Builder e pensavo che fossero implementate.
ciao,
è un comune file ASCII ma ad esempio un utente potrebbe scrivere erroneamente un indirizzo IP errato
I92.168.1.298
Quindi, una I in luodo di 1 e un valore 298 che fuoriesce dal campo di indirizzamento degli indirizzi IP
Le espressioi regolari mi sembravano una valida soluzione in quanto stabilita una regola poi deve essere verificata.
Sto usando Borland C++ Builder e pensavo che fossero implementate.
Credo che l'espressione regolare per fare questo controllo sia un po' lunga...
Secondo me se sai che sono indirizzi IP ti conviene dividere la stringa in tokens (separati da punto), convertire in numero e controllare che siano nel range corretto.
Credo che l'espressione regolare per fare questo controllo sia un po' lunga...
Secondo me se sai che sono indirizzi IP ti conviene dividere la stringa in tokens (separati da punto), convertire in numero e controllare che siano nel range corretto.
sarebbe interessante vedere sviluppato in C un automa a stati finit per il riconoscimento di quella espressioe regolare.
Non ne ho la più pallida idea di come vengono sviluppati
sarebbe interessante vedere sviluppato in C un automa a stati finit per il riconoscimento di quella espressioe regolare.
Non ne ho la più pallida idea di come vengono sviluppati
Prova a svilupparlo su carta l'automa, ti accorgerai presto che è un po' un casino perché devi tenere conto di molte cose (se vuoi fare una cosa fatta bene).
Ad esempio devi gestire cosa accade se leggi un 2 come prima cifra di un gruppo:
Inizio con 2 -> leggo un numero compreso tra 0..4 -> dopo posso leggere 0..9
Inizio con 2 -> leggo 5 -> dopo posso leggere 0..5
Inizio con 2 -> leggo un numero compreso tra 6..9 -> dopo devo per forza leggere un punto
Devi tenere conto che non puoi iniziare una sequenza con uno 0, ovvero, se leggi uno 0 all'inizio devi per forza di cose leggere un punto.
Se ho fatto bene i conti hai almeno 8 stati diversi.
Prova a svilupparlo su carta l'automa, ti accorgerai presto che è un po' un casino perché devi tenere conto di molte cose (se vuoi fare una cosa fatta bene).
Ad esempio devi gestire cosa accade se leggi un 2 come prima cifra di un gruppo:
Inizio con 2 -> leggo un numero compreso tra 0..4 -> dopo posso leggere 0..9
Inizio con 2 -> leggo 5 -> dopo posso leggere 0..5
Inizio con 2 -> leggo un numero compreso tra 6..9 -> dopo devo per forza leggere un punto
Devi tenere conto che non puoi iniziare una sequenza con uno 0, ovvero, se leggi uno 0 all'inizio devi per forza di cose leggere un punto.
Se ho fatto bene i conti hai almeno 8 stati diversi.
però è molto interessante :)
Ma verrebbe una serie di:
if(carattere == numero) allora accetta e
cifre++; // incrementa il contatore delle cifre lette
if(carattere == '.' AND cifre == 0) allora NON accetta
if(carattere == '.' AND cifre >= 1) allora accetta
e così via
Se ti serve una regex per validare un indirizzo ip puoi usare questa:
\b([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\b
Per usarle in un programma c dovrebbe bastare usare pcre come libreria.
però è molto interessante :)
Ma verrebbe una serie di:
if(carattere == numero) allora accetta e
cifre++; // incrementa il contatore delle cifre lette
if(carattere == '.' AND cifre == 0) allora NON accetta
if(carattere == '.' AND cifre >= 1) allora accetta
e così via
Si può fare in molti modi, ma io non lo farei con una catena di IF secca.
Preferisco una soluzione più elegante, ad esempio usando una struttura del tipo:
typedef struct _stato
{
struct _stato* Next[255]; /* tabella di transizione: 255 caratteri possibili */
} stato;
stato Stato[10];
void InitStati( )
{
/* inizializza tutti i Next[i] a NULL (si può anche inizializzare ad uno stato dummy) */
/* inizializza stati */
/* ESEMPIO */
Stato[0].Next['c'] = &( Stato[1] );
}
bool Parse( string Input )
{
stato* Current = &( Stato[0] ); /* Stato iniziale */
for (char Ch in Input)
{
Current = Current->Next[Ch];
if ( Current == NULL )
return false; /* si può evitare questo if usando uno stato dummy */
}
return ( Current == &( Stato[1] ) ); /* se sono nello stato finale (1) ritorna true */
}
In pratica il principio è, leggo un carattere, in base allo stato corrente vado allo stato successivo, se lo stato successivo è nullo vuol dire che hai inserito un carattere non ammesso (o per cui non esiste una transizione).
Il tutto senza catene di IF orrende :D.
Certamente consumi più memoria, in quanto ogni stato ha un array di 255 puntatori (se vuoi contemplare tutti i possibili input ASCII).
Volendo essere più puristi puoi usare uno stato dummy (che ovviamente non può essere finale) che cicla su se stesso qualunque sia il carattere in input.
La differenza in questo caso è che la funzione Parse non termina subito se trova un carattere non valido, ma si legge tutta l'intera stringa.
Una soluzione analoga potrebbe essere quella di usare una matrice con gli indici degli stati.
Se all'interno dello stato devi fare molte cose, potrebbe essere conveniente fare diverse funzioni per ciascuno degli stati, e usare i puntatori a funzione per eseguire di volta in volta lo stato corrente (ergo la funzione specifica dello stato corrente).
Sicuramente quest'ultima soluzione rende di gran lunga più leggibile il codice, piuttosto che usare una lunga sfilza di if-else o di switch-case.
peccato aver visto solo a livello teorico gli automi. La tua tesi si basava sugli automi a stati ? :D
parlando in termini di open source non sarebbe male se gli utenti postassero codice perfettamente funzionante da mettere a disposizione per chi programma, una cosa del tipo:
verifica dell'indirizzo IP dato come input - ambiente Borland C++ Builder
void __fastcall TForm1::Button1Click(TObject *Sender)
{
char *token;
char *line = "192.168.0.32";
char *search = ".";
short nm=0;
token = strtok(line, search);
if(StrToInt(token) >= 0 && StrToInt(token) <= 255)
{
Memo1->Lines->Add(token);
nm++;
}
else
{
Memo1->Lines->Add("ERRORE");
Memo1->Lines->Add(token);
nm++;
}
while( (token = strtok(NULL, search)) != NULL)
{
if(StrToInt(token) >= 0 && StrToInt(token) <= 255)
{
Memo1->Lines->Add(token);
nm++;
}
else
{
Memo1->Lines->Add("ERRORE");
Memo1->Lines->Add(token);
nm++;
}
}
if(nm < 4 || nm > 4) Memo1->Lines->Add("Formato indirizzo IP errato!!!");
}
banryu79
22-11-2011, 08:02
Quella funzione però non fa i controlli che ha indicato WarDuck nel messaggio #6...
@EDIT:
prova ad inserire indirizzi IP a caso
aa.123455.78989.1
500.3.12.90
192.168.90,12
Mica c'ho un compilatore Pascal... come la provo? E comunque basta leggere il codice del corpo della funzione per capire che non fa quei controlli. Quella funzione controlla solo che l'IP sia formato esattamente da 4 campi separati da '.', ognuno formato da un numero intero compreso tra 0 e 255 inclusi.
Ripeto: non fa i controlli che ha indicato WarDuck nel messaggio #6...
Quella funzione però non fa i controlli che ha indicato WarDuck nel messaggio #6...
prova ad inserire indirizzi IP a caso
aa.123455.78989.1
500.3.12.90
192.168.90,12
ESSE-EFFE
22-11-2011, 09:55
Per validare l'indirizzo IP non serve scomodare le espressioni regolari, basta sfruttare qualche funzione Win32, per esempio:
char *line = "192.168.0.32";
if (inet_addr(line) == INADDR_NONE)
{
// IP errato
}
else
{
// IP OK
}
Gli altri possibili input mi sembrano comunque semplici da parsare.
Per validare l'indirizzo IP non serve scomodare le espressioni regolari, basta sfruttare qualche funzione Win32, per esempio:
char *line = "192.168.0.32";
if (inet_addr(line) == INADDR_NONE)
{
// IP errato
}
else
{
// IP OK
}
Gli altri possibili input mi sembrano comunque semplici da parsare.
interessante.
Però quello dell'IP era solo la punta dell'icberg. Devo controllare anche dati del tipo
A10.7, SL170
P10.7, PB20 etc...
ESSE-EFFE
22-11-2011, 10:07
Devo controllare anche dati del tipo
A10.7, SL170
P10.7, PB20 etc...
Sì, ho letto, ma come ho già scritto, questi sono formati piuttosto semplici da parsare. Se poi ce ne sono anche di più complicati per cui tanto vale usare le RegEx per tutto, io questo non lo so...
Sì, ho letto, ma come ho già scritto, questi sono formati piuttosto semplici da parsare. Se poi ce ne sono anche di più complicati per cui tanto vale usare le RegEx per tutto, io questo non lo so...
si, in effetti ne ho molti di più e di diverso formato, per tale motivo ho pensato alle espressioni regolari
Se ti serve una regex per validare un indirizzo ip puoi usare questa:
\b([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\b
Per usarle in un programma c dovrebbe bastare usare pcre come libreria.
di quella espressione regolare sarebbe interessante capire come viene caricata in memoria per poi venire usata
In genere l'alternanza è ordinata quindi esegue i test nell'ordine in cui sono scritti. Non fa alto che cercare questo (0-199|200-249|250-255) ripetuto 4 volte.
In genere l'alternanza è ordinata quindi esegue i test nell'ordine in cui sono scritti. Non fa alto che cercare questo (0-199|200-249|250-255) ripetuto 4 volte.
la formattazione di espressioni regolari di quel tipo sono stabilite dallo standard POSIX o altro standard?
E' da un pò che cerco ma le informazioni sono abbastanza confuse, forse cerco nei posti sbagliati.
Poi stranamenete non trovo codice C già pronto da studiare che legga quelle espressioni.
C'è uno standard posix che specifica sintassi e quali risultati devono essere trovati ma non ti saprei dire se ci sia qualche libreria che lo implementa. Alla fine, un po' come per sql, ci sono vari dialetti ed ognuno fa un po' come gli pare.
Se ti interessa studiare veramente le regex non posso che consigliarti Mastering Regular Expression. La prima metà del libro spiega fin nei minimi dettagli sintassi, le differenze tra dfa/nfa per arrivare ai singoli passi di come viene eseguita la ricerca. Il resto parla delle implementazioni in vari linguaggi e può non interessare.
grazie per la dritta. Sto leggendo il libro da te citato su google libri.
Scusate se mi intrometto,
è vero che le espressioni regolari sono potentissime, però IMVHO rendono il codice abbastanza complesso.
A meno che non si abbia una grande dimestichezza con le RE :cool:
Se non sono espressioni semplici, preferisco utilizzare un po' più di codice C ma decisamente più esplicativo.
sempre IMHO, ovviamente :)
concordo con quello che dici, ma essendo arrivata l'occasione qualla buona meglio approfondire :)
OT: Sapete se il comando GREP di unix permette di fare esoperimenti con le espressioni regolari?
concordo con quello che dici, ma essendo arrivata l'occasione qualla buona meglio approfondire :)
OT: Sapete se il comando GREP di unix permette di fare esoperimenti con le espressioni regolari?
Approfondire fa sempre bene :)
OT: SI
Scusate se mi intrometto,
è vero che le espressioni regolari sono potentissime, però IMVHO rendono il codice abbastanza complesso.
A meno che non si abbia una grande dimestichezza con le RE :cool:
Se non sono espressioni semplici, preferisco utilizzare un po' più di codice C ma decisamente più esplicativo.
sempre IMHO, ovviamente :)
Non sono d'accordo. Trovo che sia molto più facile avere a che fare con una singola espressione regolare, anche se complessa, che magari 400 righe di codice c divise in 20 funzioni che si chiamano a vicenda tra di loro. Si fa molto prima ed in linguaggi come il c in cui non c'è un tipo di dato string nativo è anche più sicuro. Se il pattern non è banale è facilissimo scordarsi un controllo ed uscire dal buffer, entrare in un ciclo infinito ecc.
Non sono d'accordo. Trovo che sia molto più facile avere a che fare con una singola espressione regolare, anche se complessa, che magari 400 righe di codice c divise in 20 funzioni che si chiamano a vicenda tra di loro. Si fa molto prima ed in linguaggi come il c in cui non c'è un tipo di dato string nativo è anche più sicuro. Se il pattern non è banale è facilissimo scordarsi un controllo ed uscire dal buffer, entrare in un ciclo infinito ecc.
SNIO, si e no :)
per quello ho sottolineato IMHO.
le ho usate spesso in PHP per controllare valori di campi, però in altre situazioni preferisco un po' di codice.
Certo nel caso che accenni, dove una RE viene sostituita da 400 righe e 20 funzioni intrecciate, vale la pena considerare l'utilizzo (e spesso lo studio :D ) delle RE.
C'è uno standard posix che specifica sintassi e quali risultati devono essere trovati ma non ti saprei dire se ci sia qualche libreria che lo implementa. Alla fine, un po' come per sql, ci sono vari dialetti ed ognuno fa un po' come gli pare.
Lo standard de facto per le regex e' quello di Perl, non a caso la libreria (PCRE) che hai indicato si chiama Perl Compatible Regular Expression.
goldorak
24-11-2011, 21:09
Lo standard de facto per le regex e' quello di Perl, non a caso la libreria (PCRE) che hai indicato si chiama Perl Compatible Regular Expression.
No nel modo piu' assoluto. Perl, Python e Ruby hanno implementazioni delle espressioni regolari molto scadenti dal punto di vista prestazionale oltre a presentare diversi casi "limiti" che portano a tempi di esecuzione esponenziale.
Se uno vuole imparare le espressioni regolari e come implementarle correttamente si deve partire dalla teoria degli automi a stati finiti (deterministici o non deterministici). E il punto di partenza (per il programmatore) e' l'articolo di Ken Thompson intitolato "Regular Expression Search Algorithm" in cui descrive come compilare una espressione regolare in codice macchina (per un mainframe IBM 7094). L'articolo e' vecchio, pubblicato nel 1968 ma contiene le idee giuste. Poi oggi nessuno compila piu' le regex in codice macchina, ma si compila o per una NDFA simulandone l'esecuzione, oppure si compila direttamente in una DFA oppure si costruisce una NDFA e poi la si converte in una DFA. Ci sono anche implementazioni che compilano direttamente su una VM.
Le migliori implementazioni di regex (che si basano appunto sulla costruzione di Thompson) non hanno input patologici e sono 1 milioni di volte piu' veloci delle implementazioni di Ruby, Python e Perl.
No nel modo piu' assoluto. Perl, Python e Ruby hanno implementazioni delle espressioni regolari molto scadenti dal punto di vista prestazionale oltre a presentare diversi casi "limiti" che portano a tempi di esecuzione esponenziale.
Se uno vuole imparare le espressioni regolari e come implementarle correttamente si deve partire dalla teoria degli automi a stati finiti (deterministici o non deterministici). E il punto di partenza (per il programmatore) e' l'articolo di Ken Thompson intitolato "Regular Expression Search Algorithm" in cui descrive come compilare una espressione regolare in codice macchina (per un mainframe IBM 7094). L'articolo e' vecchio, pubblicato nel 1968 ma contiene le idee giuste. Poi oggi nessuno compila piu' le regex in codice macchina, ma si compila o per una NDFA simulandone l'esecuzione, oppure si compila direttamente in una DFA oppure si costruisce una NDFA e poi la si converte in una DFA. Ci sono anche implementazioni che compilano direttamente su una VM.
Le migliori implementazioni di regex (che si basano appunto sulla costruzione di Thompson) non hanno input patologici e sono 1 milioni di volte piu' veloci delle implementazioni di Ruby, Python e Perl.
Io non ho parlato ne' di performance ne' di implementazioni. Ho parlato di API (intesa come possibili modi per rappresentare una regex).
No nel modo piu' assoluto. Perl, Python e Ruby hanno implementazioni delle espressioni regolari molto scadenti dal punto di vista prestazionale oltre a presentare diversi casi "limiti" che portano a tempi di esecuzione esponenziale.
Se uno vuole imparare le espressioni regolari e come implementarle correttamente si deve partire dalla teoria degli automi a stati finiti (deterministici o non deterministici). E il punto di partenza (per il programmatore) e' l'articolo di Ken Thompson intitolato "Regular Expression Search Algorithm" in cui descrive come compilare una espressione regolare in codice macchina (per un mainframe IBM 7094). L'articolo e' vecchio, pubblicato nel 1968 ma contiene le idee giuste. Poi oggi nessuno compila piu' le regex in codice macchina, ma si compila o per una NDFA simulandone l'esecuzione, oppure si compila direttamente in una DFA oppure si costruisce una NDFA e poi la si converte in una DFA. Ci sono anche implementazioni che compilano direttamente su una VM.
Le migliori implementazioni di regex (che si basano appunto sulla costruzione di Thompson) non hanno input patologici e sono 1 milioni di volte piu' veloci delle implementazioni di Ruby, Python e Perl.
Tutti quanti compilano le regex e si creano degli nfa. In linguaggi come perl o ruby non lo vedi perché sono tipi di dati base del linguaggio ma viene fatto comunque. Pcre non è la libreria più potente o la più veloce ma nel 99.999% dei casi fa quello che deve fare e va veloce come tutte le altre.
Il problema con certi input è una idiosincrasia degli nfa. Anche l'implementazione di Thompson mi pare di ricordare fosse un nfa e ne soffriva. Non c'è modo di risolverla. Gli unici a non esplodere quando si usano impropriamente "*" e "+" assieme sono i dfa puri ma sono incredibilmente limitati come possibilità. Già qualcosa di banale come "(\w+) \1" è impossibile da implementare con quel tipo di sistema.
ciao VICIUS,
però partendo dal presupposto che io il corso di LFA l'ho seguito e passato l'esame, mi ritrovo a terra per quanto riguarda l'implementazione in un qualsiasi linguaggio. Forse in altri corsi era previsto anche laboratorio ma da me ahimè no. Sono daccordo di ripartire dal libro da te citato.
ciao VICIUS,
però partendo dal presupposto che io il corso di LFA l'ho seguito e passato l'esame, mi ritrovo a terra per quanto riguarda l'implementazione in un qualsiasi linguaggio. Forse in altri corsi era previsto anche laboratorio ma da me ahimè no. Sono daccordo di ripartire dal libro da te citato.
Mah sai, se sai bene la teoria, l'implementazione potrebbe richiedere solo un po' di fantasia, anche perché in informatica ci sono molti modi per fare una determinata cosa (tipicamente).
E' vero anche che ci sono casi in cui è consigliabile utilizzare una soluzione collaudata per risolvere un dato problema.
Comunque la base teorica per quanto concerne automi e linguaggi è molto importante, se è stata fatta bene.
Dove mi sono laureato io il corso di automi linguaggi e traduttori è stato uno dei più difficili in assoluto, perché l'esame richiedeva di trovare oltre che le soluzioni ai problemi, di dimostrarne la validità, cosa quest'ultima che non ci ha insegnato nessuno a fare.
D'altro canto ti basti pensare che come progetto associato al corso ci è stato chiesto di realizzare 2 parser, un Cook-Younger-Kasami e un LR1.
Relativamente a quest'ultimo non è banale comprendere il perché funziona (ancora oggi non l'ho capito molto bene), ma il Dragon Book ti spiega passo passo come fare ad implementarlo (è abbastanza meccanico come procedimento).
Relativamente alle espressioni regolari, l'impressione che ho è che probabilmente allo stato attuale sono più potenti di quanto concesso dalla teoria (nel senso che mi sembrano fare più cose), ma non ho approfondito bene il discorso (anche se so passare da un DFA ad una espressione regolare e viceversa).
Ma ad esempio non riesco ad immaginare come si possa implementare un automa puramente non deterministico (NFA), e se è questo quello che fanno i vari linguaggi.
Saper implementare delle cose è sicuramente positivo, ma sapere perché funzionano non ha prezzo e secondo me è molto più importante:D.
ciao,
il mio è stato un esame fondamentale da 6 crediti, pensa che prima era un complementare ma è stato portato avanti come un complementare. Però le cose le dovevi sapere, contrariamente il docente ti mandava a casa.
Io avrei associato al corso teorico anche qualcosa di più pratico, lo sviluppo di un piccolo automa che riconoscesse un linguaggio e magari, dato un linguaggio costruisse l'espressione regolare che lo rappresenta.
Resta comunque una materia affascinante
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.