XML教程 4.ppt

1、Rcriture pour la programmation et la preuve,Claude Kirchner Pierre-Etienne Moreau,Application XML,Document XML,XML permet de dcrire des documents structurs Paul Mark Jurgen Julien Pierre On peut voir un document XML comme un arbre,Transformation de documents XML,On a envie de pouvoir manipuler ces d

2、onnes pour y rechercher de linformation pour gnrer de nouveaux documents (HTML, LaTeX, PDF, XML, etc.) Quels sont les outils permettant de le faire XSLT / XPath Xquery Xduce / Cduce DOM Peu permettent de manipuler un document XML en Java Les manipulations se font souvent en utilisant DOM directement

3、,Exemple,On veut savoir sil existe un noeud de la forme Julien Paul Mark Jurgen Julien Pierre ,Filtrage,Il faut savoir si un pattern XML filtre vers un noeud de document XML On aimerait pouvoir crire %match(t) Julien - / Noeud trouv Ou plus gnralement : X - ,Modle de donne (simplifi),ElementNode(nam

4、e:str, attrList:TNodeList, childList:TNodeList) - TNode AttributeNode(name:str, value:str) - TNode TextNode(data:str) - TNode conc(TNode*) - TNodeList,XML vs. Term,Un document XML peut se voir comme un arbre est reprsent par : ElementNode(A, conc(AttributeNode(a, at1), conc(ElementNode(B,conc(),conc

5、() ),Pattern XML,On veut pouvoir crire un pattern de la forme X qui sera encod par : ElementNode(A, conc(AttributeNode(a, at1), conc(X) ),Questions,A-t-on : X ? X ? Quel est le type de X ? TNode ? TNodeList ? On voudrait pouvoir crire X* Quelles sont les solutions ?,Questions,En fonction du parseur,

6、 peut tre reconnu comme A-t-on : X ? X* ? Comment est encod ? ElementNode(A, conc(AttributeNode(a, at1), conc( TextNode(), ElementNode(B,conc(),conc(), TextNode() ) Est-ce que cela filtre ?,Notation explicite,(_*,X,_*) qui correspond : conc(_*,X,_*) A-t-on (_*,X,_*) ? Oui, il y a 3 solutions,Notatio

7、n implicite,(_*,X,_*) qui correspond : X qui correspond galement X A-t-on X ? Oui, il y a 3 solutions,Attributs,Les attributs sont reprsents par une liste de couples (nom,valeur) Il existe galement des notations implicites et explicites Ainsi : correspond qui correspond ,Questions,A-t-on : ? ? Pourq

8、uoi ? car ? A-t-on : ? ? Non, car : (_*, a=at1, _*, b=at2, _*) ! (b=at2, a=at1) Il faudrait du filtrage AC avec lment neutre!,Attributs dans Tom,On considre un ordre sur les noms dattributs et les formes canoniques o les attributs sont tris Ainsi, est reprsent par ElementNode(A, conc(AttributeNode(a

9、, at1), AttributeNode(b, at2), conc() De mme, pour les motifs,Utilisation dans Tom,Node sort(Node subject) %match(subject) (X1*,p1,X2*,p2,X3*) - if(compare(p1,p2) 0) return sort(xml( X1* p2 X2* p1 X3* ); return subject; ,Comparaison dattributs,int compare(Node t1, Node t2) %match(t1, t2) n1 , n2 - r

10、eturn pareTo(a2); return 0; ,Ancrage formel,Mapping,Problmatique,Comment faciliter lutilisation du filtrage dans les programmes existants ? en permettant un mlange des syntaxes en permettant de filtrer vers des structures du langage hte Nous avons donc besoin de filtrer modulo des vues,Solution adop

11、te,Tom permet de voir les objets en mmoire comme des termes algbrique Il faut pour cela dfinir un ancrage formel permettant de savoir si un terme commence par un symbole donn daccder un sous terme donn,Plus formellement,On considre les ensembles : N, la reprsentation des entiers naturels B, la reprs

12、entation des boolens F, la reprsentation des symboles T(F), la reprsentation des termes clos X, la reprsentation des variables,Contraintes respecter,t1,t2T(F), eq(t1,t2) = t1=t2 fF, tT(F), is_fsym(t,f) = Symb(t)=f fF, i1.ar(f), tT(F) subtermf(t,i) = t|i,Structure de donnes,struct term int symb; stru

13、ct term *subterm; On reprsente les symboles par des entiers (zero,3), (suc,5), (plus,7), ,Mapping de Nat vers une structure C,%typeterm Nat implement equals(t1,t2) %op Nat zero is_fsym(t) %op Nat suc(p:Nat) is_fsym(t) get_slot(p,t) , struct term* term_equals(t1,t2) t!=null class B extends A int b; %

14、typeterm A implement A equals(t1,t2) t1.equals(t2) %typeterm B implement B equals(t1,t2) t1.equals(t2) ,Mapping objet,%op A A(a:int) is_fsym(t) t instanceof A get_slot(a,t) t.a %op A B(a:int,b:int) is_fsym(t) t instanceof B get_slot(a,t) t.a get_slot(b,t) t.b Aa=x new A(3) Bb=x new B(2,3) Aa=x new B

15、(2,3),Demo,Questions,Doit-on crire des mappings ? Que fait %vas au juste ?,Outils autour de Tom,Aterm, SDF, ApiGen, Vas,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermReal ATermPlaceholder ATermBlob ATermFactory,ATerms,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermRe

16、al ATermPlaceholder ATermBlob ATermFactory,getAnnotation setAnnotation toString etc.,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermReal ATermPlaceholder ATermBlob ATermFactory,getName getArity,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermReal ATermPlaceholder ATerm

17、Blob ATermFactory,getAFun getArgument setArgument etc.,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermReal ATermPlaceholder ATermBlob ATermFactory,getFirst getNext elementAt insert append concat etc.,Bibliothque ATerm,Aterm AFun ATermAppl ATermList ATermInt ATermReal ATermPlaceholder

18、 ATermBlob ATermFactory,makeAFun makeAppl parse readFromFile etc.,Utilisation des ATerms,Aterm t1 = factory.parse(a) Aterm t2 = factory.parse(f(a,b) t2.getArgument(1) = t1 ? true Aterm t3 = t2.setArgument(t1,2) t3 = f(a,a) Aterm t4 = factory.parse(f(a,f(b) f na pas de signature particulire Les Aterm

19、s permettent de construire des termes, mais il ny a pas de scurit (signature, types),ApiGen / Vas,A partir dune signature multi-sorte Gnre des classes, reposant sur les Aterms, permettant de reprsenter les termes partage maximal typage fort des termes tout terme typ est un ATerm,Exemple,Module Expre

20、ssions true - Bool false - Bool eq(lhs:Expr, rhs:Expr) - Bool id(value:str) - Expr nat(value:int) - Expr add(lhs:Expr, rhs:Expr) - Expr mul(lhs:Expr, rhs:Expr) - Expr,Classes gnres,Classes gnres,Stratgies,Programmation par rcriture,Avantages le filtrage est un mcanisme expressif les rgles expriment

21、des transformations lmentaires Limitations les systmes de rgles sont souvent non-terminant et/ou non confluent en gnral, on ne veut pas appliquer toutes les rgles en mme temps,Exemple de systme non terminant,And(Or(x,y),z) Or(And(x,z),And(y,z) And(z,Or(x,y) Or(And(z,x),And(z,y) Or(And(x,y),z) And(Or

22、(x,z),Or(y,z) Or(z,And(x,y) And(Or(z,x),Or(z,y) Not(Not(x) x Not(And(x,y) Or(Not(x),Not(y) Not(Or(x,y) And(Not(x),Not(y),Codage du contrle dans les rgles,Solution classique introduire un nouvel oprateur f pour restreindre lensemble de rgles permettant de normaliser l r devient f(l) r on normalise un

23、 terme f(t) loprateur f permet de contrler les rgles appliquer,Encodage du contrle,f(And(x,y) and(x,y) f(Not(x) not(x) f(Or(x,y) Or(f(x),f(y) and(Or(x,y),z) Or(and(x,z),and(y,z) and(z,Or(x,y) Or(and(z,x),and(z,y) and(x,y) And(x,y) not(Not(x) x not(And(x,y) Or(not(x),not(y) not(Or(x,y) and(not(x),not

24、(y) not(x) Not(x),Consquences,Il faut dfinir la congruence explicitement, pour chaque rgle et chaque constructeur Il ny a plus de sparation entre transformation et contrle cela rend la comprhension plus difficile les rgles sont moins rutilisables,Ce quon voudrait,pouvoir contrle lapplication des rgl

25、es pouvoir spcifier simplement le traverse dune terme (I.e. appliquer une rgles dans les sous-termes) tout en sparant rgle et contrle,Solution,Utiliser des stratgies Combiner des transformations lmentaires Exemples disjunctive normal form dnf = innermost(DAOL + DAOR + DN +) DAOL : And(Or(x,y),z) Or(

26、And(x,z),And(y,z) DAOR : And(z,Or(x,y) Or(And(z,x),And(z,y) DN : Not(Not(x) x conjunctive normal form cnf = innermost(DOAL + DOAR + DN +),Autres stratgies de traverse,simplify = bottomup(repeat(R1 + ) simplify = topdown(repeat(R1 + ) Slide 14,Stratgies en Tom,Constructeurs lmentaires,Identity Fail N

27、ot Sequence Choice All One Some IfThenElse Omega mu,Dfinition de stratgies,%op VisitableVisitor Try(s1:VisitableVisitor) make(v) Choice(v,Identity) %op VisitableVisitor Repeat(s1:VisitableVisitor) make(v) mu(MuVar(x),Choice(Sequence(v,MuVar(x),Identity() %op VisitableVisitor TopDown(s1:VisitableVisi

28、tor) make(v) mu(MuVar(x),Sequence(v,All(MuVar(x) %op VisitableVisitor OnceBottomUp(s1:VisitableVisitor) make(v) mu(MuVar(x),Choice(One(MuVar(x),v) %op VisitableVisitor Innermost(s1:VisitableVisitor) make(v) mu(MuVar(x),Sequence(All(MuVar(x), Try(Sequence(v,MuVar(x) ,Stratgie lmentaire en Tom,class R

29、ewriteSystem extends strategy.term.termVisitableFwd public RewriteSystem() super(Fail(); public Term visit_Term(Term arg) throws VisitFailure %match(Term arg) a() - return b(); b() - return c(); g(c(),c() - return c(); throw new VisitFailure(); ,Utilisations,VisitableVisitor rule = new RewriteSystem

30、(); Term subject = f(g(g(a,b),g(a,a); OnceBottomUp(rule).visit(subject); Innermost(rule).visit(subject); Repeat(OnceBottomUp(rule).visit(subject);,(mode paranoaque),VisitableVisitor rule = new RewriteSystem(); Term subject = f(g(g(a,b),g(a,a); VisitableVisitor onceBottomUp = mu(MuVar(x),Choice(One(M

31、uVar(x),rule); onceBottomUp.visit(subject); VisitableVisitor innermostSlow = mu(MuVar(y),Choice(Sequence(onceBottomUp,MuVar(y),Identity(); innermostSlow.visit(subject); VisitableVisitor innermost = mu(MuVar(x),Sequence(All(MuVar(x),Choice(Sequence(rule,MuVar(x),Identity); innermost.visit(subject);,Questions,Comment calculer des ensembles de rsultats Exemples f(g(g(a,b),g(a,b) trouver les x tels que g(x,b) filtre un so