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