%%% Karol Bienkowski %%% Zadanie zaliczeniowe z Laboratorium Programowania w Logice %%% Lublin, 29 czerwca 2002 %%% Parser XMLa oraz XPath %%% % Dziala w SWI-Prolog 3.4.2 % XPath do obejrzenia pod adresem: http://www.w3.org/TR/xpath % Uruchomienie: run(XPath, Result), np. run('/*/elem', X) uzgadnia % X z lista reprezentacji tekstowych wezlow wybranych zapytaniem % /*/elem. XML jest czytany z pliku test.xml. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Pomocnicze (obsluga znakow): %%% DCG char_code_(X, Y) :- char_code(X, Y). %char_code_(X, X). % litera letter( X ) --> [X], {char_code_(X, A), ( A >= 97, A =< 122 ; A >= 65, A =< 90 )}. % litera lub cyfra alphanum( X ) --> letter(X). alphanum( X ) --> [X], {char_code_(X, A), A >= 48, A =< 57}. % bialy znak white( X ) --> [X], {char_code_(X, A), ( A == 10 ; A == 13 ; A == 27 ; A == 32 )}. % ciag bialych znakow whites --> [] | white(_), whites. % niepusty ciag bialych znakow whites1 --> white(_), whites. % litera, cyfra lub bialy znak char( X ) --> alphanum(X) | white(X). % cudzyslow lub podwojny cudzyslow quote( Q ) --> [Q], {( Q = '"' ; Q = '\'' )}. % cyfra (uzgadnia parametr z wartoscia liczba, wartoscia cyfry) digit( X ) --> [D], {char_code_(D, A), A >= 48, A =< 57, X is A - 48}. %%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Zachlanne wczytywanie: %%% DCG % identyfikator (maksymalny ciag liter i cyfr, zaczynajac od litery) ident( [L|I] ) --> letter(L), ident_(I), !. ident( [L] ) --> letter(L). % Kontynuacja identyfikatora (maksymalny ciag liter i cyfr) ident_( [A|I] ) --> alphanum(A), ident_(I), !. ident_( [A] ) --> alphanum(A). % tekst (maksymalny ciag liter, cyfr i bialych znakow) text( [L|T] ) --> char(L), text(T), !. text( [L] ) --> char(L). % liczba (maksymalny ciag cyfr) numb( X ) --> numb_( X, _ ). numb_( X, M ) --> digit( Y ), numb_( Z, N ), !, { X is N * Y + Z, M is N * 10 }. numb_( X, 10 ) --> digit( X ). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Leksemy XML: deklaracja [decl], start_tag [start(X)], %%% end_tag [end(X)], tekst [txt(X)] %%% DCG xlex( [decl|K] ) --> ['<'], ['?'], ['x'], ['m'], ['l'], whites1, ['v'], ['e'], ['r'], ['s'], ['i'], ['o'], ['n'], whites, ['='], whites, quote(Q), ['1'], ['.'], ['0'], quote(Q), whites, ['?'], ['>'], whites, xlex(K). xlex( [start(T)|K] ) --> ['<'], ident(T), whites, ['>'], xlex(K). xlex( [end(T)|K] ) --> ['<'], ['/'], ident(T), whites, ['>'], xlex(K). xlex( [start(T),end(T)|K] ) --> ['<'], ident(T), whites, ['/'], ['>'], xlex(K). xlex( [txt(T)|K] ) --> text(T), xlex(K). xlex( [] ) --> []. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Parser XMLa (buduje drzewo z element(Name, Children), %%% textnode(Text) i rootnode(RootElement); %%% dziecmi elementu sa inne elementy i wezly tekstowe) %%% DCG % parsuje dokument XML-owy (dokument XML ma zawsze jeden element) parse_xml( rootnode(E) ) --> [decl], parse_element(E). % parsuje element XML-owy parse_element( element(N1, C) ) --> [start(N)], parse_chld(C), [end(N)], {atom_chars(N1, N)}. % parsuje wezel tekstowy parse_text( textnode(T1) ) --> [txt(T)], {string_to_chrs(T1, T)}. % parsuje liste dzieci elementu parse_chld( [] ) --> []. parse_chld( [T|L] ) --> parse_text(T), parse_chld(L). parse_chld( [E|L] ) --> parse_element(E), parse_chld(L). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Serializer XMLa (z drzewa tworzy lancuch, %%% sluzy do wyswietlania wyniku programu) % zamienia na tekst (2p) jeden z wezlow drzewa (1p) serialize( rootnode(E), T ) :- serialize(E, T1), string_concat('', T1, T). serialize( textnode(T), T ). serialize( element(N, []), T ) :- !, mergestrlist(['<', N, '/', '>'], T). serialize( element(N, C), T ) :- serialize_all(C, L), mergestrlist(L, M), mergestrlist(['<', N, '>', M, '<', '/', N, '>'], T). % zamienia na tekst (2p) wszystkie wezly z listy (1p) serialize_all( [], [] ). serialize_all( [X|Y], [A|B] ) :- serialize(X, A), serialize_all(Y, B). % scala liste tekstow (1p) w jeden tekst (2p) mergestrlist([], ''). mergestrlist([A|B], X) :- mergestrlist(B, Y), string_concat(A, Y, X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Konwertuje wezly do tekstu: konkatenacja wartosci potomkow tekstowych %%% (wykorzystywane do porownania wezlow z napisami) % liczy wartosc tekstowa (2p) wezla (1p) string_value( textnode(T), T ). string_value( rootnode(E), T ) :- string_value(E, T). string_value( element(_, C), T ) :- string_value_all(C, T). % liczy wartosc tekstowa (2p) wszystkich wezlow z listy (1p). wynik (2p) to % konkatenacja wartosci tekstowej wezlow z listy string_value_all( [], '' ). string_value_all( [E|L], T ) :- string_value(E, T1), string_value_all(L, T2), string_concat(T1, T2, T). % odnosi sukckces, jezeli na liscie (1p) istnieje wezel o danej wartosci % tekstowej (2p). dziwna konstrukcja, ale inaczej nie dzialalo % (Value bez ciapkow, StrVal w ciapkach) exists_string_value( List, Value ) :- member(X, List), string_value(X, Value). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Parser XPath % Konstrukcje XPath: % / - wezel dokumentu (to co innego niz glowny element) % elem - wybranie elementu o nazwie elem (dziecko bierzacego) % * - wybranie wszystkich elementow (dzieci bierzacego) % elem/ch - wybranie dzieci wezla elem o nazwie ch % /*/name - wszystkie wnuki roota o nazwie name % elem[1] - pierwszy wezel o nazwie elem % e/a[2] - drugie dziecko wezla e o nazwie a % a/b[1]/c - dla a, biezemy pierwsze dziecko b i jego dziecko c % /elt/*[1]/elt[3] - trzeci elt pierwszego dziecka elt % /elt/*[b] - te dzieci elt, ktore maja dziecko b % /*/*[*/*] - te wnuki roota, ktore maja jakies wnuki % /elem[* = "ala"] - elem, jezeli ma dziecko o wartosci tekstowej "ala" % /elem[x = y] - elem, gdy ma dzieci x oraz y o rownych wartosciach tekstowych % Gramatyka dla XPath oraz eliminacja lewostronnej rekursji % path --> / rpath | / | rpath % -"- % rpath --> step % rpath --> step rpath_1 % rpath --> rpath / step % rpath_1 --> [] | / step rpath_1 % step --> name pred | * pred % -"- % pred --> [] | '[' pred_expr ']' % -"- % pred_expr --> numb | path | comp '=' comp % -"- % comp --> path | '"' string '"' % -"- % Drzewo XPath sklada sie z wezlow: % - root_expr - wyrazanie oznaczajace korzen drzwa % - cntxt_expr - wyrazanie oznaczajace biezacy wezel (biezacy wezel to % najpierw korzen, zmienia sie przy predykatach na % wezel badany w predykacie) % - path_expr(B, N, P) - oznacza krok sciezki. B - sciezka do tego kroku, % N - nazwa wezla (1-y filtr), P - predykat (2-i filtr) % - numb_expr(N) - wartosc liczbowa % - str_expr(S) - wartosc napisowa % - eq_expr(L, R) - porownanie % parsuje wyrazenie sciezkowe parse_path( E ) --> parse_root(R), parse_rpath(R, E). parse_path( R ) --> parse_root(R). parse_path( E ) --> parse_rpath(cntxt_expr, E). % parsuje sciezke wzgledna (2p). jako pierwszy parametr dostaje dotad % sparsowana sciezke (1p) parse_rpath( S, E ) --> parse_step(N, P), parse_rpath_1(path_expr(S, N, P), E). % predykat pomocniczy (z eliminacji lewostronnej rekursji) parse_rpath_1( S, S ) --> []. parse_rpath_1( S, E ) --> ['/'], parse_step(N, P), parse_rpath_1(path_expr(S, N, P), E). % parsuje jeden krok sciezki (nazwa (1p) i predykat (2p)) parse_step( N, P ) --> ident(I), parse_pred(P), {atom_chars(N, I)}. parse_step( *, P ) --> ['*'], parse_pred(P). % parsuje wyrazenie-korzen drzewa parse_root( root_expr ) --> ['/']. % parsuje predykat (ewentualnie pusty) parse_pred( true_expr ) --> []. parse_pred( PredExpr ) --> ['['], whites, parse_pexpr(PredExpr), whites, [']']. % parsuje wyrazenie, ktore moze byc predykatem parse_pexpr( numb_expr(N) ) --> numb(N). parse_pexpr( P ) --> parse_path(P). parse_pexpr( eq_expr(Left, Right) ) --> parse_comp(Left), whites, ['='], whites, parse_comp(Right). % parsuje lewa, albo prawa strone porownania parse_comp( E ) --> parse_path(E). parse_comp( str_expr(S) ) --> ['"'], text(S1), ['"'], {string_to_chrs(S, S1)}. %%%%%%%%%%%%%%%%%%%%%%%%% %%% Ewaluacja wyrazenia % eval - liczy wartosc (3p) wyrazenia (1p) w danym kontekscie (2p) % Do ewaluacji wyrazen uzywam konteksu, ktory zawiera biezacy wezel % oraz korzen drzewa. Oznaczam go stala con % (con(RootNode, ContextNode, Position)). %%% Ewaluacja do liczby (nv - NumericValue) eval( numb_expr(N), _, nv(N) ). %%% Ewaluacja od napisu (sv - StringValue) eval( str_expr(S), _, sv(S) ). %%% Ewaluacja do wartosci logicznej (bv - BooleanValue) eval( true_expr, _, bv(true) ). eval( eq_expr(L, R), Cont, bv(true) ) :- eval(L, Cont, nsv(LNodes)), eval(R, Cont, nsv(RNodes)), exists_string_value(LNodes, Str), exists_string_value(RNodes, Str), !. eval( eq_expr(L, R), Cont, bv(true) ) :- eval(L, Cont, nsv(LNodes)), eval(R, Cont, sv(Str)), exists_string_value(LNodes, Str), !. eval( eq_expr(L, R), Cont, bv(true) ) :- eval(L, Cont, sv(Str)), eval(R, Cont, nsv(RNodes)), exists_string_value(RNodes, Str), !. eval( eq_expr(L, R), Cont, bv(true) ) :- eval(L, Cont, sv(Str)), eval(R, Cont, sv(Str)). % Konwersja niepustego NSV na true eval( Expr, Con, bv(true) ) :- eval( Expr, Con, nsv([_|_]) ). %%% Ewaluacja do listy wezlow (nsv - NodeSetValu) eval( root_expr, con(R, _, _), nsv([R]) ). eval( cntxt_expr, con(_, N, _), nsv([N]) ). eval( path_expr(Start, Name, Pred), Context, nsv(List) ) :- eval(Start, Context, nsv(Base)), getnodesall(Base, Name, Pred, Context, List). % dla kazdego wezla z listy (1p) pobiera wezly-dzieci o danej nazwie (2p) % spelniajace predykat (3p). scala tak otrzymane listy wezlow (5p). % do obliczen wykorzystuje kontekst (4p) getnodesall( [], _, _, _, [] ). getnodesall( [Node|Rest], Name, Pred, Context, List ) :- getnodes(Node, Name, Pred, Context, List1), getnodesall(Rest, Name, Pred, Context, List2), append(List1, List2, List). % dla danego wezla (1p) pobiera dzieci (5p) o danej nazwie (2p) spelniajace % predykat (3p). do obliczen uzywa konstekstu (4p) getnodes( textnode(_), _, _, _, []). getnodes( rootnode(Elt), Name, Pred, Context, List) :- filtername([Elt], Name, List1), filterpred(List1, Pred, Context, List). getnodes( element(_, Chld), Name, Pred, Context, List ) :- filtername(Chld, Name, List1), filterpred(List1, Pred, Context, List). % wybiera z listy (1p) wezly (3p) o danej nazwie (2p). * to dowolny filtername( C, *, C ) :- !. filtername( [], _, [] ). filtername( [element(Name, C)|Rest], Name, [element(Name, C)|List]) :- !, filtername(Rest, Name, List). filtername( [_|Rest], Name, List) :- filtername(Rest, Name, List). % wybiera z listy (1p) tylko te wezly (4p), ktore spelniaja predykat (2p). % do obliczen wykorzystywany jest kontekst (3p) filterpred( List, Pred, con(R, _, _), Filtered ) :- filter_(List, Pred, con(R, _, 1), Filtered). % j.w. iteruje po wszyskich wezlach z (1p) zmieniajac pozycje w kontekscie filter_( [], _, _, [] ) :- !. filter_( [Node|Rest], Pred, con(R, _, Pos), [Node|List] ) :- true_pred(Pred, con(R, Node, Pos)), !, Pos1 is Pos + 1, filter_(Rest, Pred, con(R, _, Pos1), List ). filter_( [_|Rest], P, con(R, N, Pos), List ) :- % jezeli nie true_pred Pos1 is Pos + 1, filter_(Rest, P, con(R, N, Pos1), List). % odnosi sukckes, gdy predykat (1p) spelniony dla danego wezla (3p) % w kontekscie (2p) true_pred(Pred, Context) :- eval(Pred, Context, nv(N)), !, Context = con(_, _, N). true_pred(Pred, Context) :- eval(Pred, Context, bv(true)). %%%%%%%%%%%%% %%% Program % zamienia string na liste znakow (a nie ich kodow) i vice versa string_to_chrs( Str, Chrs ) :- is_list(Chrs), !, atom_chars(At, Chrs), string_to_atom(Str, At). string_to_chrs( Str, Chrs ) :- string_to_atom(Str, At), atom_chars(At, Chrs). % wczytuje zawartosc pliku test.xml (na string) process_file( Content ) :- seeing(Old), see('test.xml'), read_chars(Chrs), seen, see(Old), string_to_chrs(Content, Chrs). % czyta kolejne znaki z biezacego pliku read_chars( [Chr|Ret] ) :- get0(Chr), Chr \= -1, Chr \= 10, !, read_chars(Ret). read_chars( Ret ) :- get0(Chr), Chr \= -1, !, read_chars(Ret). read_chars( [] ). % uzgadnia parametr z drzewem utworzonym z czytania pliku xtest(Tree) :- process_file(Content), string_to_chrs(Content, Chrs), xlex(Lexs, Chrs, []), parse_xml(Tree, Lexs, []). % przykladowe zapytanie %xpath_query('/root/elem/a[2]'). xpath_query("/*[1]/x1[ i = \"ala\" ]"). % uzgadnia parametr z drzewem utworzonym z przykladowego zapytania XPath ptest(Tree) :- xpath_query(Que), string_to_chrs(Que, Chrs), parse_path(Tree, Chrs, []). % testuje przykladowe zapytanie na przykladowym pliku test(V) :- xtest(F), ptest(Q), eval(Q, con(F, F, 1), nsv(L)), serialize_all(L, V). % dla podanego zapytania (1p) tworzy liste tekstowych reprezentacji wybranych % wezlow (2p) run( Que, Res ) :- xtest(Xml), string_to_chrs(Que, Chrs), parse_path(Tree, Chrs, []), eval(Tree, con(Xml, Xml, 1), nsv(Nodes)), serialize_all(Nodes, Res).