Brevet FR2896358A1 — publié le 20070720

La présente invention concerne un procédé pour la transformation d'un document XML ("Extensible Markup Language") dans une autre forme, soit également en XML soit dans une forme complètement différente textuelle ou binaire. 15 Elle a plus particulièrement pour objet d'accélérer la transformation d'un document XML afin que celle-ci puisse être appliquée en ligne, le mécanisme de transformation pouvant être inséré dans le flux réseau, par exemple dans un serveur HTTP ("HyperText Transfer Protocol"). 20 Le mécanisme de transformation s'appuie sur "l'expression fonctionnelle" du document XML initial. Le mécanisme d'évaluation de l'expression peut être logiciel. Il peut également être micro programmé ou "câblé". Le langage XML apparaît aujourd'hui comme une classe de langage dont le 25 pouvoir d'expression est quasiment universelle ; il dispose de commandes étendues pour les mises en page et les éléments plus complexes ; son atout majeur est qu'il est extensible à souhait et qu'il peut donc être utilisé pour presque n'importe quel type de document. 30 La compatibilité entre le programme source et le programme cible est assurée par un fichier de définition spécifique (DTD : "Document Type Definition"). 1 Par conséquent, quand une application requiert un langage, deux choix se présentent: soit inventer un langage, spécifier sa grammaire puis développer un 5 analyseur syntaxique spécifique pour ce langage, soit spécifier une application du XML, c'est à dire spécifier un sous langage du XML au moyen de son fichier de définition spécifique. Parmi ces deux solutions, la seconde généralement est retenue car la structure 10 générale du XML est connue, par ailleurs il existe de multiples analyseurs syntaxiques qui valident le document XML au moyen de son fichier de définition spécifique. Toutefois, un document en XML, lorsqu'il doit être présenté ne l'est rarement 15 tel quel: il faut généralement le transformer afin de le rendre visualisable par exemple en HTML ("HyperText Markup Language"). Il existe des outils de transformation du XML tels que par exemple le processeur XSLT qui s'appuie sur des feuilles de style écrites en XSL 20 ("eXtended Style Sheet"). Il s'agit d'un système de réécriture d'arbre. D'une façon générale, on sait que la plupart des systèmes de transformations du XML actuellement disponibles sont très lents. Les causes de cette lenteur sont les suivantes : 25 • Le mécanisme général retenu pour la transformation du XML est un système de réécriture d'arbre. Ceci implique de parcourir plusieurs fois le document XML et d'y appliquer des règles de réécriture selon une priorité faisant l'objet d'une évaluation complexe. -3- Ce mécanisme doit être appliqué itérativement jusqu'à l'obtention d'un point fixe, c'est à dire d'un document pour lequel plus aucune règle de réécriture n'est applicable. • Dans le cas du XSL, Les règles de réécritures sont elles mêmes décrites en XML. Deux compilations XML successives doivent donc être effectuées: l'une concerne la feuille de style XSL c'est à dire les règles de réécriture, l'autre le document lui même. • Les programmes de réécriture sont généralement écrits en Java qui est un langage interprété. L'invention a donc plus particulièrement pour but de supprimer ces inconvénients. Elle propose, à cet effet, un procédé selon lequel le document XML tout entier est lui-même considéré comme sa propre expression de transformation. Selon l'invention, ce procédé est caractérisé en ce qu'il comprend les étapes 20 suivantes : la transformation du document XML en une seule et unique expression, ladite unique expression étant exprimée dans un langage d'expression fonctionnelle en notation préfixée, à chaque opérateur dudit document XML correspond une fonction, 25 l'analyse de la susdite unique expression afin de produire le document XML dans sa forme finale. Ce procédé présente donc l'avantage de permettre de : de compiler le document XML sous forme d'un programme dont 30 l'exécution génère le document dans sa forme finale,15 -4- de générer le document XML, transformé en une expression fonctionnelle, sous plusieurs formes finales qui dépendent uniquement de la machine utilisée pour évaluer cette expression fonctionnelle, - de décrire la transformation dans un langage d'expression fonctionnelle plus puissant que le XSL, et d'obtenir ainsi une plus grande efficacité du procédé de transformation selon l'invention. Avantageusement, le procédé de transformation selon l'invention permet d'obtenir des débits importants en micro-programmant, voire en câblant ledit 10 procédé de transformation. L'invention telle que précédemment définie, peut être notamment utilisée dans diverses applications, en effet : • le procédé de transformation peut être utilisé pour le rendu HTML 15 ("HTML rendition") d'un document ou d'une page Web initialement composée en XML (par exemple en "DocBook") ; dans ce cas, plusieurs qualités de HTML peuvent être produites en fonction des capacités d'affichage du navigateur, 20 • dans le cas d'un navigateur "WAP" (Wireless Application Protocol), le procédé permet de transformer le document en "WML" (Word Mark Language) ou encore en "CHTML" (Compact Hyper Text Markup Language) dans le cas d'un téléphone cellulaire "iMode". 25 • dans le cadre du "Web service", le procédé permet de transformer une requête XML en une requête compréhensible par le serveur de base de données. Par exemple, il peut transformer une requête "SOAP" (Simple Object Access Protocol) en "SQL*Net" via les "OCI" (Oracle Cali Interface) de "ORACLE". 30 - 5 • Le procédé peut également être utilisé pour accélérer le traitement des requêtes XML (par exemple SOAP) en facilitant l'analyse des analyseurs de syntaxe XML de l'application. Pour cela, il transforme le XML et le "tokenized" XML. L'analyseur de syntaxe de l'application peut alors être remplacé par un simple convertisseur de "tokenized" XML en événements "SAX"(Simple API for XML). Un mode d'exécution de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence au dessin annexé dans lequel : La figure unique représente une structure arborescente décrivant la composition et les caractéristiques d'un train comprenant une locomotive, un wagon citerne et un wagon porte conteneur. 15 On rappelle tout d'abord que le procédé selon l'invention consiste à transformer un document XML, par exemple celui illustré sur l'unique figure, en une seule et unique expression, ladite expression étant exprimée dans un langage d'expression fonctionnelle ; cette expression est ensuite analysée de manière à produire le document XML dans sa forme finale. 20 Le langage d'expression fonctionnelle retenu peut être : - soit le langage "LISP" ; dans ce cas le document XML est transformé en une seule expression LISP ; à chaque type de noeud du document XML correspond une fonction LISP qui décrit la transformation à lui 25 appliquée, soit un langage d'opérateurs post-fixés ; dans ce cas, l'expression peut être évaluée par une machine à pile qui peut être câblée, c'est à dire par un dispositif "hardware" très rapide. 30 Un document XML est équivalent à un arbre à N-aires. Chaque paire (balise ouvrante, balise fermante) définie un noeud de cet arbre. Ce noeud peut contenir soit du texte, soit d'autres paires de balises soit un mélange des deux. A titre d'exemple simple, un document XML est défini comme suit : electrique CC 7500 citerne 2 porte conteneur 4 Ce document XML peut être représenté sous la forme d'un arbre tel que montré sur l'unique figure. En effet, dans le cas présent, la composition du train et ses caractéristiques sont représentées sous la forme d'une multiplicité de noeuds No, NI, N2, N3, N4, N5, N6, N7, N8, N9, N10, qui représentent respectivement : 30 No : train ; NI : locomotive ; N2 : wagon citerne ; N3 : wagon porte conteneur ; N4 : énergie de la locomotive ; N5 : type de locomotive ; N6 : puissance de la locomotive ; N7 : charge du wagon citerne ; N8 : essieux du wagon citerne ; N9 : charge du wagon porte conteneur ; N10 : essieux du wagon porte conteneur. 15 20 25 35 -7- Chaque noeud est défini par une paire de balises, à savoir une balise ouvrante (par exemple : ) et une balise fermante (par exemple : ) concernant le noeud N1 "loco". Chaque noeud peut contenir soit du texte (blocs B1, B2, B3, B4, B5, B6, B7), soit d'autres paires de balises, soit un mélange des deux. Ainsi, dans l'exemple représenté sur l'unique figure, le noeud No "train" est en relation avec : le noeud N1 "loco" par l'intermédiaire de la liaison L0_1, le noeud N2 "wagon" par l'intermédiaire de la liaison LO.2, le noeud N3 "wagon" par l'intermédiaire de la liaison L0_3, d'autre part, le noeud N1 "loco" est en relation avec : le noeud N4 "énergie" par l'intermédiaire de la liaison L1.4, le noeud N5 "type" par l'intermédiaire de la liaison L1_5, le noeud N6 "puissance" par l'intermédiaire de la liaison L1.6, d'autre part, le noeud N2 "wagon" est en relation avec : le noeud N7 "charge" par l'intermédiaire de la liaison L2_7, le noeud N8 "essieux" par l'intermédiaire de la liaison L2_8, et d'autre part, le noeud N3 "wagon" est en relation avec : le noeud N9 "charge" par l'intermédiaire de la liaison L3_9, _ le noeud Nlo "essieux" par l'intermédiaire de la liaison L3_10, enfin : le noeud N4 "énergie" est en relation avec le bloc B 1 "électrique", le noeud N5 "type" est en relation avec le bloc B2 "CC", le noeud N6 "puissance" est en relation avec le bloc B3 "7500", - le noeud N7 "charge" est en relation avec le bloc B4 "citerne", le noeud N8 "essieux" est en relation avec le bloc B5 "2", le noeud N9 "charge" est en relation avec le bloc B6 "porte conteneur", et -le noeud N9 "essieux" est en relation avec le bloc B7 "4". L'équivalent fonctionnel de ce document est : train[3]loco[2]energie[1]"electrique"type[1] 5 "CC"puissance[1]"7500" wagon[2]charge[1]"citerne"essieux[1]"2"wagon[2] charge[1]"porte conteneur"essieux[1]"4" On voit que chaque noeud est transformé en un opérateur suivi de son arité 10 entre [] et des ses arguments. Les arguments de l'opérateur sont soit le résultat de l'évaluation d'opérateur soit du texte littéral. Cette notation fonctionnelle est équivalente à un programme exécuté par une machine. Pour chaque opérateur, cette machine évalue les arguments puis 15 passe les arguments à l'opérateur qui produit son résultat. Quand les arguments sont eux même produits par des opérateurs le même processus de calcul est relancé récursivement. En évaluant l'opérateur correspondant à la racine de l'arbre, c'est à dire le 20 premier opérateur du programme, on évalue ou exécute la totalité du document. L'algorithme est récursif : le même procédé de calcul est rappelé pour chaque opérateur : • Pour chaque argument (Parité est donnée pour chaque opérateur): • Si c'est une valeur littérale 25 • Installer la valeur au sommet de la pile des arguments • Incrémenter l'index de programme • Sinon (c'est un opérateur) • Incrémenter l'index de programme • Rappeler récursivement la machine pour cet opérateur 30 • Appeler l'opérateur avec son arité A. Celui-ci agit sur les A valeurs aux sommets de la pile d'arguments. • Dépiler A valeurs dans la pile d'arguments. • Empiler le résultat de l"'épateur". Pour la compréhension du procédé, est décrit ci-après l'algorithme de construction de l'arbre et de construction de l'expression. Si on considère les balises ouvrantes et fermantes comme des classes parenthèses, il apparaît que le XML est un langage de "Dick" très simple. Bien que pouvant contenir une liste d'attributs, une balise peut être considérée comme un "token" produit par l'analyse lexicale. La grammaire s'exprime en "BNF" (Backus Normal Form) de la manière suivante : • lement ::= balise *( texte J lement ) anti-balise L'analyse syntaxique du XML est donc réalisée par un automate à pile dont 15 l'algorithme est le suivant : 1. balise ouvrante: push 2. balise fermante: pop; shift 3. texte: shift 20 Tel qu'il est défini, l'algorithme d'évaluation de l'expression fonctionnelle du document XML au moyen de la machine décrite ci-dessus, les noeuds de l'arbre sont parcourus en profondeur d'abord. Dans certains cas, la construction d'un contexte d'évaluation pour chacun des opérateurs associés aux noeuds de l'arbre nécessite un parcours en hauteur d'abord. 25 Si à chaque noeud X et son opérateur associé de même nom X on associe un opérateur conjugué X* et si pour chaque noeud on remplace l'expression X[n] [An} par X [n + 1 ] X * [ O ] [An}, on obtient n double parcours en hauteur et en profondeur en une seule passe. 30 - 10 - Ainsi, l'originalité du procédé de transformation d'un document XML,selon l'invention, réside dans le fait que le document XML tout entier est lui-même considéré comme sa propre expression de transformation ; ce qui permet une plus grande efficacité du procédé de transformation et notamment la possibilité de décrire la transformation dans un langage fonctionnel plus puissant que le langage XSL. Revendications 1. Procédé pour la transformation d'un document XML, caractérisé en ce qu'il comprend les étapes suivantes : la transformation du document XML en une seule et unique expression, ladite unique expression étant exprimée dans un langage d'expression fonctionnelle en notation préfixée, à chaque opérateur dudit document XML correspond une fonction, l'analyse de la susdite unique expression afin de produire le document 10 XML dans sa forme finale. 2. Procédé selon la revendication 1, caractérisé en ce que la susdite analyse de l'expression fonctionnelle du document XML est effectuée en une seule passe selon un double parcours en 15 hauteur puis en profondeur au moyen d'un opérateur conjugué passé en argument fixé. 3. Procédé selon la revendication 1, caractérisé en ce que le susdit langage d'expression fonctionnelle retenu est le 20 langage "LISP" ; dans ce cas le document XML est transformé en une seule expression LISP ; à chaque type de noeud du document XML correspond une fonction LISP qui décrit la transformation à lui appliquée, 4. Procédé selon la revendication 1, 25 caractérisé en ce que le susdit langage d'expression fonctionnelle retenu est un langage d'opérateurs post-fixés. 5. Procédé selon la revendication 4, caractérisé en ce que dans le cas du susdit langage d'opérateurs post-fixés, la 30 susdite expression fonctionnelle est évaluée par une machine câblée.