java espressioni regolari

[79Kuntz79]

Ciao Amici,
in una applicazione java, mi hanno detto che per risolvere il problema devo utilizzare delle espressioni regolari.

Qualcuno sa dirmi cosa significa e se ci sono degli esempi?

Grazie mille a tutti.

[bobc]

Si parla di espressioni regolari quando il linguaggio che si vuole compilare è un linguaggio regolare. Un linguaggio regolare è un linguaggio in cui in genere le produzioni hanno la forma:
A->a
A->aB
con A e B simboli non terminali (ovvero possono essere soggetto di ulteriori produzioni) e a simbolo terminale.
L'espressione regolare può inoltre essere analizzata mediante un automa deterministico a stati finiti.
Spero di avere reso l'idea...

[79Kuntz79]

non potresti scivermi qualche esempio?

[bobc]

Hai la traccia di quell'applicazione da fare?
comunque per ora ti faccio lo stesso qualche esempio sperando che3 esso ti possa tornare utile (purtroppo non ho alcun materiale relativo a questa fase di passaggio tra produzioni ed espressione che difatti è molto delicato, se hai pazienza e se puoi concedermi 24 ore invento un'esempio più completo, per ora ne scrivo uno così "alla buona")

Probabilmente ti sono assegnate delle produzioni: tu risolvile come se stessi facendo un sistema di equazioni di n incognite.
ad esempio
A->a
B->aB|C
C->A|epsilon
A,B,C simboli non terminali(ovvero possono fare altre produzioni)
a simbolo terminale (non ci sono altre produzioni).
L'epsilon significa un simbolismo nullo.

L'espressione regolare si ottiene (nota la chiamata ricorsiva da B ad aB):

E=(a+)|(a*)
(a+)significa che almeno una volta nel tuo linguaggio ci deve essere a (a*)significa che ci può essere il simbolo a nell'espressione da zero a più volte.L'epsilon e un'elemento bloccante, permette di specificare la fine di un'espressione.
In questo caso nel tuo analizzatore lessicale ti viene un automa con un solo stato che funge sia da stato iniziale che da stato finale, infatti con a* si vede che vengono considerate corrette anche espressioni nulle.

Un attimo che ti mando un ulteriore esempio circa la codifica da un espressione regolare ad un automa a stati finiti.

[bobc]

E=(a+|b+)* d+
dall'espressione regolare data, si dovrà ricavare l'automa riconoscitore.

Stato Input Cambio allo stato:
S0(iniziale) a S1
S0( " ) b S2
S0 d S3
S1 a S1
S1 d S3(finale)
S2 b S2
S2 d S3(finale)
S3(finale) d S3(finale)
A parole: si parte dallo stato S0.
Se si è in S0 e il carattere sotto la testina equivale ad a si passa allo stato S1, se equivale a b si passa ad S2. Da S0 si può passare inoltre allo stato S3 (nota l'asterisco nella prima sottoespressione)[...] Quando ti ritrovi nello stato finale puoi passare d quante volte vuoi (nota il simbolo + che significa ricorrenza minima uno,
infatti se ti trovi nello stato S3 condizione necessaria è che tu almeno una volta gli abbia passato d, ricorrenza massima un numero di ricorrenze qualsiasi maggiore di uno).Se lo stato dell'automa si ferma nello stato finale S3 senza errori, il linguaggio è corretto.

[bobc]

Ho dimenticato forse di dirti qualcosa.
La seguente espressione regolare:
E=(a+)|(a*)
che ho citato come esempio nel penultimo post accetta come linguaggio corretto le seguenti stringhe:
""(stringa vuota),"a","aa","aaa","aaaa","a...a(per n volte con n tendente ad infinito )".
Spero che ora ti sia un po più chiaro il concetto

[79Kuntz79]

ciao bob.
Sei veramente gentilissimo. Essendo al lavoro non ho approfondito molto quello che mi hai scritto.
Però ti inizio a dirti qual'è il mio problema e che mi hanno detto che lo devo risolvere per forza con le espressioni regolari ("è da aggiungere che io questo problema lo avevo risolto con gli array però mi hanno detto che lo devo fare con le espressioni regolari altrimenti niente da fare").
Ecco il mio problema;

Francesco, è nato ad Aversa, Il 20 aprile 1979 n. 789 perchè......

Nella mia stringa bisogna togliere n. 789. Quello che resa sempre fisso è "n." mentre il numro varia. Secondo te con le espressioni regolari si può risolvere questo problema e far diventare la mia stringa così?
Francesco, è nato ad Aversa, Il 20 aprile 1979 perchè......

Grazie.

P.S.: anche se non si risolve, leggerò lo stesso con attenzione la tua lezione, che sicuramente mi servirà in futuro.

[bobc]

Credo di aver capito...
tra qualche oretta scriverò la soluzione(spero! ).Ora lo sto facendo su un pezzo di carta.

[bobc]

La tua frase è compresa da una grammatica che genera le seguenti produzioni:
FRASE-><NOME><VIRGOLA><NATOA><CITTA'><VIRGOLA><DATANASCI TA><N><NUMERO><PERCHé>(<...>+)
<NOME>->"Francesco"(|"Giuseppe"|..., se sono ammessi più nomi)
<VIRGOLA>->","
<NATOA>->"è nato ad"
<CITTA'>->"Aversa"
<DATANASCITA>-><GIORNO><MESE><ANNO>
<GIORNO>->"20"
<MESE>->"Aprile"
<ANNO>->"1979"
<PERCHE>->"perchè"
<...>-><LETTERA>
<LETTERA>->a|b|d|e|f|...
Nota: i nomi scritti in maiuscolo sono iSIMBOLI NON TERMINALI e quelli in minuscolo i simboli terminali.
Nel prossimo post ti scrivo l'espressione regolare ottenuta con
l'automa riconoscitore.(un post troppo lungo può essere dispersivo )

[bobc]

Avevo dimenticato le due produzioni:
<N>->"n°"
<NUMERO>-><CIFRA>
<CIFRA>->1|2|3...

L'espressione regolare ottenuta è (non scrivo i simboli terminali reali poichè può risultare noioso):
E=nome virgola natoa città virgola giorno mese anno n (cifra+)/*perchè un numero può essere composto da più cifre...*/
perchè (...+)
Automa riconoscitore:
Stato Input StatoDestinazione
S0(iniz) nome S1
S1 virgola S2
S2 natoa S3
S3 città s4
s4 virgola s5
s5 giorno s6
s6 mese s7
s7 anno s8
s8 n s9
s9 cifra s10
s10 cifra s10
s10 perchè s11
s11 carattere s12
s12(finale)carattere s12