%% Description: Tree-Representation of Constituent Structure %% %% Writer: Ch. Lehner (1990: 168ff.) %% %% Name: tree.pl %% %% Tree-Representation of Constituent Structure %% tree(S):- ana(S,L,0,R,0), dr_baum(L). % ¿øÀúÀÚÀÇ 1Ç× ¼ú¾î drucke-baum/1À» tree/1·Î °³¸í ana(Baum,[k(Baum,Pos)],L_aussen,R_aussen,Altes_max):- atomic_oder_var(Baum), !, atomic_length(Baum,N), Rechtes_ende is L_aussen + N + 2, max(Altes_max,Rechtes_ende,R_aussen), Pos is (R_aussen + L_aussen + 2)//2 + N mod 2. ana(Baum,[k(F,Pos),L],L_aussen,R_aussen,Altes_max):- Baum =.. [F|Nachfolger], atomic_length(F,N), M is N + 2, max(Altes_max,M,Neues_max), ana_nachfolger(Nachfolger,L_aussen,R_aussen,L,Neues_max), erster_knoten(L,Pos1), letzter_knoten(L,Pos2), Pos is (Pos1 + Pos2)//2. ana_nachfolger([Baum],L_aussen,R_aussen,L,Max):- ana(Baum,L,L_aussen,R_aussen,Max), Pos is (L_aussen+R_aussen)//2. ana_nachfolger([Baum|Rest],L_aussen,R_aussen,L,Max):- ana(Baum,L1,L_aussen,M,Max), ana_nachfolger(Rest,M,R_aussen,L2,0), append(L1,L2,L). max(X,Y,X):- X >= Y, !. max(X,Y,Y). tr_li(Parse) :- S =.. Parse, tree(S). dr_baum(L):- L = [_|_], drucke_knoten(L,0), nl, drucke_aeste(L,0), nl, drucke_zweige(L,L1,0), nl, dr_baum(L1). dr_baum([]). drucke_knoten([X,Y|R],Spalte1):- Y \= [_|_], !, dr_kn(X,Spalte1,Spalte2), drucke_knoten([Y|R],Spalte2). drucke_knoten([X,[_|_]|R],S1):- dr_kn(X,S1,S2), drucke_knoten(R,S2). drucke_knoten([X],S):- dr_kn(X,S,_). drucke_knoten([],_). dr_kn(k(X,Pos),S1,S2):- atomic_length(X,N), N2 is Pos - N//2 - S1, tab(N2), S2 is Pos + N//2 + (N mod 2), write(X). /* Blaetter */ drucke_aeste([X,Y|Rest],S):- Y \= [_|_], !, drucke_aeste([Y|Rest],S). drucke_aeste([X],S):- !. /* nicht-verzweigende, z.B. lexikalische Kategorien */ drucke_aeste([k(X,Pos),L|Rest],S1):- knoten_zahl(L,1), !, tab(Pos-S1), write(|), S2 is Pos + 1 , drucke_aeste(Rest,S2). /* normale Kategorien */ drucke_aeste([X,[K|R]|Rest],S1):- !, dr_ae(X,[K|R],S1,S2), drucke_aeste(Rest,S2). drucke_aeste([],_). /* dr_ae(Dominierender_Knoten,[Tochter_links,L1,Tochter_rechts,L2] */ dr_ae(k(X,Pos),L,S1,S2) :- erster_knoten(L,Pos1), letzter_knoten(L,Pos2), tab(Pos1-S1+1), n_mal(Pos-Pos1-1,'_'), write(|), n_mal(Pos2-Pos-2,'_'), S2 is Pos2 - 1. erster_knoten([k(_,Pos)|L],Pos). /* einen letzten Knoten gibt es nur dann, wenn es einen ersten Knoten gibt */ letzter_knoten([_|R],Pos):- letzter_knoten(R,Pos). /* 1. Fall: Blatt */ letzter_knoten([k(_,Pos)],Pos):- !. /* 2. Fall: dominierender Knoten */ letzter_knoten([k(_,Pos),[_|_]],Pos). /************************************************/ /* Blaetter */ drucke_zweige([X,Y|Rest],Rest1,S1):- Y \= [_|_], !, drucke_zweige([Y|Rest],Rest1,S1). drucke_zweige([X],[],S):- X \= [_|_], !. /* nicht-verzweigende, z.B. lexikalische Kategorien */ drucke_zweige([k(_,Pos),X|Rest],L,S1):- knoten_zahl(X,1), !, tab(Pos - S1), write(|), S2 is Pos + 1, drucke_zweige(Rest,L1,S2), append(X,L1,L). /* normale Kategorien */ drucke_zweige([X,[K|R]|Rest],L,S1):- !, dr_zw(X,[K|R],S1,S2), drucke_zweige(Rest,L1,S2), append([K|R],L1,L). drucke_zweige([],[],_). /* dr_zw(Dominierender_Knoten,[Tochter_links,L1,Tochter_rechts,L2] */ dr_zw(k(X,Pos),L,S1,S4) :- erster_knoten(L,Pos1), tab(Pos1 - S1), write(/), S2 is Pos1 + 1, knoten_dazwischen(L,S2,S3), letzter_knoten(L,Pos2), tab(Pos2 - S3 - 1), write(\), S4 is Pos2 . knoten_dazwischen([k(_,_)|R],S1,S2):- drucke_zweige_fuer_knoten(R,S1,S2). drucke_zweige_fuer_knoten([k(_,_)],S,S):- !. drucke_zweige_fuer_knoten([k(_,_),[Letzte|Nachfolger]],S,S):- !. drucke_zweige_fuer_knoten([k(_,Pos)|R],S1,S2):- !, tab(Pos - S1), write(|), S3 is Pos + 1, drucke_zweige_fuer_knoten(R,S3,S2). drucke_zweige_fuer_knoten([_|R],S1,S2):- drucke_zweige_fuer_knoten(R,S1,S2). knoten_zahl([k(_,_)|L],1):- not(member_x(k(_,_),L)). n_mal(Arith,A):- X is Arith, n_mal_x(X,A). n_mal_x(N,A):- N > 0, !, write(A), M is N - 1, n_mal(M,A). n_mal_x(0,_). member_x(X,L):- member(X,L), !. atomic_oder_var(X):- var(X), !. atomic_oder_var(X):- atomic(X). atomic_length(X,5):- var(X), !. atomic_length(X,N):- name(X,L), list_length(L,N). list_length([],0). list_length([K|R],N):- list_length(R,M), N is M + 1. term_laenge(S,N):- atomic(S), !, atomic_length(S,N). term_laenge(S,N):- S \= [_|_], !, S =..[F|A], list_length(A,L), atomic_length(F,X), alle_args(A,Y), N is X + Y + 2 + L - 1. term_laenge(L,N):- L = [_|_], alle_args(L,X), list_length(L,Y), N is X + 2 + Y - 1. alle_args([],0). alle_args([K|R],N):- term_laenge(K,X), alle_args(R,Y), N is X + Y. /* test for printing the constituent structure */ % just type ?- testtree1. to test the predicate tree/1 testtree1 :- tree(s(np(det,n),vp(tv,np(det,n),pp(p,np(det,n))))). testtree2 :- tree(s(np(det(a),n(girl)),vp(tv(watches),np(det(a),n(boy)),pp(p(with),np(det(a),n(telescope))),pp(p(on),np(det(the),n(street)))))).