% re2nfa.pl - dicembre 2010
%
% compile2nfa
% %oneof
% plus
% or
% star --------
% recognize
% regular_expression
%Controllore delle regular expression
%Caso Base: Atomic
regular_expression(RE):- atomic(RE).
%Caso Complesso: Concatenazione rappresentato da lista => ab=[a,b]
regular_expression(_):- regular_expression(RE),regular_expression(REs).
%Caso Complesso: Opzione una delle due unione => a+b = or(a, b)
regular_expression(or(RE1,RE2)):- !,regular_expression(RE1),regular_expression(RE2).
%Caso Complesso: chiusura di Kleene => a*=star(a)
regular_expression(star(RE)):- regular_expression(RE).
%Caso Complesso: concatenazione con chiusura di Kleene medesimo =>
%aa*=plus(a)
regular_expression(plus(RE)):- regular_expression(RE).
%Caso Complesso: "Una delle" => a+b+c=oneof([a,b,c])
regular_expression(oneof([RE|REs])):- regular_expression(RE),regular_expression(RE).
%
%-------------------------------------------------------------------
%
%Creazione della NFA
compile2nfa(FA_Id,RE):- regular_expression(RE),assert(m(FA_Id)),clear2_nfa(FA_Id),assert(initial(FA_Id,q(0))),assert(final(FA_Id,q(0))),compile3nfa(FA_Id,RE).
%Caso base stringa vuota
compile3nfa(_,_).
%Stringa di un solo simbolo atomico
compile3nfa(FA_Id,RE):- atomic(RE), retract(final(FA_Id,q(N))),M is N+1, assert(delta(FA_Id,q(N),RE,q(M))),assert(final(FA_Id,q(M))),!.
%Concatenazione di concatenazione
compile3nfa(FA_Id,[RE|REs]):- RE=[_|_],compile3nfa(FA_Id,RE),compile3nfa(FA_Id,REs),!.
%Funzione or
compile3nfa(FA_Id,or(RE1,RE2)):-
retract(final(FA_Id,q(N))),
M is N,
assert(delta(FA_Id,q(N),epsilon,q(M))),
assert(final(FA_Id,q(M))),
compile3nfa(FA_Id,RE1),
retract(final(FA_Id,q(S))),
T is S,
assert(delta(FA_Id,q(N),epsilon,q(T))),
assert(final(FA_Id,q(T))),
compile3nfa(FA_Id,RE2),
retract(final(FA_Id,q(Y))),
Z is Y,
assert(final(FA_Id,q(Z))),
assert(delta(FA_Id,q(S),epsilon,q(Z))),
assert(delta(FA_Id,q(Y),epsilon,q(Z))),!.
%funzione plus
compile3nfa(FA_Id,plus(RE)):-
final(FA_Id,q(N)),
compile3nfa(FA_Id,RE),
final(FA_Id,q(M)),
assert(delta(FA_Id,q(M),epsilon,q(N))),!.
%funzione chiusura di Kleene
compile3nfa(FA_Id,star(RE)):-
retract(final(FA_Id,q(N))),
assert(final(FA_Id,q(N))),
compile3nfa(FA_Id,RE),
retract(final(FA_Id,q(M))),
assert(final(FA_Id,q(M))),
assert(delta(FA_Id,q(M),epsilon,q(N))),
assert(delta(FA_Id,q(N),epsilon,q(M))),!.
%funzione oneof
compile3nfa(FA_Id,oneof([RE1])):- compile3nfa(FA_Id,RE1),!.
compile3nfa(FA_Id,oneof([RE1,RE2])):- compile3nfa(FA_Id,or(RE1,RE2)),!.
compile3nfa(FA_Id,oneof([RE1,RE2|REs])):-append([RE2],REs,X), compile3nfa(FA_Id,or(RE1,oneof(X))).
%concatenazione
compile3nfa(FA_Id,[RE|REs]):- atomic(RE), retract(final(FA_Id,q(N))),M is N+1, assert(delta(FA_Id,q(N),RE,q(M))),assert(final(FA_Id,q(M))), compile3nfa(FA_Id, REs).
compile3nfa(FA_Id,[or(RE1,RE2)|REs]):-compile3nfa(FA_Id,or(RE1,RE2)),compile3nfa(FA_Id,REs),!.
compile3nfa(FA_Id,[plus(RE)|REs]):-compile3nfa(FA_Id,plus(RE)), compile3nfa(FA_Id,REs).
compile3nfa(FA_Id,[star(RE)|REs]):-compile3nfa(FA_Id,star(RE)), compile3nfa(FA_Id,REs).
compile3nfa(FA_Id,[oneof([RE1|RE2])|REs]):-compile3nfa(FA_Id,oneof([RE1|RE2])),compile3nfa(FA_Id,REs),!.
%
% ------------------------------------------------------------------------
%
%Controlla se la stringa finale Ë nello stato accettante
%Riconoscere se la stringa appartiene al linguaggio
%Si pone lo stato iniziale in caso di stringa o epsilon
recognize(FA_Id,[]):- initial(FA_Id,q(X)), recognize(FA_Id,[],q(X),_).
recognize(FA_Id,[RE|REs]):- initial(FA_Id,q(X)), recognize(FA_Id,[RE|REs],q(X),[X]).
%Input epsilon per iscritto
recognize(FA_Id,[epsilon|REs],q(X),A):- recognize(FA_Id,REs,q(X),A).
%Trova l'uscita con epsilon mosse
recognize(FA_Id,[],q(X),_):-final(FA_Id,q(X)).
recognize(FA_Id,[],q(X),_):- delta(FA_Id,q(X),'epsilon',q(Y)), X = Y, recognize(FA_Id,[],q(Y),_).
recognize(FA_Id,[],q(X),_):-delta(FA_Id,q(X),'epsilon',q(Y)),delta(FA_Id,q(Y),'epsilon',q(Z)),X\=Z,recognize(FA_Id,[],q(Z),_),!.
%ricorsione con funzione delta
recognize(FA_Id,[RE|REs],q(X),_):- delta(FA_Id,q(X),RE,q(Y)),recognize(FA_Id,REs,q(Y),[Y]),!.
recognize(FA_Id,[RE|REs],q(X),[X|Ds]):- delta(FA_Id,q(X),'epsilon',q(Y)),control(Y,[X|Ds]),recognize(FA_Id,[RE|REs],q(Y),[Y,X|Ds]).
%
% ------------------------------------------------------------------------
%
%Pulizia di una macchina chiamata dall'utente
clear_nfa(FA_Id):- retract(delta(FA_Id,_,_,_)),clear_nfa(FA_Id),!.
clear_nfa(FA_Id):- retract(initial(FA_Id,_)),retract(final(FA_Id,_)).
%Pulizia di una macchina chiamata dal programma per la sovrascrittura
clear2_nfa(FA_Id):- clear_nfa(FA_Id),!,retract(m(FA_Id)).
clear2_nfa(FA_Id):- retract(m(FA_Id)),!.
%Pulizia di tutte le macchine
clear_nfas:- retract(delta(_,_,_,_)),clear_nfas,!.
clear_nfas:- retract(initial(_,_)),retract(final(_,_)),clear_nfas,!.
clear_nfas.
%
% ------------------------------------------------------------------------
%
%Stampa a video una macchina
list_nfa(FA_Id):-listing(delta(FA_Id,_,_,_)),listing(final(FA_Id,_)),listing(final(FA_Id,_)).
%Stampa a video tutte le macchine
list_nfas:-listing(delta(_,_,_,_)),listing(initial(_,_)),listing(final(_,_)).
%
% ------------------------------------------------------------------------
%
%Sfoglia lista
control(_,[]).
control(Y,[X|Ds]):- X = Y, control(Y,Ds).
% ==== da integrare ===
% gensym2(X,Y,N):- concat(X,N,K), retract(K), assert(K), M is N, gensym2(X,Y,M).
% gensym2(X,Y,N):- concat(X,N,K), not(retract(K)), concat(X,N,Y), assert(Y).
%
% gensym(X,Y):- concat(X,1,K), retract(K), assert(K), gensym2(X,Y,2). %spostare dopo
% gensym(X,Y):- concat(X,1,Y), not(retract(Y)), assert(Y).
%ehmmmmmm