Conversione diretta ed inversa tra automi a stati non definiti (nfa) ed espressioni regolari
•Download as DOCX, PDF•
0 likes•4,132 views
Recommended
Recommended
More Related Content
What's hot
Similar to Conversione diretta ed inversa tra automi a stati non definiti (nfa) ed espressioni regolari
Similar to Conversione diretta ed inversa tra automi a stati non definiti (nfa) ed espressioni regolari (20)
Conversione diretta ed inversa tra automi a stati non definiti (nfa) ed espressioni regolari
- 1. UNIVERSITÀ DEGLI STUDI DI TRIESTE FACOLTÀ DI INGEGNERIA Tesi di Laurea in INGEGNERIA INFORMATICA Conversione diretta ed inversa tra automi a stati non definiti (NFA) ed espressioni regolari Relatore Prof. Eric Medvet Candidato Paolo Oltramonti Correlatore Dott. Andrea De Lorenzo Anno Accademico 2012/2013
- 2. Sommario Introduzione ....................................................................................................................................................................... 2 Risultato ......................................................................................................................................................................... 2 Stato dell’arte e motivazioni ........................................................................................................................................... 2 Vincoli di progetto e tecnologie software utilizzate ....................................................................................................... 2 Analisi ................................................................................................................................................................................. 3 Automi ............................................................................................................................................................................ 3 Struttura e codifica delle NFA ........................................................................................................................................ 4 Espressioni regolari ........................................................................................................................................................ 4 Elementi comuni e differenze tra NFA ed espressioni regolari ...................................................................................... 4 Progettazione ..................................................................................................................................................................... 6 Conversione da NFA ad espressione regolare ................................................................................................................ 6 Conversione da NFA a DFA ......................................................................................................................................... 6 Minimizzazione DFA ................................................................................................................................................... 6 Conversione da DFA a GNFA ................................................................................................................................... 7 Conversione da GNFA ad espressione regolare ......................................................................................................... 7 Conversione da espressione regolare ad NFA ................................................................................................................ 7 Dividere l’espressione in blocchi convertibili in maniera diretta ............................................................................... 7 Convertire i blocchi convertibili in maniera diretta in stati di NFA ............................................................................ 8 Inserire nella NFA gli stati intermedi ottenuti dalla conversione .............................................................................. 8 Realizzazione....................................................................................................................................................................... 9 Interfaccia ....................................................................................................................................................................... 9 Implementazione ......................................................................................................................................................... 10 Implementazione del modulo di conversione da NFA ad espressioni regolari ........................................................ 10 Implementazione del modulo di conversione da espressioni regolari a NFA .......................................................... 11 Implementazione dei moduli generici ..................................................................................................................... 12 Module ed integration test ............................................................................................................................................... 14 Esempi di conversione diretta ed inversa ......................................................................................................................... 15 Conclusioni........................................................................................................................................................................ 16
- 3. Introduzione L’obiettivo della tesi è quello di sviluppare un software che effettua la conversione diretta ed inversa tra automi a stati finiti non deterministici (NFA) codificatiattraverso oggetti JSON ed espressioni regolari sotto forma di stringa. Risultato Il lavoro ha portato alla realizzazione di un algoritmo composto da due moduli principali che eseguono la conversione e la conversione inversa. Il primo modulo riceve in ingresso un oggetto JSON che contiene la descrizione della NFA da convertire e restituisce in uscita una stringa contenente l’espressione regolare equivalente alla NFA fornita in ingresso. Il secondo modulo riceve in ingresso una stringa contenente l’espressione regolare da convertire e restituisce in uscita l’NFA equivalente codificata in un oggetto JSON. Stato dell’arte e motivazioni Il progetto si colloca nell’ambito di una ricerca di alto livello sulla generazione automatica di pattern a partire da esempi. Nella ricerca si sono esplorate due strade: Le NFA Le espressioni regolari Entrambe le strade si sono rivelate molto interessanti e quindi per beneficiare dei vantaggi di entrambi gli approcci era necessario sviluppare una metodologia per convertire da espressioni regolari ad NFA e viceversa. Vincoli di progetto e tecnologie software utilizzate I vincoli di progetto sono legati al fatto che questo software si deve integrare con un software preesistente. Il software preesistente è stato realizzato utilizzando linguaggio di programmazione Javascript e codifica le NFA come oggetti JSON, quindi i vincoli di progetto sono il linguaggio di programmazione e la codifica delle NFA.
- 4. Analisi Sono stati oggetto dell’analisi i seguenti aspetti: - Automi Struttura e codifica delle NFA Espressioni regolari Automi Un automa è un modello che permette di descrivere con precisione e in maniera formale il comportamento di un sistema. Distinguiamo due tipi principali di automi a stati finiti: gli automi a stati finiti deterministici (DFA) gli automi a stati finiti non deterministici (NFA) La differenza fondamentale tra queste due tipologie sta nel fatto che le NFA possono avere più stati attivi contemporaneamente, mentre le DFA possono avere soltanto uno stato attivo. Per maggiori informazioni: DFA: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_03.pdf NFA: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_05.pdf
- 5. Struttura e codifica delle NFA La struttura e la codifica delle NFA definite tramite un oggetto JSON non sono state realizzate dal laureando. Si riporta per completezza la struttura della NFA: [ { input char: [nextstates] … input char: [next states] }, … { input char: [next states] … input char: [next states] } ] Espressioni regolari Un’espressione regolare è un formalismo che permette di descrivere un insieme di stringhe. Definisce una funzione che prende in ingresso una stringa, e restituisce in uscita un valore booleano, a seconda che la stringa aderisca o meno al pattern. Un’espressione regolare è un linguaggio regolare. Maggiori informazioni: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_04.pdf Elementi comuni e differenze tra NFA ed espressioni regolari Elementi comuni: Entrambe le rappresentazioni sono dei pattern Entrambe le rappresentazioni riconoscono un linguaggio regolare Un linguaggio regolare può essere rappresentato con entrambe le rappresentazioni Differenze: Le espressioni regolari hanno il vantaggio di essere utilizzate negli editor di testo, quindi hanno maggiore utilità
- 6. I tempi di esecuzione: o delle NFA dipendono linearmente dalla lunghezza dell’input o delle espressioni regolari dipendono anche dalla complessità dell’espressione Nel grafico si può vedere una comparazione del tempo di esecuzione, al crescere di n, dell’espressione regolare e dell’input riportate sotto i grafici.
- 7. Progettazione La progettazione si articola in due fasi: - Progettazione del modulo di conversione da NFA ad espressioni regolari Progettazione del modulo di conversione da espressioni regolari a NFA Conversione da NFA ad espressione regolare Per convertire una NFA in un’espressione regolare, bisogna eseguire i passaggi descritti di seguito: - Convertire la NFA in DFA Minimizzare la DFA Convertire la DFA in GNFA Convertire la GNFA in espressione regolare attraverso il ripping degli stati Di seguito verranno descritti i passaggi sopra descritti nel dettaglio. Conversione da NFA a DFA La conversione da NFA a DFA viene fatta attraverso la costruzione dei sottoinsiemi, algoritmo con il quale si ottiene una DFA equivalente che simula il non determinismo della NFA, ma è deterministico. L’algoritmo di costruzione dei sottoinsiemi compie fondamentalmente due operazioni: - l’ €-closure: parte da uno stato e identifica tutti gli stati raggiungibili attraverso transizioni vuote Il move: inserisce nello stesso insieme tutti gli stati raggiungibili con lo stesso input a partire da uno stato qualunque di quelli ottenuti precedentemente attraverso l’€-closure Gli insiemi ottenuti saranno gli stati della DFA. Per maggiori informazioni: http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/TeseiLPC20032004Total.pdf(capitolo 2.5) Minimizzazione DFA La minimizzazione di una DFA viene fatta identificando ricorsivamente per ogni coppia di stati, gli stati differenti. Due stati differenti si identificano dal fatto che abbiano degli output diversi per gli stessi input. Il primo passaggio prevede l’esclusione delle coppie di stati finali-non finali. Nei passaggi successivi vengono ricorsivamente analizzate le coppie rimanenti fino a quando non ci sono più cambiamenti. Gli stati che non vengono identificati sono quindi uguali e possono essere raggruppati. Per maggiori informazioni: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_10.pdf
- 8. Conversione da DFA a GNFA La conversione da DFA a GNFA viene fatta aggiungendo uno stato prima del primo stato della DFA ed uno stato dopo l’ultimo stato della DFA. Questi due stati vengono collegati tramite delle transizioni vuote in modo da avere un unico stato iniziale ed un unico stato finale, caratteristica che contraddistingue una GNFA. Per maggiori informazioni: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf Conversione da GNFA ad espressione regolare La conversione da GNFA ad espressione regolare viene fatta eliminando ricorsivamente gli stati della GNFA uno ad uno fino a quando rimangono solamente lo stato iniziale e lo stato finale collegati da una singola transizione. L’operazione attraverso la quale si rimuovono ricorsivamente gli stati è denominata ripping. Lo stato che viene rimosso in uno specifico passaggio prende il nome di stato di ripping. Tutte le transizioni collegate allo stato di ripping vengono eliminate ed aggiunte agli stati precedenti e successivi modificando di conseguenza il valore della transizione. Alla fine del processo di ripping, nell’unica transizione rimasta, ci sarà l’espressione regolare. Per maggiori informazioni: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf Conversione da espressione regolare ad NFA Per convertire un’espressione regolare in una NFA, bisogna eseguire i passaggi descritti di seguito: - Creare una NFA con 2 stati ed un collegamento contenente l’espressione regolare Dividere l’espressione regolare in blocchiconvertibili in maniera diretta Convertire i blocchi convertibili in maniera diretta in stati di NFA Inserire nella NFA gli stati intermedi ottenuti dalla conversione Ripetere i gli ultimi due passaggi fino a quando non sono stati elaborati tutti blocchi convertibili Dividere l’espressione in blocchi convertibili in maniera diretta Le espressioni regolari possono essere convertite direttamente in stati di un automa se si presentano in una delle seguenti forme: - r1 r2 : Concatenazione r1 | r2 : “Or” logico r1* : Kleenclosure dove r rappresenta un’espressione regolare. Tutte le espressioni regolari possono essere ricondotte ricorsivamente a blocchi di questo tipo.
- 9. L’espressione regolare sarà quindi divisa in blocchi convertibili direttamente identificati in maniera ricorsiva. Convertire i blocchi convertibili in maniera diretta in stati di NFA I blocchi convertibili vengono convertiti in stati di automi secondo le seguenti regole: Per maggiori informazioni: http://www.csee.umbc.edu/~squire/cs451_l6.html Inserire nella NFA gli stati intermedi ottenuti dalla conversione Gli stati vengono inseriti ricorsivamente tra lo stato da cui esce la transizione con l’espressione del blocco e lo stato di destinazione della transizione.
- 10. Realizzazione La realizzazione si divide nella realizzazione di un’interfaccia rudimentale che sarà utilizzata soltanto per visualizzare i risultati e testare il funzionamento dell’algoritmo nell’implementazione del software. Interfaccia Al fine di testare l’algoritmo è stata creata una rudimentale interfaccia per poter visualizzare i risultati delle conversione ed eseguire dei test. L’interfaccia è stata realizzata attraverso una semplice pagina HTML suddivisa in 3 colonne: - Nella prima colonna viene visualizzata la macchina NFA in formato JSON Nella seconda colonna viene visualizzata la macchina in formato grafico Nella terza colonna sono presenti: o La form per inserire l’espressione regolare da convertire con il pulsante per eseguire la conversione o Il pulsante per eseguire la conversione inversa o La label con l’espressione regolare, risultato della conversione inversa La pagina HTML è stata sviluppata dal laureando, mentre le librerieJavascript che disegnano la NFA nella pagina sono state fornite dal relatore.
- 11. Implementazione Anche l’implementazione come la progettazione si articola in due fasi: - Implementazione del modulo di conversione da NFA ad espressioni regolari Implementazione del modulo di conversione da espressioni regolari a NFA Di seguito il diagramma delle classi. Implementazione del modulo di conversione da NFA ad espressioni regolari La realizzazione del modulo di conversione da NFA ad espressioni regolari è composta dall’implementazione dei quattro sotto moduli descritti nella fase di analisi e dall’integrazione di essi. Analizziamo nel dettaglio i sotto moduli. Implementazione del sotto modulo di conversione da NFA a DFA Il modulo riceve in ingresso una NFA e restituisce in uscita una DFA. La DFA viene ottenuta utilizzando l’algoritmo di costruzione dei sottoinsiemi spiegato nel capitolo di analisi. Il metodo eClosure riceve in ingresso una NFA e lo stato su cui applicare l’algoritmo di eClosure e restituisce in uscita l’insieme degli stati della NFA raggiungibili tramite transizioni vuote a partire dallo stato passato come parametro. Il metodo moveTo riceve in ingresso una NFA, un insieme di stati su cui applicare l’algoritmo di moveTo e i valori di input con i quali applicare l’algoritmo. Restituisce in uscita un array con i risultati dell’algoritmo di moveTo applicato a tutti gli input della NFA, quindi un array contenente i possibili nuovi stati della DFA.
- 12. Implementazione del sotto modulo di minimizzazione della DFA Il modulo riceve in ingresso una DFA e restituisce in uscita una DFA minimizzata secondo l’algoritmo spiegato nel capitolo dell’analisi. Implementazione del sotto modulo che converte la DFA in GNFA Il modulo riceve in ingresso una DFA e restituisce in uscita una GNFA attraverso l’algoritmo spiegato nel capitolo dell’analisi. Implementazione del sotto modulo che converte la GNFA in espressione regolare Il modulo riceve in ingresso una GNFA e restituisce in uscita un’espressione regolare attraverso l’algoritmo spiegato nel capitolo dell’analisi. Implementazione del modulo di conversione da espressioni regolari a NFA La realizzazione del modulo di conversione da espressioni regolari a NFA è composta dall’implementazione della logica descritta nel capitolo dell’analisi. E’ stato aggiunto un modulo di preelaborazione dell’espressione regolare in modo da poter convertire espressioni regolari contenenti dei simboli non convertibili direttamente in stati di NFA. Analizziamo nel dettaglio i sotto moduli.
- 13. Implementazione del modulo di preelaborazione dell’espressione regolare Il modulo riceve in ingresso un’espressione regolare e restituisce in uscita un’espressione regolare applicando le seguenti conversioni: - r+ viene convertito in rr* r{n} viene convertito in una concatenazione di r ripetute n volte r{n,} viene convertito in una concatenazione di r ripetute n volte più una r* alla fine Implementazione del modulo di conversione da espressione regolare a NFA Il modulo riceve in ingresso un’espressione regolare e restituisce in uscita una NFA. La NFA viene ottenuta implementando l’algoritmo descritto nel capitolo dell’analisi. Il metodo expressionsBlocks riceve in ingresso un’espressione regolare e restituisce un array di stringhe contenenti dei blocchi dell’espressione regolare convertibili in stati di NFA in maniera diretta. Il metodo revAtomicRegex riceve in ingresso lo stato di partenza e di destinazione di una transizione e il suo valore di input, che deve essere un’espressione regolare convertibile direttamente in stati di una NFA. Implementazione dei moduli generici Sono stati realizzati anche dei moduli generici per ottimizzare operazioni ricorrenti: Nome: CreateNfa Funzione: Crea un nuovo automa vuoto Nome: CreateState (statename) Funzione: Crea un nuovo stato da poter assegnare ad un automa. Il parametro è il nome che viene assegnato al nuovo stato Nome: CreateTransaction(inval,outval) Funzione: Crea una nuova transizione da poter assegnare ad uno stato. Nei parametri vengono passati il valore dell’input della transizione e lo stato di destinazione
- 14. Nome: assignTransaction(transaction, state) Funzione: Assegna una transizione ad uno stato. Nei parametri vengono passati la transizione e lo stato a cui assegnarla Nome: assignState(state, nfa) Funzione: Assegna uno stato ad un automa. Nei parametri vengono passati lo stato e l’automa a cui assegnarlo Nome: indexOfState(stateVal, nfa) Funzione:Restituisce l’indice dello stato di un automa in base al nome dello stato Nome: InputsRange(nfa) Funzione: Restituisce un array contenente tutti gli input accettati da un automa. L’automa viene passato come parametro Nome: arrayIsEqual(array1,array2) Funzione: Confronta due array e restituisce true se gli array sono uguali o false se gli array sono diversi
- 15. Module ed integration test Per effettuare i test si è utilizzato il browser Google Chrome e delle librerie fornite dal relatore che permettono di disegnare la NFA in una pagina HTML. Si è quindi realizzata una pagina HTML con una semplice form che permette di inserire un’espressione regolare che verrà convertita in NFA e visualizzata in pagina. Nella form è presente anche un pulsante per effettuare la conversione inversa a partire dal risultato ottenuto con la conversione diretta. Il risultato della conversione inversa viene visualizzato in una label in modo da poter confrontare l’espressione regolare data inizialmente in ingresso con l’espressione regolare ottenuta dalla conversione inversa. Per effettuare i test dei singoli moduli si è utilizzata la console di Google Chrome, stampando i valori di ingresso e di uscita dei singoli moduli.
- 16. Esempi di conversione diretta ed inversa Di seguito si riportano alcuni esempi di conversione diretta ed inversa ottenuti utilizzando il software realizzato. 1. Regex: ab*ab*ab* Conversione a Nfa: Riconversione a regex: ab*ab*ab* 2. Regex: (ab|cd)efg Conversione a Nfa: Riconversione a regex: (cd|ab)efg 3. Regex: (ab*a|b)(a|b)* Conversione a Nfa: Riconversione a regex: (ab*a|b)(a|b)*
- 17. Conclusioni L’obiettivo era quello di realizzare un software che effettua la conversione da NFA a espressioni regolari e viceversa. L’obiettivo può considerarsi raggiunto in quanto il software effettua correttamente sia la conversione diretta che inversa. La parte che ha richiesto più attenzione nel progetto è stata quella di semplificazione dell’espressione regolare in modo che la conversione da NFA ad espressione regolare generasse l’espressione più semplice possibile. Per il funzionamento dell’algoritmo di ripping, bisogna applicare diversi livelli di semplificazione prima di arrivare all’algoritmo di ripping e nell’algoritmo di ripping stesso. Per questo progetto sono state implementate 32 funzioni Javascript utili a svolgere tutti i passaggi necessari per la conversione.