[C] espressioni regolari

[Zebra75]

Le espressioni regolari mi pare di aver capito, che sono il modello di stringa che ci aspettiamo in input e il pattern mostrato nel codice, dovrebbe esserne un esempio. Come dovrebbe essere la parte relativa di codice che effettua la verifica di quanto digitato dall'utente ?
Sarebbe il parser ?

char *pattern = "/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/";

[Zebra75]

ma ho fatto una domanda così strana oppure sarebbe troppo onerosa in termini di tempo una risposta ?

[wizard1993]

io ti dirò la verità quello mi sembra tutto tranne c, semmi quello e js

[Zebra75]

Originariamente inviato da wizard1993

io ti dirò la verità quello mi sembra tutto tranne c, semmi quello e js

ed hai ragione, ma lo avevo anche scritto che lo scorcio di programma era in javascript!
Siccome mi interessava incollare un pattern già fatto su cui discutere, quello che ho trovato è stato quello.

[mjordan]

Originariamente inviato da Zebra75

ma ho fatto una domanda così strana oppure sarebbe troppo onerosa in termini di tempo una risposta ?

Io non ho proprio capito la domanda, non ho capito che ci azzecca il C nel topic e non ho nemmeno capito se vuoi scrivere qualcosa o vuoi capire come funziona quel codice o il pattern matching in se.

[Zebra75]

Originariamente inviato da mjordan

Io non ho proprio capito la domanda, non ho capito che ci azzecca il C nel topic e non ho nemmeno capito se vuoi scrivere qualcosa o vuoi capire come funziona quel codice o il pattern matching in se.

credo invece che tu abbia capito!
Mi interessa capire come funziona il pattern matching in se

[mjordan]

Originariamente inviato da Zebra75

credo invece che tu abbia capito!
Mi interessa capire come funziona il pattern matching in se

Ah allora la risposta non è difficile.
Ci sono tantissimi metodi per realizzare il pattern matching, tutte varianti specializzate del piu' generico string matching.
Il vero problema, in questo caso, non è tanto l'implementazione in se quanto trovare un'implementazione che sia efficiente. In genere per realizzare string/pattern matching ci si basa sull'algoritmo di Knuth-Morris-Pratt (detto semplicemente algoritmo KMP)
Ulteriori dettagli li trovi ovunque, anche implementazioni (molto spesso in C).

[Zebra75]

Originariamente inviato da mjordan

Ah allora la risposta non è difficile.
Ci sono tantissimi metodi per realizzare il pattern matching, tutte varianti specializzate del piu' generico string matching.
Il vero problema, in questo caso, non è tanto l'implementazione in se quanto trovare un'implementazione che sia efficiente. In genere per realizzare string/pattern matching ci si basa sull'algoritmo di Knuth-Morris-Pratt (detto semplicemente algoritmo KMP)
Ulteriori dettagli li trovi ovunque, anche implementazioni (molto spesso in C).

quindi avendo una espressione regolare com e questa:
"/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

come farebbe un ipotetico codice in C a verificare l'input di un utente ?

Mi basterebbe anche una spiegazione testuale senza alcuna implementazione giacchè quello che mi preme conoscere è il meccanismo di riconoscimento.

[mjordan]

Originariamente inviato da Zebra75

quindi avendo una espressione regolare com e questa:
"/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

come farebbe un ipotetico codice in C a verificare l'input di un utente ?

Mi basterebbe anche una spiegazione testuale senza alcuna implementazione giacchè quello che mi preme conoscere è il meccanismo di riconoscimento.

In C, per lo meno nella libreria standard, non hai funzioni che gestiscono espressioni regolari. Se tu volessi gestirle hai solo tre vie:
1) Usare una libreria atta allo scopo (la via preferita)
2) Implementare da te un sistema che le gestisca (tedioso e comunque non privo di alcun fondamento scientifico da poter essere fatto in 5 minuti senza alcuna conoscenza).
3) Implementare un piccolo parser di espressioni regolari mediante l'uso di una grammatica regolare e qualche generatore di parser.

Siccome il punto 1) dipende dalla libreria che usi, ti do un'infarinatura su un possibile metodo di risoluzione del punto 2) che poi è il fondamento del punto 3)
Le espressioni regolari (come dice il nome stesso) sono classificate come "linguaggi regolari". I linguaggi regolari sono quei linguaggi che possono essere generati da grammatiche regolari, le cui grammatiche possono essere rappresentate mediante automi a stati finiti. Un'automa a stati finiti, a sua volta, può essere implementato effettivamente in un computer mediante una struttura dati detta grafo, appositamente modificata, che consente diverse operazioni in modo semplice. Determinare quindi quale stringa appartiene a quale espressione, si traduce quindi in due operazioni:
1) Visita sul grafo e determinazione della posizione successiva.
2) Confronto di stringhe.

Il confronto di stringhe generalmente lo si fa con l'algoritmo di Knuth-Morris-Pratt mentre i tradizionali algoritmi di visita dei grafi vengono applicati.

In ogni caso, se non hai nessuna conoscenza della teoria che sta dietro a queste cose piu' una buona conoscenza di base di algoritmi e strutture dati, hai praticamente zero possibilità di fare un'implementazione ad hoc. Potresti abbozzare qualcosa con le funzioni di stringa, ma non avresti la certezza che il funzionamento possa essere corretto per ogni input e comunque procedendo "abbozzando", potresti solo trattare una piccola casistica. Infatti ci sarebbe anche il problema del bilanciamento di eventuali parentesi, punteggiatura, ecc. che poi sono dettate dalla sintassi che si vuole considerare.

Io non so se è questo che volevi sapere, in genere per le regexp si usa una libreria e non ci si preoccupa di questi dettagli implementativi, che sono invece alla base di chi si occupa di linguaggi formali, compilatori, interpreti e quant'altro necessiti di confronto fra stringhe, generazione e matching. Alcuni anni fa implementai una shell Unix con un piccolo analizzatore di espressioni regolare per la gesione dei comandi in ambiente Linux/Solaris, utilizzando esclusivamente lo standard C, senza librerie esterne (a parte nCurses per la gestione del prompt piu' altre chicche). Purtroppo quel codice andò perso ma ci vollero circa 2000 righe di codice solo per la gestione dell'input da riga di comando (tralasciando tutta la gestione dei processi richiesta). Nonostane ciò, continuava ad essere un piccolo progetto universitario, quindi niente di che possa essere messo in produzione effettivamente (anche se gestiva praticamente in modo corretto anche i child process di init e KDE . Ne ero orgoglioso.
Fu un progetto di sistemi operativi, ma l'effettiva implementazione richiese conoscenze apprese in materie come compilatori, metodi formali dell'informatica e algoritmi e strutture dati. Implementare questa roba a "mano" nella pratica non si fa mai, a meno che, come ti dicevo prima, non si abbiano esigenze particolari (ma anche li basta usare un generatore di parser, quindi le casistiche di effettiva necessità sono ancora piu' ristrette).

[Zebra75]

ho fatto algoritmi e strutture dati ma non abbiamo studiato l'algoritmo da te esposto!

Ma matroidi, alberi binari, ternari, k-ari, grafi e compagni bella si, a iosa.

cmq, sei stato esaustivo ma mi è rimasto un dubbio. Partendo da questo "/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

il parser legge la parte in grassetto come se fossero delle istruzioni per lui ed analizza che i primi 6 caratteri siano formati da lettere

"/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

poi legge le successive istruzioni nelle regexp, sempre quelle in grassetto e ricavate le informazioni verifica che i successivi due caratteri siano realmente due numeri

e così via....

E' così che funzionerebbe ?



uhm............
però forse viene usato un albero binario

[mjordan]

Originariamente inviato da Zebra75

ho fatto algoritmi e strutture dati ma non abbiamo studiato l'algoritmo da te esposto!

Ma matroidi, alberi binari, ternari, k-ari, grafi e compagni bella si, a iosa.

Perfetto allora hai tutte le nozioni per proseguire nella comprensione. Hai per caso il Cormen-Leiserson-Rivest come libro?

cmq, sei stato esaustivo ma mi è rimasto un dubbio. Partendo da questo "/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

il parser legge la parte in grassetto come se fossero delle istruzioni per lui ed analizza che i primi 6 caratteri siano formati da lettere

"/^[a-zA-Z]{6}[0-9]{2}[a-zA-Z][0-9]{2}[a-zA-Z][0-9]{3}[a-zA-Z]$/"

poi legge le successive istruzioni nelle regexp, sempre quelle in grassetto e ricavate le informazioni verifica che i successivi due caratteri siano realmente due numeri

e così via....

E' così che funzionerebbe ?

Molto approssimativamente si. Ma proprio molto approssivamente. In pratica si effettua una tokenizzazione ad hoc della stringa e poi con le tecniche che ti ho detto si fa l'accettazione. Comunque se è il funzionamento, che ti interessa, puoi provare a scrivere quelle regole dando in pasto a Bison una bella grammatica che la descrive. Una volta fatto ciò, esso ti genererà un bell'analizzatore, che semplicemente lo puoi richiamare in un banale programma C da passare in un debugger per fare un'esecuzione "passo passo", cosi ti rendi conto effettivamente di tutti i passaggi computazionali che fa.

Per me un debugger è uno strumento indispensabile anche per leggere il codice, non solo per trovare errori.

Vale la pena di impararlo, soprattutto se ti interessi di queste cose:
http://www.gnu.org/software/bison/ma...le-GLR-Parsers

E' un tool meraviglioso. Le grammatiche che passerai sono molto simili alla forma normale di Backus, che ti divrebbe essere familiare.

EDIT: Con i matroidi e la programmazione lineare si possono fare dei semi miracoli quando si parla di strutture dati, visite e tempi di accesso (*cough* *cough* euristiche...)

[Zebra75]

abbiamo anche noi il Cormen come libro di testo che tra le altre cose, è stato corretto, nella versione italiana, dal nostro docente

[mjordan]

Originariamente inviato da Zebra75

abbiamo anche noi il Cormen come libro di testo che tra le altre cose, è stato corretto, nella versione italiana, dal nostro docente

Bene li l'algoritmo KMP c'è

[Zebra75]

Originariamente inviato da mjordan

Bene li l'algoritmo KMP c'è

se non è troppo e se non ho compreso male, potresti dare in pasto a Bison quell'espressione rerolare e farmi vedere cosa ti genera ?

[Zebra75]

ho sbagliato thread, scusate

[misterx]

Originariamente inviato da Zebra75

se non è troppo e se non ho compreso male, potresti dare in pasto a Bison quell'espressione rerolare e farmi vedere cosa ti genera ?

interesserebbe anche a me