/*****************************************************************************/
/* */
/* Christophe DELORD */
/* */
/* Stage 1997/98 : ENSEEIHT - Traitement du langage naturel */
/* */
/*****************************************************************************/
:-module(lfg,
[
'@='/2, % Operateur d'unification pour les equations
make_far_links/2, % Connexion des liens a longue distance
afficher_frame/1 % Affichage du frame produit par l'analyseur
]
).
:-op(800,xfx,<-). % Unification de frames
:-op(800,xfx,@=). % Unification de sous-frames
:-op(800,xfx,+=). % Concatenation de listes terminees par une variable
/*****************************************************************************/
/* */
/* Representation des frames */
/* */
/*****************************************************************************/
/* Les frames sont representes par des listes dont la queue est une variable.
* Cela permet de faire les mises a jour des frames directement dans le meme
* frame et simplifie l'ecriture des equations associees aux regles
*/
/*****************************************************************************/
/* */
/* Equations LFG */
/* */
/*****************************************************************************/
% F et G sont de la forme : frame:liste_de_champs
F @= G :-
extract(F,F1,OP), % OP = <- ou +=
extract(G,G1,_), % On extrait les deus sous-frames a unifier
( OP='<-'
->
F1<-G1, G1<-F1 % Unification des frames
;
F1+=[G1|_] % Memorisation des liages longue distance
).
extract(F,F,'<-'):- % Extraction d'une variable : '<-' = unification
var(F),
!.
extract(F:[far_up],F1,'+='):- % Extraction de la liste des liasons longues
!, % '+=' = concatenation (ensembliste)
F<-far_up=F1.
extract(F:[far_down],F1,'+='):-
!,
F<-far_down=F1.
extract(F:[X|S],F1,OP):- % Parcours du chemin d'acces
!,
F<-X=Y, % On cherche (ou on cree) le frame de nom X
extract(Y:S,F1,OP). % Puis on poursuit la recherche sur ce frame
extract(F:[],F,'<-'):- % Chemin d'acces vide => on renvoie F
!.
extract(F,F1,'<-'):- % Pour le cas des predicats
F=..[FCT|ARGS], FCT\='.', FCT\=',', FCT\=':', ARGS\=[],
!,
maplist(extract,ARGS,N_ARGS), % on traite les arguments
F1=..[FCT|N_ARGS]. % et on le reconstruit
extract(F,F,'<-'). % Dans les autres cas, rien a faire
extract(F,G):-extract(F,G,_).
/*****************************************************************************/
/* */
/* Unification */
/* */
/*****************************************************************************/
/* Cas particuliers ou les frames sont vides */
% Si G est vide, on le lie avec F
F <- G :- var(G), !, F=G.
% Si F est vide, on le cree avec G.
% Si G n'est pas un frame, il faut creer la liste : F=[G|_]
F <- G :- var(F), !, (G=(_=_) -> F=[G|_] ; F=G).
% On parcous le frame G, et on insere chaque couple attribut=valeur dans F
F <- [A=V|G] :- !, F <- A=V, (var(G) -> true ; F<-G).
% Cas particulier des liasons longue distance : concatenation
[far_up=FAR_UP|_] <- far_up=UP :- !, FAR_UP+=UP.
[far_down=FAR_DOWN|_] <- far_down=DOWN :- !, FAR_DOWN+=DOWN.
% Unification de deux attributs deja presents : on unifie les valeurs
[A=V1|_] <- A=V2 :- !, V1<-V2.
% Tant que l'attribut n'est pas trouve, on continue sur la suite du frame
[_|F] <- A=V :- !, F<-A=V.
F <- F.
/*****************************************************************************/
/* */
/* Ajout d'une liste de dependances a distance a la fin d'une autre */
/* */
/*****************************************************************************/
/* ca marche pas : [X|Y]+=[X|Y] => bug
_ += L2 :- var(L2), !.
L1 += L2 :- var(L1), !, (is_list(L2) -> L1=L2; L1=[L2|_]).
[_|L1] += L2 :- L1 += L2.
*/
L1 += L2 :- % pour rajouter L2 a la fin de L1
filtre(L1,L2,L3), % L3 = liste des elements de L2\L1
cat(L1,L3). % On rajoute L3 a L1
:-op(800,xfx,has).
% Construit la liste L3=L1\L2
% Une variable de L2 n'est dans L1 que si c'est la MEME variable
% Ceci permet d'avoir plusieurs fois la meme liaison a distance
% mais de ne la prendre en compte qu'une seule fois
filtre(_,L2,_):-var(L2),!.
filtre(L1,[X|L2],L3):-L1 has X, !, filtre(L1,L2,L3).
filtre(L1,[X|L2],[X|L3]):-filtre(L1,L2,L3).
cat(_,L3):-var(L3),!. % L3 vide : rien a rajouter
cat(L1,L3):-var(L1),!,L1=L3. % L1 vide, on rajoute L3
cat([_|L1],L3):-cat(L1,L3). % Parcours L1 pour atteindre la queue
% has se comporte comme member, mais traite en plus le test d'egalite
% de deux variables SANS LES UNIFIER, ce qui est essentiel pour les
% liaisons longue distance
L has _ :- var(L), !, fail.
[X|_] has Y :- free_variables([X,Y],[X]), !.
[_|L] has Y :- L has Y.
/*****************************************************************************/
/* */
/* Affichage d'un frame */
/* */
/*****************************************************************************/
afficher_frame(F):-aff(F,5),nl.
aff(F,_):-var(F),!. % frame vide, on n'affiche rien
aff([],_):-!. % frame vide 'nettoye'
aff([X|F],I):- % affichage d'une variable
var(X),
!,
tab(I),
writef("%t",[X]),
aff(F,I).
aff([A=V|F],I):- % affichage d'un couple attribut=valeur
!,
nl,
tab(I),
writef("%15l = ",[A]),
(member(A,[predicate,far_up,far_down])
->
print(V)
;
I3 is I+3,
aff(V,I3)
),
aff(F,I).
aff(V,_):-writef("%t",[V]).
/*****************************************************************************/
/* */
/* Dependances a longue distance */
/* */
/*****************************************************************************/
/* Ici, les listes des liaisons a longue distance ont ete construites.
* Il faut maintenant apparier les liaisons vers le haut et vers le bas
*/
/* Pour faire ces liens :
* - On extrait les deux listes (liaisons vers le haut et vers le bas)
* - On unifie les elements de ces listes deux par deux
* - Et on nettoye le frame
*/
make_far_links(F,CF):-
get_links(F,FAR_UP,FAR_DOWN),
make_all_links(FAR_UP,FAR_DOWN),
clean(F,F,CF).
/* Pour lier les variables deux par deux :
* - On prend un element dans chaque liste
* - On les unifie
* - On continue sur le reste de la liste
* Cela implique que les deux listes ont la meme longueur. Sinon, la
* phrase est malformee
*/
make_all_links(FAR_UP,FAR_DOWN):-
my_member(ONE_FAR,FAR_UP,OTHER_FAR_UP),
my_member(ONE_FAR,FAR_DOWN,OTHER_FAR_DOWN),
make_all_links(OTHER_FAR_UP,OTHER_FAR_DOWN).
make_all_links([],[]).
% my_member renvoie en plus la liste privee de l'element
my_member(_,L,_):-var(L),!,fail.
my_member(E,[E|L],L).
my_member(E,[F|L],[F|M]):-my_member(E,L,M).
/* Extraction des liens
* On parcours le frame et on memorise a chaque etape le contenu des
* champs far_up et far_down
*/
get_links(F,_,_):-var(F), !.
get_links([far_up=UP|F],FAR_UP,FAR_DOWN):-
!,
get_links(F,FAR_UP,FAR_DOWN),
FAR_UP+=UP.
get_links([far_down=DOWN|F],FAR_UP,FAR_DOWN):-
!,
get_links(F,FAR_UP,FAR_DOWN),
FAR_DOWN+=DOWN.
get_links([_=V|F],FAR_UP,FAR_DOWN):-
!,
get_links(V,FAR_UP,FAR_DOWN),
get_links(F,UP_F,DOWN_F),
FAR_UP+=UP_F,
FAR_DOWN+=DOWN_F.
get_links(_,_,_).
/* Nettoyage du frame
* - Suppression des champs far_up et far_down
* - unification des frames lies a distance
*/
clean(_,F,F):-var(F),!.
clean(F,[far_down=_|S],CF):-!,clean(F,S,CF).
clean(F,[far_up=[FAR_UP|_]|S],CF):-
!,
F<-FAR_UP,
clean(F,S,CF).
clean(F,[A=V|S],[A=CV|CF]):-
!,
clean(V,V,CV),
clean(F,S,CF).
clean(_,X,X).