Visualizzazione Stampabile
Ciao a tutti dovrei fare un progetto in prolog per l'università e avrei bisogno di una mano per farlo perchè non so bene come muovermi T_T però prima di esporre il problema vorrei sapere se qui ci sono utenti che conoscono questo linguaggio dato che per quanto ho visto è raro trovarne x( o magari se conoscete un forum + indicato...
grazie!
che tipo di progetto prolog ? :uhm:
ecco si tratta di realizzare un compilatore da espressioni regolari a automi a stati finiti non deterministici...
la consegna è questa:
qualche consiglio su come iniziare sarebbe utile xD grazie.Citazione:
Lo scopo di questo progetto è di realizzare un compilatore da regexps ad NFA.
Il predicato principale da implementare è compile2nfa/2. Il secondo predicato da
realizzare è recognize/2. Infine (o meglio all’inizio) va realizzato il predicato regular_expression/1
1. regular_expression(RE) è vero quando RE è un’espressione regolare.Numeri ed atomi (in genere anche ciò che soddisfa atomic/1, è un’espressione regolare).
2. compile2nfa(FA_Id, RE) è vero quando, dato un identificatore FA_Id
per l’automa (ovvero un termine Prolog senza variabili), RE è compilabile in
un automa nella base dati del Prolog.
3. recognize(FA_Id, Input) è vero quando l’input per l’automa identificato da FA_Id viene consumato completamente e l’automa si trova in uno stato finale.
Suggerimenti
I predicati delta/4, initial/2 e final/2 sono definiti con un FA_Id come primo argomento.Attenzione a com’è gestito il cambio di stato in presenza del simbolo vuoto epsilon.
Il predicato compile2nfa ed i suoi predicati ancillari, dovendo creare una rappresentazione di un automa basata sulla regexp data, devono usare –ça va sans dir–
il predicato assert/1 o sue varianti.
Si suggerisce anche di definire dei predicati clear_nfas/0, clear_nfa/1, list_nfas/0 e list_nfa/1 che “puliscano” la base dati e che “listino” la struttura di un automa
poi aggiunge che:
In Prolog, senza disturbare il parser intrinseco del sistema, possiamo rappresentare le regexps semplici così:
• <re1><re2>…<rek> diventa [<re1>, <re2>, …, <rek>]
• <re1> | <re2> diventa or(<re1>, <re2>)
• <re>* diventa star(<re>)
Altre modalità di composizione di regexps sono:
• oneof([<re1>, <re2>, …<rek>]) ovvero una delle <rei>
• plus(<re>) ovvero almeno 1 ripetizione dell’espressione
Ma come vengono rappresentati gli automi?
E sai come si fa a generare un NFA che riconosce un linguaggio definito da un'espressione regolare? L'algoritmo lo trovi nelle dispense di Fondamenti dell'Informatica di Dovier e Giacobazzi, nel capitolo sulle espressioni regolari.
Il passaggio di stato con epsilon non dovrebbe presentare problemi: semplicemente, ogniqualvolta metti uno stato dentro al tuo set di stati corrente devi stare attento a mettere dentro anche tutti gli stati raggiungibili da esso tramite epsilon-transizioni (ovviamente questo vale ricorsivamente anche per stati inseriti in questo modo).
Se la rappresentazione dell'automa è lasciata libera, presta solo attenzione a distinguere bene lo stato iniziale e gli stati accettanti dell'automa rispetto agli altri stati "normali": questo semplifica la scrittura di compile2nfa perché ti risparmia di scorrere la lista di tutti gli stati.
Aggiungerò qualcosa: come vedi l'algoritmo per compile2nfa come è descritto nelle dispense è molto comodo da tradurre in un programma logico, in quanto definito per induzione sulla struttura delle espressioni regolari. Quindi puoi generare esplicitamente una clausola per ogni caso dell'induzione, sia base (cioè quando l'espressione è vuoto o è costituita da un singolo carattere) che induttivo (cioè è ottenuta per unione, giustapposizione o chiusura di Kleene). Quindi con cinque clausole te la cavi senza grossi problemi.
Posso permettermi di dire che questo progetto è facile, una volta che si è capito l'algoritmo :) ?