[SOLVED] %% -*- prolog -*-

%% -*- prolog -*-

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Fonctions de compatibilit entre diffrents systmes Prolog.

Copyright By Assignmentchef assignmentchef

%% Devrait marcher avec SWI-Prolog et GNU Prolog.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% character(+C)
%% Vrifie que C est un caractre.
%% Prolog, comme C, reprsente les caractres par leur code ASCII,
%% mais certaines implmentation, comme SWI, utilisent des atomes
%% de longueur 1 la place.
character(Char) :- integer(Char); atom(Char), atom_length(Char, 1).

%% Certains systms dfinissent `list` dautres `is_list`, alors la place
%% on dfini le ntre.
isa_list([]).
isa_list([_|_]).

%% string_to_chars(+Str, -Chars)
%% Converti une string en une liste de caractres.
%% Les chanes de caractres peuvent tre reprsentes de diffrentes manires,
%% et cela dpend aussi du systme Prolog utilis.
string_to_chars(Str, Chars) :- atom(Str), atom_codes(Str, Chars).
string_to_chars(Str, Chars) :-
%% Le Prolog officiel fait comme Haskell:String = [Char].
%% GNU Prolog suit cette pratique mais pas SWI Prolog qui utilise un
%% type spar pour les chanes de caractres, quil faut donc convertir
%% via `string_chars`.
= [] -> fail;
string(Str), string_chars(Str, Chars).
string_to_chars(Str, Chars) :- isa_list(Str), Chars = Str.

%% chars_to_string(+Chars, -Str)
%% Converti une liste de caractres en une string.
%% Si le systme Prolog utilis supporte les strings utilise a,
%% sinon utilise un atome.
chars_to_string(Chars, Str) :-
= [] -> atom_codes(Str, Chars); string_chars(Str, Chars).

%% GNU Prolog dfini `new_atom`, mais SWI Prolog lappelle `gensym`.
genatom(X, A) :-
(predicate_property(new_atom/2, built_in);% Older GNU Prolog
predicate_property(new_atom(_,_), built_in)) % Newer GNU Prolog
-> new_atom(X, A);
gensym(X, A).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Expressions Rgulires (RE)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% re_wf(+RE)
%% Vrifie que RE est une expression rgulire valide (Well-Formed).
re_wf(Char) :- character(Char).
re_wf(any). % Souvent nomm `.`.
re_wf(in([])).
re_wf(in([Char|Chars])) :- character(Char), re_wf(in(Chars)).
re_wf(notin(Chars)) :- re_wf(in(Chars)).
re_wf([]). % Souvent nomm “.
re_wf([RE|REs]) :- re_wf(RE), re_wf(REs).% Concatnation.
re_wf(RE1 / RE2) :- re_wf(RE1), re_wf(RE2). % Disjonction.
re_wf(?(RE)) :- re_wf(RE).
re_wf(*(RE)) :- re_wf(RE).
re_wf(+(RE)) :- re_wf(RE).
re_wf(name(Name, RE)) :- (atom(Name); integer(Name)), re_wf(RE). %Motif nomm.
%% Compatibilit pour les Prolog o String [Char].
re_wf(in(String)) :-
= [] -> fail;
string(String), string_chars(String, Chars), re_wf(in(Chars)).
re_wf(String) :-
= [] -> fail;
string(String), string_chars(String, Chars), re_wf(Chars).

%% match(+RE, +Str, -Groups, -Tail)
%% Fait un pattern-match de lexpression rgulire RE sur la liste de
%% caractres Str.Tail est la partie de Str qui reste aprs la
%% partie accepte par RE.Groups contient la liste des motifs nomms qui
%% ont t trouvs, avec leur chane de caractres.
match(Char, [Char|Tail], [], Tail) :- character(Char).
match(any, [_|Tail], [], Tail).
match(in(Chars), [Char|Tail], [], Tail) :- member(Char, Chars).
match(notin(Chars), [Char|Tail], [], Tail) :-
isa_list(Chars), + member(Char, Chars). %%+ -> negation
match([], Tail, [], Tail).
match([RE|REs], Str, Gs, Tail) :-
match(RE, Str, Gs1, T), match(REs, T, Gs2, Tail),
append(Gs1, Gs2, Gs).
match(RE1 / RE2, Str, Gs, Tail) :-
match(RE1, Str, Gs, Tail); match(RE2, Str, Gs, Tail).
match(?(RE), Str, [], Tail) :- match(RE, Str, [], Tail).
match(?(_), Str, [], Str).
match(*(RE), Str, Gs, Tail) :-
match(RE, Str, Gs1, T),
Str = T,%vite boucle-sans-fin lorsque RE accepte la chane vide.
match(*(RE), T, Gs2, Tail),
append(Gs1, Gs2, Gs).
match(*(_), Str, [], Str).
match(+(RE), Str, Gs, Tail) :-
match(RE, Str, Gs1, S), match(*(RE), S, Gs2, Tail),
append(Gs1, Gs2, Gs).
match(name(Name, RE), Str, [(Name = GStr)|Gs], Tail) :-
match(RE, Str, Gs, Tail),
append(GChars, Tail, Str),
%% Utilise `chars_to_string` pour que le rsultat soit plus facile
%% lire pour un humain.
chars_to_string(GChars, GStr).
%% Compatibilit pour les Prolog o String [Char].
match(String, Str, Gs, Tail) :-
= [] -> fail;
string(String), string_chars(String, Chars), match(Chars, Str, Gs, Tail).
match(in(String), Str, Gs, Tail) :-
= [] -> fail;
string(String), string_chars(String, Chars),
match(in(Chars), Str, Gs, Tail).
match(notin(String), Str, Gs, Tail) :-
= [] -> fail;
string(String), string_chars(String, Chars),
match(notin(Chars), Str, Gs, Tail).

%% match_string(+RE, +Str, -Groups, -Tail)
%% Comme `match`, mais opre sur des string.
%% Accepte en entre nimporte quel type de string:
%% un atome
%% une liste de caractres (la reprsentation standard ISO Prolog).
%% un objet de type string (e.g. comme utilis dans SWI-Prolog).
%% En sortie renvoie un string si possible (e.g. en SWI-Prolog)
%% ou sinon renvoie un atome.
match_string(RE, Str, Gs, Tail) :-
string_to_chars(Str, Chars),
match(RE, Chars, Gs, TailChars),
chars_to_string(TailChars, Tail).

%% search_in_chars(+RE, +Str, -Res)
%% Boucle de recherche, qui essaie de trouver des sous-chanes acceptes par
%% lexpression rgulire RE.
%% Renvoie dans Res la chane qui a t accepte par RE et
%% les sous-groupes qui ont t trouvs.
search_in_chars(RE, Str, Res) :-
match(RE, Str, Gs, Tail), append(FoundChars, Tail, Str),
chars_to_string(FoundChars, Found),
Res = [ = Found | Gs].
search_in_chars(RE, [_|Str], Res) :- search_in_chars(RE, Str, Res).

%% search(+RE, +Str, -Res)
%% Comme `search_in_chars` mais accepte des strings.
search(RE, Str, Res) :-
string_to_chars(Str, Chars),
search_in_chars(RE, Chars, Res).

%% Exemples de recherches:
%% search(hello / help / [*(a),b], hello about help, Res)
%% search([(, name(k,*(any)), =, name(v,*(any)), )],
%% (age=23) and (position=straight), Res)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Non-deterministic Finite State Automaton(NFA)
%% Un automate tats finis non-dterministe est reprsent ici par un
%% ensemble dtats (State), o chaque tat est associ un pas (Step)
%% qui indique ce qui peux se passer quand on est dans cet tat.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% state_wf(+State, +NFA)
%% Vrifie que State est un tat valide dans NFA.
state_wf(State, NFA) :- atom(State), member((State = _), NFA).

%% step_wf(+Step, +NFA)
%% Vrifie que Step est un pas valide dans NFA.
%% Un pas peu prendre la forme:
%% success si on a atteint un tat final (i.e. un succs).
%% step(Steps) o Steps est une liste dlments de la forme
%% (Char -> State) qui indique quel est ltat suivant selon le prochain
%% caractre. noter que ces lments peuvent mentionner plusieurs fois
%% le mme caractre, auquel cas chacun des tats correspondants est
%% acceptable.Cest ce qui justifie le N de NFA.
%% Au lieu de se terminer par une liste vide, la liste
%% simplement chane peut se terminer par un tat, qui est alors utilis
%% pour nimpore quel caractre qui nest pas mentionn dans la liste.
%% epsilon(Marks,States) o States est une liste dtats vers lesquels la
%% machine peut transitionner sans avoir besoin davancer dun caractre.
%% Ceci aussi justifie le N de NFA.
%% Marks est une liste de marques de la forme `beg(Name)` ou `end(Name)`,
%% qui indiquent que le sous-groupe nomm Name commence ou fini ici.
step_wf(success, _).
step_wf(step([]), _).
step_wf(step(S), NFA) :- state_wf(S, NFA).
step_wf(step([(Char -> State) | Steps]), NFA) :-
character(Char), state_wf(State, NFA), step_wf(step(Steps), NFA).
step_wf(epsilon([], []), _).
step_wf(epsilon([], [State | States]), NFA) :-
state_wf(State, NFA), step_wf(epsilon([], States), NFA).
step_wf(epsilon([Mark|Marks], Ss), NFA) :-
step_wf(epsilon(Marks, Ss), NFA),
(Mark = beg(Name); Mark = end(Name)),
(atom(Name); integer(Name)).

%% nfa_wf(+NFA)
%% Vrifie que NFA est une machine valide.
nfa_wf(NFA) :- nfa_wf(NFA, NFA).

%% nfa_wf(+Ss, +NFA)
%% Boucle interne de nfa_wf.
nfa_wf([], _).
nfa_wf([State = Step | Ss], NFA) :-
%% Chaque tat ne peut tre dfini quune seule fois.
member(State = _, Ss) -> fail;
step_wf(Step, NFA), nfa_wf(Ss, NFA).

%% nfa_match(+NFA, +Step, +Marks, +Str, -Groups, -Tail)
%% Cette relation est vrifie si la machine NFA, en partant de Step sur la
%% chane Str, peut atteindre un tat terminal, auquel cas Tail contient
%% ce qui reste de la chane.
%% En dautres termes, elle consomme des caractres de Str jusqu atteindre
%% un tat terminal et renvoie le reste non-consomm de la chane dans Tail.
%% Marks contient les marques dj vues, et Groups renvoie les sous-groupes
%% nomms.
nfa_match(_, success, [], Str, [], Str).
%% !!REMPLIR ICI!!

%% nfa_search_in_chars(+NFA, +Str, -Res)
%% Boucle de recherche, qui essaie de trouver des sous-chanes acceptes par
%% la machine NFA.
%% Renvoie dans Res la chane qui a t accepte par la NFA, et ses
%% sous-groupes, comme `search_in_chars`.
nfa_search_in_chars(NFA, Str, Res) :-
%% Le premier tat dans la liste est pris comme tat initial.
NFA = [(_State = Step) | _],
nfa_match(NFA, Step, [], Str, Gs, Tail), append(FoundChars, Tail, Str),
chars_to_string(FoundChars, Found),
Res = [ = Found | Gs].
nfa_search_in_chars(NFA, [_|Str], Res) :-
nfa_search_in_chars(NFA, Str, Res).

%% nfa_search(+NFA, +Str, -Res)
%% Comme `nfa_search_in_chars` mais avec des string.
nfa_search(NFA, Str, Res) :-
string_to_chars(Str, Chars),
nfa_search_in_chars(NFA, Chars, Res).

%% Exemples de recherches:
%% nfa_search([s0 = success], hello, Res).
%% -> devrait renvoyer [ = ] 6 fois.
%% nfa_search([s0 = step(s1), s1 = epsilon([], [s0, s2])), s2 = success],
%%hello, Res).
%% -> devrait trouver toutes les sous-chanes non-vides de hello.
%% nfa_search([s0 = step([(108 -> s1), (101 -> s1)]),
%% s1 = epsilon([], [s0, s2]),
%%s2 = success],
%%hello, Res).
%% -> devrait trouver ell, el, e, ll, l, et l.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% new_state(-State)
%% Cre un nouvel tat pas encore utilis dans NFA.
new_state(State) :- genatom(s, State).

%% re_comp(+RE, +EndState, -BeginState, -NFA)
%% Compile lexpression rgulire RE en un NFA dont ltat de dpart
%% est BeginState (qui est aussi le premier tat de sa liste) et ltat de
%% sortie lorsque RE a t accepte avec succs est EndState.
re_comp([], S, S, []).
re_comp([RE|REs], E, B, NFA) :-
re_comp(REs, E, I, NFA2),
re_comp(RE, I, B, NFA1),
append(NFA1, NFA2, NFA).
re_comp(any, E, B, [B = step(E)]) :- new_state(B).
re_comp(*(RE), E, B, [B = epsilon([], [B1,E]) | NFA]) :-
new_state(B), re_comp(RE, B, B1, NFA).
%% Compatibilit pour les Prolog o String [Char].
re_comp(String, E, B, NFA) :-
= [] -> fail;
string(String), string_chars(String, Chars), re_comp(Chars, E, B, NFA).
%% !!REMPLIR ICI!!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% limination des cycles depsilon infinis
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% !! COMPLTER!!Le code ci-dessous limine les cycles depsilon
%% mais na aucun respect pour les marques.

%% nfa_epsilons(+NFAi, -NFAo)
%% NFAo est une version optimise de NFAi.
%% Loptimisation consiste remplacer dans les epsilon(Ss) les tats
%% qui sont eux-mme des epsilons par leurs destinations, de manire
%% ce quil ny ait plus de chanes depsilon.
%% Le but principal est dliminer les *cycles* depsilon.
nfa_epsilons(NFAi, NFAo) :- nfa_epsilons(NFAi, NFAi, NFAo).

%% nfa_epsilons(+NFA, +NFAi, -NFAo)
%% Boucle interne.
nfa_epsilons(_, [], []).
nfa_epsilons(NFA, [S = epsilon(_, Ss) | NFA1], [S = epsilon([], Ns) | NFA2]) :-
!, nfa_epsilons_1(NFA, [S], Ss, Ns),
nfa_epsilons(NFA, NFA1, NFA2).
nfa_epsilons(NFA, [S | NFA1], [S | NFA2]) :- nfa_epsilons(NFA, NFA1, NFA2).

%% nfa_epsilons_1(+NFA, +Epsilons, +States, -NonEpsilons)
%% Prend un liste dtats `States` et renvoie une liste dtats `NonEpsilons`
%% equivalente mais o les tats-epsilon ne sont plus prsents.
%% `Epsilons` est la liste des tats-epsilon dj vus.
nfa_epsilons_1(_, _, [], []).
nfa_epsilons_1(NFA, Es, [S|Ss], Ns) :-
member(S, Es)
%% Si S est un tat-epsilon quon a dj vu, il ny a rien de nouveau.
-> nfa_epsilons_1(NFA, Es, Ss, Ns)
;(member(S = epsilon(_, Ss1), NFA)
%% Un nouvel tat-epsilon.
-> append(Ss1, Ss, Ss2),
nfa_epsilons_1(NFA, [S|Es], Ss2, Ns)
;nfa_epsilons_1(NFA, Es, Ss, Ns1),
(member(S, Ns1)
-> Ns = Ns1
;Ns = [S|Ns1])).

%% re_compile(+RE, -NFA)
%% Point dentre pour compiler une expression rgulire en une NFA.
re_compile(RE, NFA) :-
new_state(E),% Ltat final.
re_comp(RE, E, B, NFA1),
%% limine les cycle depsilon qui peuvent apparatre par exemple
%% avec `*(RE)` si RE accepte la chane vide, comme `*(*(a))`.
nfa_epsilons(NFA1, NFA2),
(B = E; NFA2 = [B = _ | _])
%% Attention garder ltat initial B comme premier lment de NFA.
-> append(NFA2, [E = success], NFA)
; write(user_error, re_comp(not(etat_initial = premier_etat))),
nl(user_error), !, fail.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% re_search(+RE, +Str, -Res)
%% Boucle de recherche, qui essaie de trouver des sous-chanes acceptes par
%% lexpression rgulire RE en la compilant dabord vars un NFA.
%% Devrait donner des rsultats aussi fidles que possible
%% search(RE, Str, Res).
re_search(RE, Str, Res) :-
re_compile(RE, NFA),
(nfa_wf(NFA)
-> nfa_search(NFA, Str, Res);
Res = re_compile_error).

CS: assignmentchef QQ: 1823890830 Email: [email protected]