Brevet FR2917865A1 — publié le 20081226

La présente invention concerne un procédé et un dispositif d'analyse d'une expression à évaluer, un procédé d'évaluation, un programme d'ordinateur et un support d'information. Elle vise, en particulier, à fournir une représentation efficace de requêtes XPath en vue de leur évaluation au fil de l'eau. XPath (contraction de XML Path Language pour langage de chemin pour XML) est une spécification du consortium W3C (acronyme de world wide web consortium pour consortium de la toile mondiale). Le but de cette spécification est de définir une syntaxe pour adresser des parties d'un document XML. Cette syntaxe utilise une notation similaire aux expressions de chemins dans un système de fichiers, (par exemple, dans l'exemple de document XML 300 et d'expressions 305 illustrés en figure 3, /bookstore/book ). XPath définit quatre types de données : chaîne , booléen , nombre et ensemble de noeuds ainsi que des expressions permettant de manipuler ces données (opérateurs = , != , ...). Un noeud XPath peut représenter différents types d'évènement XML : racine pour le début du document, élément, attribut, texte, commentaire, processinginstruction et namespace . Cette syntaxe sert de base à la formation de requêtes sur des documents en vue de leur transformation (XSL transformation ou XSLT ), d'accéder rapidement à des sous-parties ( XPointer ) ou d'effectuer des traitements sur des parties du document ( XQuery ). XPath a pour principal avantage de simplifier le développement d'applications appelées à naviguer dans des documents XML. L'entité responsable de l'évaluation d'une expression XPath est appelée Processeur XPath . Le processeur XPath accepte généralement comme entrées, d'une part, une ou plusieurs expressions XPath et, d'autre part, une référence sur des données XML (lues dans un fichier ou reçues via une transmission réseau) sur lesquelles la ou les expressions doivent être évaluées. Le paragraphe suivant décrit les caractéristiques de la spécification XPath 1.0 utiles à la bonne compréhension de l'invention. Il est à noter que la spécification de XPathl .0 est donnée ici à titre d'exemple pour faciliter la compréhension de l'invention. L'invention s'applique également avec d'autres versions de la syntaxe XPath, par exemple XPath 2.0. Comme mentionné dans l'introduction, XPath définit quatre types de données ainsi que sept types de noeuds. La syntaxe XPath définit également une grammaire décrivant les règles de construction des différentes expressions et sous-expressions. Les expressions XPath peuvent être regroupées en deux sous catégories que nous désignerons comme : - les Expressions de navigation : ce sont les expressions qui retournent une liste ordonnée de noeuds XPath, essentiellement les LocationPath et les Steps qui correspondent à la spécification d'un chemin à résoudre dans un document XML et - les Expressions de calcul : a. Expressions retournant un booléen OrExpr , AndExpr , RelativeExpr , EqualityExpr , b. Expressions retournant un nombre : AdditiveExpr , MultiplicativeExpr et c. Expressions retournant n'importe quel type : FilterExpr et en particulier les FunctionCall . L'invention s'intéresse essentiellement aux expressions composées des deux types de sous-expressions, par exemple un appel de fonction dont au moins un des paramètres est exprimé par une LocationPath . En ce qui concerne l'organisation des LocationPath (que l'on peut traduire par chemin de localisation ), une LocationPath peut-être absolue ou relative selon qu'elle commence par / ou non. Dans le cas d'une LocationPath absolue, la recherche commence depuis la racine du document alors que dans le cas de LocationPath relatives, la recherche est contextuelle (par exemple depuis le noeud courant). Toute LocationPath est composée de Steps (que l'on peut traduire par étapes de chemin ). Ce niveau de décomposition est le niveau clé pour l'évaluation des LocationPath car il peut être mis en correspondance avec un niveau de profondeur dans le document XML. Par exemple, en figure 3, l'expression /bookstore/book contient deux Steps qui sont : bookstore (recherché à la profondeur 1) et book (recherché à la profondeur 2). En ce qui concerne l'organisation des Step , l'évaluation d'un Step se fait conditionnellement au Step parent, c'est-à-dire le Step qui le précède dans l'expression. Le résultat de l'évaluation d'un Step fournit donc le contexte d'évaluation pour le Step suivant. Ce contexte est composé d'un noeud contexte, d'une position et d'une taille : le noeud contexte est le noeud solution du Step précédent, la position indique le rang du noeud solution du Step courant parmi ses frères, la taille du contexte indique le nombre de noeuds solution du Step courant. Toute expression de type Step est composée de une à trois entités parmi : - un AxisSpecifier , optionnel (qui vaut child par défaut), décrit la relation entre le noeud contexte et les noeuds solution du Step . L' AxisSpecifier est un mot-clé parmi treize qui sont prédéfinis par la syntaxe XPath, suivi de :: . Par exemple : /a/child ::b ou /a/attribute ::b signifient respectivement que l'on cherche un noeud b fils d'un noeud a et un noeud attribut b fils d'un noeud a . Les treize AxisSpecifier définis par la spécification sont les suivants : - self , child , attribute (ou @ ), namespace , descendant , descendant-or-self , following , et followingsibling , qui sont considérés comme des axes vers l'avant ( forward axes , en anglais) et - parent , ancestor , ancestor-or-self , preceding et preceding-sibling , qui sont considérés comme des axes vers l'arrière ( backward axes ou reverse axes , en anglais). - un NodeTest , obligatoire, définit la contrainte de type (node() , text() , comment() ou processing-instruction()) ou de nom (préfixe + nom) que doivent respecter des noeuds pour être considérés comme solution du Step . Par exemple, /child ::b impose une contrainte de nom alors que /descendant::comment() permet de rechercher tous les noeuds de type commentaire. - un Predicate (que l'on peut traduire par prédicat en français), optionnel, permet d'imposer des conditions supplémentaires pour la recherche de noeuds solutions. Une expression prédicat est signalée par des crochets : [...] et suit les mêmes règles de construction que toute expression XPath. Par exemple, /a/b[2] permet de sélectionner tous les deuxièmes fils b de chaque élément a ; /a/b[@id= 3 ] permet de sélectionner les fils b de a possédant un attribut id ayant une valeur égale à 3. Comme décrit ci-dessus, XPath permet d'accéder à des parties d'un document XML. Une implémentation simple d'un processeur XPath consisterait à construire une représentation intermédiaire du document XML sous une forme qui faciliterait la recherche, un arbre DOM (acronyme de document object model pour modèle objet de document) par exemple, et à parcourir cet arbre autant de fois que nécessaire pour l'extraction des noeuds demandés. Une telle approche pose un double problème. Tout d'abord, elle peut s'avérer coûteuse en mémoire dans le cas de documents XML de grande taille. En effet, considérant un processeur XPath implanté dans un appareil embarqué (type appareil photo, photocopieur ou autre) les ressources sont limitées. Il faut donc veiller à évaluer les expressions XPath au fur et à mesure que les données XML sont disponibles en recourant le moins possible au stockage de ces données. Le second problème réside dans les multiples parcours faits sur l'arbre à la recherche des solutions. Dans un contexte de traitements des données XML à la volée ( streaming environment en anglais), il n'est pas envisageable de parcourir plusieurs fois les données, surtout si ces données proviennent d'un échange de messages entre appareils communicant à travers un réseau (cas des services Web, c'est-à-dire de la toile, par exemple). Il convient donc de définir une représentation des expressions XPath de façon à préparer et à faciliter, d'une part, leur évaluation dans un cadre de réception des données XML à la volée et, d'autre part, l'émission des résultats à l'application aussitôt que ceux-ci sont disponibles. On trouve dans l'état de l'art des solutions permettant d'évaluer à la volée des expressions XPath de type expressions de navigation . Par exemple, le document US 7,171,407 décrit une représentation des expressions de navigation sous forme de graphe orienté acyclique. Dans cette représentation, chaque NodeTest des Step des LocationPath correspond à un sommet (ou noeud) du graphe, les AxisSpecifiers étant représentés par les arcs du graphe. Cette représentation a pour principal avantage d'organiser la recherche d'informations XML selon l'ordre du document. En effet, si des AxisSpecifiers de type parent ou ancêtre sont présents dans les LocationPath à évaluer, les NodeTest correspondants sont organisés exclusivement selon une relation de descendance, c'est-à-dire respectant l'ordre du document. Toutefois, si cette représentation s'avère intéressante pour des expressions XPath purement de navigation, elle ne permet pas d'aborder les expressions de type calcul, ou de type hybride (mixant expressions de navigations et de calcul). De plus, cette représentation impose de maintenir des structures de stockage pour les noeuds XPath solution du dernier Step de chaque LocationPath afin de déterminer a posteriori si ce noeud est une solution pour la LocationPath dans son ensemble, le temps de résoudre des prédicats ou de vérifier les AxisSpecifiers , par exemple. La présente invention vise à remédier à ces inconvénients. A cet effet, la présente invention vise, selon un premier aspect, un procédé d'analyse d'une expression XPath composée de sous-expressions à évaluer sur un document structuré, caractérisé en ce qu'il comporte : - une étape de classification des sous-expressions de ladite expression en un sous-ensemble comportant des sous-expressions de calcul et un sous-ensemble comportant des sous-expressions de navigation et - une étape de liaison de chaque sous-expression de navigation à la sous-expression de calcul qui l'utilise. Grâce à ces dispositions, on fournit une représentation des expressions XPath permettant de résoudre les deux limitations de l'art antérieur. En particulier, le procédé d'analyse objet de la présente invention permet de représenter une expression XPath dans une forme apte à être évaluée à la volée. L'analyse peut être réalisée une fois et l'évaluation peut être réalisée plusieurs fois sur l'expression analysée sans recourir à une nouvelle analyse. Par exemple, un processeur XSLT qui définit une stylesheet comprenant des expressions XPath peut, dans une première phase de compilation, lancer l'analyse des expressions XPath puis, dans une deuxième phase d'évaluation, lancer l'évaluation de ces expressions XPath. Il apparaît ainsi que tant que la stylesheet n'est pas éditée, l'évaluation peut s'appuyer sur les expressions XPath analysées, ce qui réduit le délai de traitement. Une autre application du procédé d'analyse objet de la présente invention concerne un analyseur d'expressions XPath qui donne une information sur la compatibilité d'expressions avec une approche d'évaluation à la volée. Cette analyse, dans un cadre applicatif XSLT, permet également de classifier les expressions dépendant du document XML pour leur résolution de celles dites statiques. Cet analyseur peut donc faire partie d'un compilateur XSLT, XQuery ou toute autre langage basé sur XPath, en vue d'optimiser le traitement des stylesheets . L'analyse a pour but d'isoler les parties de l'expression nécessitant des informations XML des parties de l'expression consistant en des calculs ou en des conversions de type et donc de proposer des représentations et des mécanismes d'évaluations permettant la résolution des premières au cours de la lecture du document structuré. Selon des caractéristiques particulières, l'étape de classification comporte une étape de structuration de chacun des sous-ensembles de sous-expressions. Cette structuration fournit une représentation réutilisable de l'expression et un support pour son évaluation. Selon des caractéristiques particulières, au cours de l'étape de structuration, on représente le sous-ensemble comportant des sous- expressions de calcul par un arbre d'évaluation et le sous-ensemble comportant des expressions de navigation par un arbre de navigation. Grâce à ces dispositions, on simplifie la répartition des résultats, par rapport à une approche représentant à la fois les sous expressions de type navigation et les sous expressions de type calcul dans une structure unique faite de cibles. Selon des caractéristiques particulières, au cours de l'étape de structuration, on constitue l'arbre de navigation avec des cibles de navigation compilées, structure permettant de représenter la recherche d'informations correspondant à ladite expression dans le document structuré, chaque cible de navigation compilée étant liée à une sous-expression de navigation de type LocationPath et à au moins un Step dans cette LocationPath . Ce lien facilite la répartition, l'exploitation et la transmission des résultats provenant du document structurés. Selon des caractéristiques particulières, au cours de l'étape de structuration, chaque entité de type NodeTest de chaque Step est associée à au moins une cible de navigation compilée. Ce partage des NodeTest communs à une ou plusieurs cibles de navigation compilées permet de réduire le nombre de tests à effectuer lors de l'évaluation. De plus la représentation de l'expression s'en trouve plus compacte. Selon des caractéristiques particulières, au cours de l'étape de structuration, au cours de l'étape de structuration, on détermine si une cible de navigation compilée courante appartient à un nouveau chemin absolu ou relatif et, si oui, on crée une nouvelle branche dans l'arbre de navigation. Grâce à ces dispositions, on garantit, dans la représentation, la relation unique entre une sous expression de navigation et son expression de type calcul. Selon des caractéristiques particulières, au cours de l'étape de structuration, on détermine si la cible de navigation compilée courante appartient à un nouveau chemin absolu ou relatif et, si oui, on crée une structure de représentation d'une LocationPath comme nouvelle feuille de l'arbre d'évaluation, cette structure de représentation assurant le lien entre la branche courante de l'arbre d'évaluation et la nouvelle branche de l'arbre de navigation. Ce lien permet la transmission directe et automatique d'un résultat issu du document structuré vers l'expression de type calcul qui l'utilise. Selon des caractéristiques particulières, le procédé d'analyse objet de la présente invention tel que succinctement exposé ci-dessus comporte une étape de création d'une cible d'évaluation associée à la cible de navigation compilée courante, ladite cible d'évaluation comportant des informations représentant un statut d'évaluation, une éventuelle solution rencontrée lors de l'évaluation et un lien entre la cible d'évaluation et la cible de navigation compilée courante. Selon des caractéristiques particulières, dans le cas de LocationPath dont au moins un Step contient au moins un prédicat, l'arbre d'évaluation descend jusqu'à l'entité Step afin de relier la sous-expression correspondant au prédicat à sa sous-expression parente, la cible compilée étant insérée au début de cette nouvelle branche et un lien de cette cible compilée vers la LocationPath dont elle est issue est mis à jour ainsi qu'un type associé à cette cible compilée indiquant qu'elle représente le premier Step du chemin. Selon des caractéristiques particulières, au cours de l'étape de classification, on réalise des simplifications sur l'arbre d'évaluation. Grâce à ces dispositions, on conserve une représentation moins coûteuse en occupation mémoire que l'arbre avant simplification. Par exemple, ComparisonExpr permet de regrouper les sous-expressions de calcul de haut niveau comme un seul noeud dans l'arbre d'évaluation. De même, PurePathExpr permet de court-circuiter les différentes sous-expressions de calcul lorsque l'on identifie une sous-expression XPath comme constituée uniquement d'une sous-expression de navigation. PureFCall permet également de court-circuiter les différentes sous-expressions de calcul lorsque l'on identifie une sous-expression XPath comme constituée uniquement d'une sous-expression correspondant à une FunctionCall . ExprResult correspond aux cas où une sous-expression est résolue dès la compilation (cas de Literai ou Number ), auquel cas l'arbre d'évaluation se limite à un noeud qui porte un résultat. Selon des caractéristiques particulières, au cours de l'étape de classification, on effectue une étape d'analyse grammaticale au cours de laquelle un analyseur sémantique parcourt la liste de symboles des expressions et identifie les types d'expression définis par la syntaxe liée au langage XPath contenus dans l'expression à analyser. Selon des caractéristiques particulières, au cours de l'étape d'analyse grammaticale, pour au moins un symbole issu d'une analyse lexicale, on détermine, règle de grammaire par règle de grammaire, si le symbole répond à ladite règle. Selon des caractéristiques particulières, au cours de l'étape d'analyse grammaticale, si le symbole répond à une règle, on détermine si ladite règle est liée à une sous-expression de navigation et, si oui, on construit une sous-expression de navigation et, sinon, on construit une sous-expression de calcul. Selon des caractéristiques particulières, au cours de l'étape de classification, on détermine si une sous-expression peut contenir d'autres sous-expressions et, si oui, la représentation de chaque dite sous-expression comporte une référence à un lien de parenté avec au moins une autre sous-expression. Selon des caractéristiques particulières, au cours de l'étape de classification, on met en oeuvre une structure de représentation générique pour différents types de sous-expressions de calcul. Ceci évite une structure de représentation par sous-expression telle que décrit dans la grammaire, réduisant ainsi l'arbre d `évaluation. De plus, cela permet de regrouper plusieurs sous-expressions en une seule structure de représentation. Par exemple, les sous-expressions de type AndExpr , OrExpr , EqualityExpr , RelationalExpr , AdditiveExpr , MultiplicativeExpr et UnaryExpr peuvent être représentées par une sous-expression générique de type ComparisonExpr qui consiste à appliquer un opérateur sur une ou deux opérandes. La présente invention vise aussi un procédé d'évaluation sur un document structuré en langage de balisage, sur un document structuré en langage de balisage, caractérisé en ce qu'il met en oeuvre le procédé d'analyse d'expression tel que succinctement exposé ci-dessus et comporte une étape d'évaluation de l'expression mettant en oeuvre l'évaluation des sous-expressions de navigation de l'expression sur des données du document structuré. Ainsi, l'invention fournit un moyen d'évaluer des expressions XPath à la volée par une analyse de ses expressions pour distinguer la partie calculatoire de la partie dépendant de données XML, tout en préservant le lien entre ces deux parties en vue des transmissions de résultats et en limitant leur stockage. Les avantages pouvant découler de ces dispositions comportent : - une grande efficacité puisque le parcours du document XML est unique, -l'émission des résultats dès qu'ils sont calculés, - le traitement simple des noeuds XML résultats avec un stockage 20 minimum, - l'évaluation efficace du fait de la factorisation de calculs tels que les NodeTest et de la résolution a priori des AxisSpecifiers , - l'évaluation est effectuée sans forcément parcourir complètement le document XML (contrôle de l'exécution depuis l'arbre d'évaluation), 25 - l'analyse est réutilisable, la représentation interne calculée une fois peut être évaluée plusieurs fois sur le même document ou sur des documents différents et - le support d'expression combine des appels de fonction ou des opérations avec des expressions purement de navigation. 30 Selon des caractéristiques particulières, au cours de l'étape d'évaluation de l'expression XPath, on évalue au moins une sous-expression de calcul et une sous-expression de navigation selon les étapes suivantes : - lancement de l'exécution des sous-expressions de calcul en récupérant, depuis un arbre d'évaluation représentant le sous-ensemble comportant des sous-expressions de calcul, une expression de calcul dite racine et en parcourant des noeuds dits fils jusqu'à atteindre toutes les feuilles de l'arbre d'évaluation, - parcours du document structuré pour construire au moins un résultat pour chaque sous-expression de navigation associée à une sous-expression de calcul feuille de l'arbre d'évaluation, -transmission de chaque résultat de chaque sous-expression de navigation à la sous-expression de calcul associée, et, itérativement jusqu'à atteindre la sous-expression de calcul racine de l'arbre d'évaluation : application d'un traitement lié à la sous-expression de calcul sur le résultat, - au cas où la sous-expression de calcul est un noeud fils, propagation du résultat dudit traitement à la sous-expression de calcul parente. Selon des caractéristiques particulières, au cours de l'étape de propagation, si la sous-expression de calcul parente possède au moins une sous-expression de calcul n'ayant pas encore subi l'étape d'application de traitement, l'itération est suspendue jusqu'à ce que chaque dite sous-expression de calcul fille subisse ladite étape d'application de traitement. Selon un deuxième aspect, la présente invention vise un dispositif d'analyse d'une expression XPath composée de sous-expressions à évaluer sur un document structuré, caractérisé en ce qu'il comporte : - un moyen de classification des sous-expressions de ladite expression en un sous-ensemble comportant des sous-expressions de calcul et un sous-ensemble comportant des sous-expressions de navigation et - un moyen de liaison de chaque sous-expression de navigation à la sous-expression de calcul qui l'utilise. Selon un troisième aspect, la présente invention vise un programme d'ordinateur chargeable dans un système informatique, ledit programme contenant des instructions permettant la mise en oeuvre du procédé d'analyse tel que succinctement exposé ci-dessus. Selon un quatrième aspect, la présente invention vise un support d'informations lisibles par un ordinateur ou un microprocesseur, amovible ou non, conservant des instructions d'un programme informatique, caractérisé en ce qu'il permet la mise en oeuvre du procédé d'analyse tel que succinctement exposé ci-dessus. Les avantages, buts et caractéristiques de ce procédé d'évaluation, de ce dispositif, de ce programme et de ce support d'information étant similaires à ceux du procédé d'analyse objet de la présente invention, tel que succinctement exposé ci-dessus, ils ne sont pas rappelés ici. D'autres avantages, buts et caractéristiques de la présente invention ressortiront de la description qui va suivre, faite, dans un but explicatif et nullement limitatif en regard des dessins annexés, dans lesquels : - la figure 1 représente, schématiquement, le contexte d'application d'un mode de réalisation de la présente invention, - la figure 2 représente, schématiquement, un mode de réalisation particulier du dispositif objet de la présente invention, - la figure 3 représente un document XML et des expressions et - les figures 4 à 7 représentent, sous forme de logigrammes, des étapes mises en oeuvre dans un mode de réalisation particulier du procédé objet de la présente invention, - les figures 8 à 10 représentent, schématiquement, chacune, un arbre d'évaluation mis en oeuvre dans des modes de réalisation particuliers de la présente invention et - les figures 11 à 15 représentent, sous forme de logigrammes, des étapes mises en oeuvre dans un mode de réalisation particulier du procédé objet de la présente invention. La figure 1 décrit le contexte applicatif de l'invention proposée. Le scénario typique d'utilisation de la présente invention implique une application 101 manipulant des données XML extraites par un ou plusieurs processeurs XPath 102 grâce à un ou plusieurs analyseurs (ou navigateur) XML 103 ( parser en anglais) travaillant sur un flux de données XML 104. Le processeur XPath comprend comme entités principales : - un compilateur 121 qui analyse les expressions et les traduit en une représentation interne, décrit en référence à la figure 4. Celui-ci est composé de deux analyseurs, l'un lexical 111, l'autre sémantique 112 ; -une unité de contrôle d'exécution 122 qui gère la communication avec l'application, les interactions entre les différents modules et prend en charge l'évaluation des noeuds. Il est notamment composé d'une entité 124 responsable de la résolution des étapes composant les sous-expressions de navigation appelé gestionnaire de cibles et - un navigateur 123 qui permet au contrôleur d'exécution de communiquer de façon générique avec n'importe quel analyseur XML 103 et de représenter et de mémoriser les évènements XML sous forme de noeuds XPath dans un contexte de navigation 131. Les principales étapes de l'évaluation d'une expression XPath sont, d'une part, son analyse en vue de sa compilation, puis son évaluation. La mise en oeuvre de la présente invention est le fait du ou des processeurs XPath 102. La figure 2 illustre un mode de réalisation particulier du dispositif objet de la présente invention. Ce dispositif 201, par exemple un micro-ordinateur et ses différents périphériques, comporte une interface de communication 218 reliée à un réseau de communication 202 apte à transmettre et à recevoir des données numériques. Le dispositif 201 comporte également un moyen de stockage 214, tel que par exemple un disque dur. Il comporte aussi un lecteur de disquette 215. La disquette 224 peut contenir des données XML à traiter ainsi que le code d'un programme implémentant la présente invention, code qui, une fois lu par le dispositif 201, est stocké dans le disque dur 214. Selon une variante, le programme permettant au dispositif de mettre en oeuvre la présente invention, est stocké en mémoire morte 210 (appelée ROM, acronyme de read only memory ). En seconde variante, le programme pourra être reçu pour être stocké de façon identique à celle décrite précédemment par l'intermédiaire du réseau de communication 202. Le dispositif 201 possède un écran 212 permettant de visualiser les résultats des évaluations. A l'aide du clavier 213, l'utilisateur peut spécifier une expression XPath. L'unité centrale 211 (appelée CPU , acronyme de central processing unit , sur le dessin) exécute les instructions relatives à la mise en oeuvre de l'invention, instructions stockées dans la mémoire morte 210 ou dans les autres éléments de stockage. Lors de la mise sous tension, les programmes relatifs à l'évaluation d'expressions XPath et d'extraction des évènements XML stockés dans une mémoire non volatile, par exemple la ROM 210, sont transférés dans la mémoire vive RAM 217 qui contient alors le code exécutable de l'invention ainsi que des registres pour mémoriser lesvariables nécessaires à la mise en oeuvre de l'invention. Bien entendu, les disquettes 224 peuvent être remplacées par tout support d'information tel qu'un disque compact ou une carte mémoire. De manière plus générale, un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé objet de la présente invention. Le bus de communication 221 permet la communication entre les différents éléments inclus dans le micro-ordinateur 201 ou reliés à lui. La représentation du bus 221 n'est pas limitative et, notamment, l'unité centrale 211 est susceptible de communiquer des instructions à tout élément du micro-ordinateur 201 directement ou par l'intermédiaire d'un autre élément du micro-ordinateur 201. Le mode de réalisation particulier du procédé objet de la présente invention décrit en regard des figures 4 à 15 consiste, par une analyse de l'expression XPath à évaluer, à classifier les sous-expressions de cette expression en deux sous ensembles de sous-expressions : un sous-ensemble des expressions de type calcul (appelées, dans la suite de la description, expressions de calcul ) et un sous-ensemble des expressions de type navigation (appelées, dans la suite de la description, expressions de navigation ). Ensuite, pour chaque sous-ensemble de sous-expressions, une structure de représentation adaptée est créée. Un arbre d'évaluation représente le sous-ensemble de sous-expressions de type calcul tandis qu'un arbre de navigation représente le sous ensemble des sous-expressions de type navigation. De plus, chaque sous-expression de navigation est reliée à la sousexpression de type calcul qui l'utilise, afin de faciliter la propagation et le calcul des résultats. Enfin, les noeuds de l'arbre de navigation servent de support à l'évaluation des sous-expressions de navigation sur des données XML reçues à la volée. La figure 4 illustre des étapes mises en oeuvre lors de l'évaluation d'une expression XPath. L'expression XPath à évaluer peut, sans que ce soit limitatif, être spécifiée par un utilisateur ou bien être pré-stockée dans un fichier lu par l'application ou encore résulter de l'exécution au niveau de l'application d'un programme générant des requêtes XPath. Cette expression est reçue par le processeur XPath 102 lors de l'étape 441. Puis, au cours de l'étape 442, on analyse, un à un, les caractères qui représentent l'expression XPath et on les regroupe en symboles ( tokens en anglais). Ces symboles peuvent représenter des symboles réservés, propres à la spécification, comme, par exemple, le caractère / ou le symbole :: , ou des digits (compression de digital units pour unités numériques) ou des caractères simples. L'étape 442 est effectuée par l'analyseur lexical 111, qui dispose d'une table de symboles prédéfinis en fonction de la grammaire XPath 1.0. A la suite de la décomposition en symboles effectuée au cours de l'étape 442, au cours d'une étape 443, on teste les symboles générés. Si, au cours de cette étape 443, un des symboles est analysé comme non permis ou inconnu par l'analyseur lexical 111, le compilateur 121 arrête le traitement et informe le processeur XPath 102 de la non-conformité de l'expression, lors d'une étape 449. L'expression ne peut donc pas être évaluée. Dans une variante, on ignore le symbole non reconnu et on poursuit la compilation. Si l'analyseur lexical 111 détermine, au cours de l'étape 443, que l'ensemble des symboles considérés sont valides, on passe à une étape 444 d'analyse grammaticale. Cette étape 444 consiste, pour l'analyseur sémantique 112, à parcourir la liste de symboles issus de l'étape 442 et à identifier les types d'expression définis par la syntaxe XPath 1.0 (voir la table ci-dessous) et contenus dans l'expression à compiler. Dans la colonne de droite de ce tableau sont identifiés les niveaux introduits par l'invention afin de compacter l'arbre d'évaluation. Type de Type Type d'expression résultat ou sous- Règle de construction simplifié expression Non OrExpr Expr :._ déterminé Booléen OrExpr :._ AndExpr I Comparis OrExpr 'or' AndExpr onExpr Booléen AndExpr :._ EqualityExpr I AndExpr 'and' EqualityExpr Booléen EqualityExpr ::= RelationalExpr I EqualityExpr '=' RelationalExpi EqualityExpr RelationalExpr Booléen RelationalExpr ::= AdditiveExpr 1 RelationalExpr ' Sinon, l'évaluation se poursuit en fonction de données XML, lors d'une étape 448 décrite en référence à la figure 11. La figure 5 illustre des étapes d'une analyse sémantique d'une expression XPath, qui détaillent l'étape 444 de la figure 4. Ces étapes visent à : - identifier dans l'expression XPath à évaluer les sous-expressions de type calcul, -identifier dans l'expression XPath à évaluer les sous-expressions de navigation, - structurer le sous-ensemble des sous-expressions de calcul, par exemple en construisant un arbre d'évaluation représentant l'ensemble des sous-expressions de calcul, - structurer le sous-ensemble des sous-expressions de navigation, par exemple en construisant un arbre de navigation représentant l'ensemble des sous-expressions de navigation, -relier chaque branche de l'arbre de navigation à une feuille de l'arbre d'évaluation et - initialiser un arbre d'évaluation de l'ensemble des sous-expressions de navigation. Un exemple de représentation selon de telles étapes est donné en figure 8 : l'arbre d'évaluation 860 est relié à l'arbre de navigation 862 par les liens 861 et 863. L'arbre d'évaluation 860 est composé d'un appel de fonction 864 comprenant quatre paramètres 865 à 868. La grammaire XPath indique qu'un appel de fonction ( FunctionCall ) peut accepter zéro, un ou plusieurs paramètres, ces paramètres étant n'importe quel type d'expression XPath ( Expr ). Dans l'exemple fourni, la fonction appelée est la fonction concat qui permet de concaténer des chaînes de caractères. Cette fonction peut accepter un nombre de paramètres supérieur ou égal à 2. Dans l'exemple, elle contient 4 paramètres représentés par des expressions de différents types. Ces expressions se trouvant comme composant une autre expression, sont désignées comme sous-expressions. L'arbre de navigation 862 est, quant à lui, composé de cibles de navigation compilées (CNCij) où i est lié à une sous-expression de type LocationPath et j est l'indice du Step dans cette LocationPath . Les différents arbres construits par l'analyseur sémantique 112 le sont selon une approche ascendante ( bottom-up en anglais), comme connu de l'homme du métier, par exemple de Compilateurs : Principes, techniques et outils par Alfred Aho, Ravi Sehti et Jeffrey UlIman, Editions Dunod, 2000 : les feuilles de l'arbre d'évaluation sont construites en premier puis rassemblées au cours du parcours des symboles issus de l'analyse lexicale en 442. En regard de la figure 5, on détaille maintenant la mise en oeuvre de ces différentes étapes au sein de l'analyseur sémantique 112. Celui-ci dispose de la liste de symboles 500 construits par l'analyseur lexical 111 lors de l'étape 442 et validés lors de l'étape 443 ainsi que de la grammaire XPath détaillée dans le premier tableau ci-dessus. Au cours d'une étape 501, l'analyseur sémantique 112 récupère le premier symbole de la liste 500. Ensuite, au cours d'une étape 502, la règle courante à considérer par l'analyseur sémantique est initialisée à la première règle de la grammaire XPath (dans le premier tableau ci-dessus, il s'agit d'un élément de la deuxième colonne. Le symbole courant est également initialisé, au cours d'une étape 503, avec la valeur du premier symbole lu à l'étape 501. Au cours d'une étape 504, l'analyseur sémantique 112 détermine si le symbole courant répond à une (ou aux) règle(s) de construction de la règle courante. Par exemple, si le premier symbole correspond à la première règle identifiée sera la règle de construction associée à une AbbreviatedLocationPath . Si ce n'est pas le cas, l'analyseur sémantique 112 détermine, au cours d'une étape 507, s'il reste des règles à considérer et, si oui, il considère comme règle courante la règle suivante dans la grammaire, au cours d'une étape 508. A cet effet, l'analyseur sémantique 112 maintient une pile des sous-expressions rencontrées qui correspondent aux types de règles traversées, la sous-expression en haut de la pile se trouve être la dernière lue. Si, au cours de l'étape 504, l'analyseur sémantique 112 détermine que le symbole courant intervient dans une des constructions associées à la règle courante, l'analyseur détermine si cette règle courante est liée à une sous-expression de navigation, lors d'une étape 505. Si oui, l'analyseur sémantique 112 effectue une étape 506 de construction d'une sous-expression de navigation, comme décrit en regard de la figure 7. Sinon, l'analyseur sémantique 112 passe à la construction d'une sous-expression de calcul, comme exposé en regard de la figure 6, au cours d'une étape 509. Lorsque toutes les règles ont été parcourues, c'est-à-dire lorsque le résultat de l'étape de test 507 est négatif, sans que le symbole courant ne puisse être mis en correspondance avec la règle, une erreur est détectée, ce qui conduit à une expression non valide lors de l'étape 445. A la suite des étapes 506 ou 509 de construction de sous-expressions, de type navigation ou calcul, respectivement, l'analyseur sémantique 112 détermine s'il reste un symbole à analyser, au cours d'une étape 510 et, si oui, passe au symbole suivant et retourne à l'étape 503. S'il ne reste pas de symbole à analyser, la construction de sous-expressions est achevée. La figure 6 illustre le traitement d'une expression de calcul, au cours de l'étape 509. On considère donc ici que la règle courante identifiée au cours de l'étape 504, à laquelle correspond le symbole courant, correspond à une règle de construction qui n'est pas relative à des sous-expressions de navigation, le résultat du test 505 étant négatif, c'est-à-dire qu'elle n'est pas présente dans le deuxième tableau ci-dessus. Dans ce cas, une représentation de la sous-expression associée à cette règle est créée. A chaque type de sous- expression de calcul définie par la grammaire XPath est associée une structure de représentation qui comprend au moins: - le type de la sous-expression, - un statut d'évaluation ( à lancer , en cours de traitement ou terminé ), - un éventuel lien vers une sous-expression parente, - des liens vers la ou les sous-expressions qui la composent, - une suite d'instructions nécessaires à son évaluation et -une suite d'instructions nécessaires au traitement et à la propagation d'un résultat qui lui parvient. L'étape 509, détaillée en figure 6, consiste, pour l'analyseur sémantique 112, à construire une structure de ce type. Au cours d'une étape 601, on identifie la sous-expression associée à la règle de construction identifiée à l'étape 504 et on crée une structure de représentation telle que décrite ci-dessus. Lors d'une étape 602, la sous-expression ainsi créée est insérée dans l'arbre d'évaluation en tant que feuille de l'arbre. Elle devient la sous-expression courante pour l'analyseur sémantique 112 lors d'une étape 603. L'analyseur sémantique 112 détermine alors s'il s'agit d'une règle terminale, lors d'une étape 604, en déterminant si la sous-expression courante peut elle-même contenir d'autres sous-expressions (par exemple une FunctionCall avec Arguments) ou non (par exemple une FunctionCall sans Arguments ou une VariableReference ). Si oui, l'étape de construction 509 est achevée. Sinon, l'analyseur sémantique 112 détermine, pour la sous-expression courante, s'il y a une ambiguïté quant à sa sous-expression parente ou non, au cours d'une étape 605. S'il existe une telle ambiguïté, l'étape 509 se termine. S'il n'y a pas d'ambiguïté, par exemple une FunctionCall ne peut découler que d'une PrimaryExpr qui ne peut découler elle-même que d'une FilterExpr , au cours d'une étape 606, l'analyseur sémantique 112 récupère depuis sa pile la sous-expression parente et la retire de la pile. L'analyseur sémantique 112 crée, pour cette sous-expression parente, une représentation au cours de l'étape 606. Puis, au cours d'une étape 607, on crée un lien de parenté de la sousexpression courante vers la sous-expression parente. De même, le lien de filiation de la représentation de la sous-expression parente est initialisé vers la représentation de la sous-expression courante, au cours d'une étape 608. On note que ces étapes 607 et 608 reviennent à l'insertion de la sous-expression parente créée en tant que noeud parent de la sous-expression courante, dans l'arbre d'évaluation. Puis, on retourne à l'étape 603 au cours de laquelle la dernière sous-expression créée devient la sous-expression courante jusqu'à ce que toutes les sous-expressions de la pile de sous-expressions de l'analyseur sémantique 112 aient été dépilées. Selon un mode préféré de réalisation, l'analyseur sémantique 112 utilise une structure de représentation générique pour différents types de sous- expressions de calcul. Ceci évite une structure de représentation par sous-expression telle que décrit dans la grammaire, réduisant ainsi l'arbre d'évaluation. De plus, cela permet de regrouper plusieurs sous-expressions en une seule structure de représentation. Par exemple les sous-expressions de type AndExpr , OrExpr , EqualityExpr , RelationalExpr , AdditiveExpr , MultiplicativeExpr et UnaryExpr peuvent être représentées par une sous-expression générique de type ComparisonExpr qui consiste à appliquer un opérateur sur une ou deux opérandes. Dans ce mode préféré de réalisation, l'analyseur sémantique 112 se réfère à la colonne de droite de la grammaire ( Type simplifié ) décrite dans le premier tableau ci-dessus. Cette colonne montre les simplifications possibles sur l'arbre d'évaluation : - ComparisonExpr permet de regrouper les sous-expressions de calcul de haut niveau comme un seul noeud dans l'arbre d'évaluation, - PurePathExpr permet de court-circuiter les différentes sous-expressions de calcul lorsque l'analyseur sémantique 112 identifie une sous-expression XPath comme constituée uniquement d'une sous-expression de navigation, - PureFCall permet également de court-circuiter les différentes sous-expressions de calcul lorsque l'analyseur sémantique 112 identifie une sous-expression XPath comme constituée uniquement d'une sous-expression correspondant à une FunctionCall et - ExprResult correspond aux cas où une sous-expression est résolue dès la compilation (cas de Literai et Number ). Dans ce cas particulier, l'arbre d'évaluation se limite à un noeud qui porte un résultat. La figure 9 illustre un arbre d'évaluation considérant toutes les sous-expressions de la grammaire. Sa simplification selon les règles énumérées ci- dessus conduit à l'arbre d'évaluation de la figure 10. Il apparaît clairement que le nombre de niveaux à traverser, aussi bien pour le lancement de l'exécution que pour la remontée et le traitement des résultats, est nettement réduit par ces simplifications. En ce qui concerne les expressions de navigation, la construction de leur représentation est détaillée en regard de la figure 7. On considère ici que la règle de construction courante identifiée au cours de l'étape 504 comme correspondant au symbole courant, correspond à une règle de construction relative à une sous-expression de navigation. Cela peut être le cas par exemple pour un symbole / , . , .. ou // ou tout autre symbole permettant d'identifier le début d'une sous-expression de navigation (essentiellement un Step et les sous-expressions du deuxième tableau donné ci-dessus). Dans ce cas, l'analyseur sémantique 112 signale, lors de l'étape 506, au contrôleur d'exécution qu'une nouvelle sous-expression de navigation sera à évaluer. Durant cette étape, l'analyseur sémantique 112 prépare ou met à jour l'arbre de navigation de la façon suivante. Au cours d'une étape 700, l'analyseur sémantique 112 crée une cible de navigation compilée, structure permettant de représenter la recherche d'informations XML associée à un Step . La cible de navigation compilée contient au moins : - un lien vers la LocationPath dont elle est issue, - un type indiquant si la cible concerne un prédicat ou non et si elle est la première ou non dans sa LocationPath , - un lien vers la cible correspondant au Step suivant dans la LocationPath , - une information sur l' AxisSpecifier du Step qu'elle représente et - une information sur le NodeTest à vérifier pour le Step qu'elle représente ; et - éventuellement, une liste de prédicats associés au Step qu'elle représente. Concernant l'information sur le NodeTest , cette entité est présente dans une chaque expression de type Step . Dès qu'un Step est identifié, au cours de l'étape 505, son NodeTest associé est extrait par l'analyseur sémantique 112. L'analyseur sémantique 112 détermine, dans une pile de NodeTest , telle qu'illustrée en 869 en figure 8, si le dernier NodeTest rencontré est déjà présent ou non. S'il est déjà présent, l'information sur le NodeTest de la cible en cours de construction est reliée à ce NodeTest . Sinon, le dernier NodeTest rencontré est inséré dans la pile de NodeTest 869 et l'information sur le NodeTest de la cible en cours de construction est reliée à ce dernier. Ceci permet à plusieurs cibles de navigation compilées de correspondre à un même NodeTest . Puis, au cours d'une étape 701, on détermine si la cible de navigation appartient à un nouveau chemin absolu ( AbsoluteLocationPath ), ce qui revient à tester si le symbole courant est égal à / ou à // . Si c'est le cas, au cours d'une étape 702, l'analyseur sémantique 112 crée une nouvelle branche dans l'arbre de navigation, ce qui revient à créer une structure de représentation d'une LocationPath et l'insère comme nouvelle feuille de l'arbre d'évaluation. C'est cette structure de représentation qui assure le lien entre la branche de l'arbre d'évaluation et la branche de l'arbre de navigation. Dans le cas de LocationPath dont au moins un Step contient un ou plusieurs prédicats, l'arbre d'évaluation descend jusqu'à l'entité Step afin de relier la sous-expression correspondant au prédicat à sa sous-expression parente. A la suite à cette création, la cible de navigation est insérée au début de cette nouvelle branche, lors d'une étape 703, et son lien vers la LocationPath dont elle est issue est mis à jour ainsi que son type indiquant qu'elle représente le premier Step du chemin. Une cible d'évaluation associée à la cible de navigation courante est alors créée par le gestionnaire de cibles 124, lors d'une étape 704. Cette cible d'évaluation comporte essentiellement des informations représentant un statut d'évaluation et les éventuelles solutions rencontrées lors de l'évaluation. Le lien entre la cible d'évaluation et la cible de navigation compilée est conservé dans la cible d'évaluation, au cours d'une étape 705. Finalement, cette cible d'évaluation est insérée dans la première liste de cibles de la pile de cibles d'évaluation du gestionnaire de cibles 124, lors de l'étape 706. Puis on retourne à l'étape 510. Si, au cours de l'étape 701, on détermine que la cible de navigation n'appartient pas à un nouveau chemin absolu, au cours d'une étape 707, on détermine si la cible de navigation appartient au début d'un chemin relatif, c'est-à-dire d'une nouvelle LocationPath , ou si la cible de navigation appartient à un nouveau Step dans la LocationPath courante. L'ambiguïté est levée par le contexte de l'analyseur sémantique 112 qui sait s'il se trouve déjà dans la construction d'une LocationPath ou non. Si la cible de navigation appartient au début d'un chemin relatif, une représentation de la nouvelle LocationPath est créée, au cours d'une étape 708, et devient la LocationPath courante pour l'analyseur sémantique 112. Puis, au cours d'une étape 709, on détermine si l'arbre de navigation contient déjà une branche ou pas. Si l'arbre de navigation ne contient pas de branche, au cours d'une étape 710, on crée une cible de navigation dite racine . Puis, au cours d'une étape 711, une nouvelle branche de navigation est créée. Sur cette nouvelle branche, sont insérées, au cours d'une étape 712, les deux cibles créées respectivement lors de l'étape 710 et 700. Puis, au cours d'une étape 713, une cible d'évaluation correspondant à la cible racine est créée et insérée dans la première liste de cibles de la pile de cibles du gestionnaire de cibles 124. Cette cible est reliée à la cible racine lors d'une étape 714. Puis, on passe au symbole suivant et on retourne à l'étape 504. Si on détermine, au cours de l'étape 707 que la cible de navigation appartient à un nouveau Step dans la LocationPath courante, c'est-à- dire que ce n'est pas le premier Step dans cette LocationPath , ou Si on détermine, au cours de l'étape 709 que l'arbre de navigation contient déjà une branche, au cours d'une étape 715, l'analyseur sémantique 112 insère la cible de navigation compilée créée à l'étape 700 dans la branche de navigation courante. Puis, au cours d'une étape 716, la cible nouvellement insérée est reliée à la cible qui la précède sur la branche et on met à jour le lien de cette cible précédente vers la cible nouvellement insérée. Puis, on passe au symbole suivant et on retourne à l'étape 504. L'évaluation d'une expression XPath se déroule en deux étapes, respectivement décrites en regard des figures 11 et 12. La première étape, illustrée en figure 11, consiste à lancer l'exécution de toutes les sous-expressions de calcul associées aux noeuds de l'arbre d'évaluation, ce qui correspond à l'étape 446 de la figure 4. Tout d'abord, l'expression correspondant au noeud racine de l'arbre d'évaluation (voir figure 11) est récupérée au cours d'une étape 1100. A partir de ce noeud racine, on parcourt, au cours d'une étape 1101, les noeuds fils jusqu'à atteindre une feuille de l'arbre. Pour chaque noeud rencontré au cours de ce parcours, la sous-expression associée voit son statut d'évaluation mis à en cours de traitement . Lorsqu'une feuille de l'arbre d'évaluation est atteinte au cours de l'étape 1101, l'exécution de la sous-expression associée est activée lors d'une étape 1102. Puis, au cours d'une étape 1103, on détermine si un résultat est disponible sans avoir besoin d'informations XML. Si oui, ce résultat est propagé à la sous-expression parente (noeud précédent dans l'arbre) lors d'une l'étape 1106. Lorsque au cours d'une étape 1107 de remontée du résultat, le noeud parent possède plusieurs fils, le résultat est mis en attente de résultat de tous les fils afin d'agréger les résultats des noeuds fils pour calculer le résultat du noeud parent, au cours d'une étape 1108. La propagation du résultat du noeud reprend quand tous les noeuds fils ont un résultat qui permet l'agrégation au cours de l'étape 1108. A la suite à cette agrégation, la remontée de résultat se poursuit par itération des étapes 1106 à 1108, jusqu'à ce que le noeud racine de l'arbre d'évaluation soit atteint, le résultat du test de l'étape 1106 étant alors négatif. Lorsque ce noeud est atteint, le résultat courant correspond à un résultat pour l'expression XPath et est émis vers l'application au cours d'une étape 1109. Si, au cours del'étape 1103, on détermine que le résultat n'est pas disponible sans avoir besoin d'informations XML, ce qui est le cas, typiquement, pour une sous-expression de navigation, la sous-expression est mise en attente de données XML, au cours d'une étape 1104. A titre d'exemple, en figure 8, les feuilles de l'arbre d'évaluation sont les ExprResult 865 et 867 correspondant aux premier et troisième arguments de l'appel de fonction et les LocationPath en fin des branches 866 et 868 correspondent aux deuxième et quatrième arguments. Typiquement l'étape 1103 retournerait vrai pour les deux premières tandis que les deux dernières seraient mises en attente de données XML lors de l'étape 1104. L'étape suivante 1105 permet de poursuivre le parcours des autres branches de l'arbre d'évaluation. Comme illustrée en figure 12, la seconde étape principale du traitement consiste en la récupération des informations XML 104 en vue de la résolution des sous-expressions mises en attente de données XML lors de l'étape 1104, typiquement les sous-expressions de navigation. Cela correspond à l'étape 448 de la figure 4. C'est le contrôleur d'exécution 122 qui effectue cette partie, aidé par le gestionnaire de cibles 124. L'initialisation de cette seconde étape a été préparée par le gestionnaire de cibles lors des étapes 706 et 713. La suite du traitement se déroule selon les étapes décrites en figure 12. Au cours d'une étape 1200, le navigateur XML 103 est initialisé avec le document XML 104 sur lequel l'application 101 souhaite évaluer une ou plusieurs expressions XPath. Puis, au cours d'une étape 1201, on détermine si le navigateur XML 103 est prêt à envoyer des évènements XML, auquel cas, le gestionnaire de cibles 124 marque ses cibles d'évaluation initiales, au cours d'une étape 1202, comme solution intermédiaire , positionne à 0 un indice de profondeur qui correspond à la profondeur dans le document XML ou par rapport au contexte d'évaluation initial (dans le cas de LocationPath relatives), puis au cours d'une étape 1203, prépare les prochaines cibles devant être traitées. A cet effet, le gestionnaire de cibles 124 analyse, pour chacune des cibles initiales, la cible de navigation compilée associée. Le gestionnaire de cibles 124 insère dans sa pile de cibles une nouvelle liste de cibles d'évaluation à considérer à la prochaine profondeur. Ces nouvelles cibles sont liées, pour chaque cible d'évaluation initiale, à la (ou aux) prochaine(s) cible(s) de navigation compilée(s) de la cible de navigation compilée associée à la cible d'évaluation initiale. Les prochaines cibles de navigation compilées sont trouvées en avançant sur les différentes branches de navigation. A titre d'exemple, en référence à la figure 8, CNC10 et CNC20 sont les cibles de navigation compilées associées aux cibles d'évaluation initiales 0E10 et 0E20 du gestionnaire de cibles 124. L'étape 1203 consiste alors à créer deux cibles d'évaluation 0E11 et 0E21 reliées à CNC11 et CNC21. Une fois créées, les nouvelles cibles d'évaluation 0E11 et 0E21 ont leur lien vers leur cible parente mis à jour avec la cible d'évaluation qui les précède (0E10 et 0E20) dans la pile de cibles du gestionnaire 124. A la suite de l'étape 1203, au cours d'une étape 1204, le processeur XPath 102 reçoit un évènement XML 104 par l'intermédiaire du navigateur XML 103. Cet évènement est sauvegardé en mémoire 131 du navigateur XPath 123. Puis, au cours d'une étape 1205, on détermine si l'événement XML consiste en un début d'élément XML et, si oui, on passe à l'étape 1206. Sinon, au cours d'une étape 1207, on détermine si l'événement XML consiste en la fin du document XML 104 et, si oui, l'évaluation de l'expression XPath se termine. Sinon, au cours d'une étape 1208, on détermine si l'événement consiste en une fin d'élément XML et, si oui, on passe à l'étape 1209. Sinon, on passe à l'étape 1206. Ainsi, si l'événement est un évènement signalant un noeud XML de type texte ou commentaire, le traitement se poursuit au cours de l'une des étapes 1206 et 1209, les noeuds texte et commentaire comportant deux évènements, début du noeud et fin du noeud. Dans le cas d'un début de noeud XPath, lors de l'étape 1206, le gestionnaire de cibles 124 incrémente son indice de profondeur de 1 , lors d'une étape 1310, comme illustré en figure 13. Puis, le gestionnaire de cibles 124 récupère, au cours d'une étape 1311, la première cible dans la liste correspondant à la profondeur courante. Puis, au cours d'une étape 1312, on détermine si au moins une cible d'évaluation est présente dans cette liste de cibles et, si oui, le NodeTest correspondant, récupéré par l'intermédiaire des cibles de navigation compilées des cibles d'évaluation, est sélectionné lors d'une étape 1313. Sinon, l'étape 1206 se termine et on passe à l'évènement XML suivant au cours de l'étape 1204. En référence à l'exemple de la figure 8, à la profondeur 1 , un seul NodeTest 869 est activé et il correspond à vérifier que le nom de l'élément courant est égal à bookstore . Au cours d'une étape 1314, on détermine si le NodeTest sélectionné lors de l'étape 1313 a déjà été résolu pour la profondeur courante. Si c'est le cas, la cible d'évaluation courante a son statut d'évaluation mis à jour au cours d'une étape 1316, en fonction du résultat du NodeTest . Si le NodeTest n'a pas déjà été résolu, il l'est lors d'une étape 1315 qui consiste à réellement effectuer les tests sur le noeud courant. Selon la spécification XPath, il peut s'agir de tester le nom ou le type du noeud courant. Chaque NodeTest étant associé à au moins une cible de navigation compilée et donc indirectement à une cible d'évaluation, le statut d'évaluation de ces dernières peut donc être mis à jour au cours de l'étape 1316. Au cours de cette étape 1316, le statut d'évaluation de la cible d'évaluation peut prendre différentes valeurs : - Solution potentielle si la cible de navigation associée à la cible d'évaluation contient des prédicats et qu'il s'agit d'une feuille sur une branche de navigation, - Solution potentielle intermédiaire pour le même cas que précédemment mais pour une cible de navigation compilée non feuille, - Solution intermédiaire Si la cible d'évaluation est entièrement atteinte et que sa cible de navigation compilée associée n'est pas une feuille, - Solution Si la cible d'évaluation est entièrement atteinte et que sa cible de navigation compilée associée est une feuille, - Sans Solution Si la cible d'évaluation n'est pas atteinte. Au cours d'une étape 1317, on détermine si, au cours de l'étape 1316, des cibles d'évaluation atteignent le stade Solution . Si oui, le noeud courant est propagé vers la cible d'évaluation parente lors d'une étape 1318 décrite plus bas. Sinon, au cours d'une étape 1319, on détermine si le statut de la cible d'évaluation est la valeur Sans Solution . Si oui, au cours d'une étape 1320, on passe à la cible suivante et on retourne à l'étape 1312. Sinon, on prépare la ou les prochaines cibles d'évaluation liées à la cible d'évaluation courante au cours d'une étape 1321. Les deux tests combinés 1317 et 1319 permettent respectivement de faire remonter un résultat pour une branche de l'arbre de navigation ou d'arrêter la recherche le long d'une branche de l'arbre. Les autres valeurs de statuts d'évaluation, solution intermédiaire , solution intermédiaire potentielle et solution potentielle conduisent à l'étape 1321, équivalente à l'étape 1203 : étant donnée une cible d'évaluation, on détermine dans sa cible de navigation compilée associée quelles sont les prochaines cibles de navigation, Step suivant ou appartenant à un Predicate , dans l'arbre de navigation. Pour chaque cible se trouvant à la même profondeur ou à une profondeur +1, une cible d'évaluation est créée et insérée respectivement dans la liste de cibles courante ou dans la liste de cibles pour la prochaine profondeur. Ceci permet de résoudre a priori l' AxisSpecifier . A la suite de l'étape 1321, on passe à la cible d'évaluation suivante dans la liste courante au cours de l'étape 1320, jusqu'à ce que la dernière cible soit atteinte, le résultat du test de l'étape 1312 devenant faux . Lorsqu'il n'y a plus de cible d'évaluation pour la liste de cibles courante, l'étape 1206 se termine et l'on retourne à l'étape 1204 jusqu'à ce que la fin du document soit atteinte. La propagation des résultats effectuée au cours de l'étape 1318 consiste, pour une cible d'évaluation dont le statut vaut Solution , à propager le noeud résultat jusqu'à la racine de la branche correspondante pour ensuite le transférer à la feuille associée de l'arbre d'évaluation. Typiquement, sur l'exemple de la figure 8, la cible d'évaluation correspondant à CNC13 aurait son statut mis à Solution sur un début d'élément XML nommé title . La propagation du résultat de l'étape 1318 consiste à faire remonter le noeud XPath représentant cet évènement jusqu'à la cible d'évaluation correspondant à CNC10. Ensuite par l'intermédiaire du lien 861, ce résultat est transmis à la LocationPath 866 en attente de données XML depuis l'étape 1104. A cet effet, comme illustré en figure 14 qui détaille l'étape 1318, on cherche la cible d'évaluation parente de la cible courante. Au cours d'une étape 1400, on détermine si cette cible d'évaluation parente est une cible d'évaluation racine , c'est-à-dire dont la cible de navigation compilée associée est une racine d'une branche de navigation. Si tel est le cas, le résultat est fourni à la LocationPath parente au cours d'une étape 1401. Ensuite, si ce résultat permet d'éliminer l'ensemble des sous-expressions de navigation en attente de données XML depuis l'étape 1104, ce qui est déterminé au cours de l'étape 1322 de la figure 13, l'étape d'évaluation 448 de la figure 4 est terminée. Sinon on retourne à l'étape 1320. Si, au cours de l'étape 1400, on détermine que la cible d'évaluation parente n'est pas une racine , le résultat est passé à cette cible d'évaluation parente lors d'une étape 1402, puis on détermine si son statut d'évaluation est solution intermédiaire , lors d'une étape 1403. Si oui, on retourne à l'étape 1400 jusqu'à atteindre la racine ou une cible parente avec un statut différent de solution intermédiaire . Sinon, au cours d'une étape 1404, on détermine si le statut est solution potentielle intermédiaire . Sinon, c'est- à-dire si le statut est sans solution , le résultat arrivant est écarté et on retourne à l'étape 1318. Si le statut est solution potentielle intermédiaire , le résultat est mis en attente au niveau de la cible d'évaluation, au cours d'une étape 1405, jusqu'à sa résolution complète. On note que le passage du statut de solution potentielle à celui de solution , intermédiaire ou non, se fait lors de l'étape 1107 où une sous- expression représentant un prédicat possède un résultat et le transmet à son Step parent. En revenant à la figure 12, au cours de l'étape 1209, c'est-à-dire dans le cas d'une fin de noeud XPath, on désactive, au cours d'une étape 1500 illustrée en figure 15, les cibles d'évaluation appartenant à la liste de cibles correspondant à la profondeur courante dans la pile de cibles du gestionnaire 124. La désactivation peut consister soit à les enlever de la pile de cibles, soit à leur associer un statut active / inactive qui est, dans ce cas, initialisé à inactive . Puis, au cours d'une étape 1501, on détermine si, parmi les cibles d'évaluation à désactiver, certaines correspondent à des cibles d'évaluation racine, cette information étant portée par le type de la cible de navigation compilée associée. Si c'est le cas, un signal est envoyé à la LocationPath parente pour indiquer qu'aucune solution n'a été trouvée pour le contexte d'évaluation courant, au cours d'une étape 1502. Cela permet de débloquer des sous-expressions en attente de données XML depuis l'étape 1104 et de remonter un résultat vide au cours des étapes 1106 à 1108 et, éventuellement, d'émettre un résultat d'évaluation au cours de l'étape 1109. Puis, au cours d'une étape 1503, on détermine si cette propagation conduit à une fin d'évaluation. Sinon, on passe à une étape 1504, au cours de laquelle la profondeur courante est décrémentée de 1 . Puis, au cours d'une étape 1505, on détermine si la profondeur vaut 0 , cela signifie que l'on a atteint la fin des données XML. Si oui, l'évaluation se termine. Sinon, les cibles d'évaluation se trouvant à cette nouvelle profondeur sont réinitialisées, au cours d'une étape 1506, l'initialisation concernant les statuts d'évaluation et le statut des NodeTest associés, en vue d'une évaluation sur de nouvelles données XML au cours de l'étape 1204, si la fin d'évaluation n'est pas atteinte, ce qui est déterminé au cours de l'étape 1310 illustrée en figure 13. Comme on le comprend à la lecture de la description qui précède, la mise en oeuvre de la présente invention fournit un moyen d'évaluer des expressions XPath à la volée, par une analyse de ses expressions afin de distinguer la partie calculatoire de la partie dépendant de données XML, tout en préservant le lien entre ces deux parties en vue des transmissions de résultats et en limitant leur stockage. REVENDICATIONS 1 - Procédé d'analyse d'une expression XPath composée de sous-expressions à évaluer sur un document structuré (300), caractérisé en ce qu'il comporte : - une étape (444, 444b) de classification des sous-expressions de ladite expression en un sous-ensemble comportant des sous-expressions de calcul et un sous-ensemble comportant des sous-expressions de navigation et - une étape (444, 444c, 705) de liaison de chaque sous-expression de navigation à la sous-expression de calcul qui l'utilise. 2 û Procédé selon la revendication 1, caractérisé en ce que l'étape (444) de classification comporte une étape de structuration (444b, 506, 509, 702, 711) de chacun des sous-ensembles de sous-expressions. 3 û Procédé selon la revendication 2, caractérisé en ce que, au cours de l'étape de structuration (444b, 506, 509, 702, 711), on représente le sous-ensemble comportant des sous-expressions de calcul par un arbre d'évaluation (860) et le sous-ensemble comportant des expressions de navigation par un arbre de navigation (862). 4 û Procédé selon la revendication 3, caractérisé en ce que, au cours de l'étape de structuration (444b, 506, 509, 702, 711), on constitue l'arbre de navigation (862) avec des cibles de navigation compilées (862), structure permettant de représenter la recherche d'informations correspondant à ladite expression dans le document structuré (300), chaque cible de navigation compilée étant liée à une sous-expression de navigation de type LocationPath et à au moins un Step dans cette LocationPath . 5 û Procédé selon la revendication 4, caractérisé en ce que, au cours de l'étape (444b, 506, 509, 702, 711) de structuration, chaque entité de type NodeTest de chaque Step est associée à au moins une cible de navigation compilée (862). 6 û Procédé selon l'une quelconque des revendications 4 ou 5, caractérisé en ce que, au cours de l'étape (444b) de structuration, on détermine (701, 707) si une cible de navigation compilée courante (862) appartient à un nouveauchemin absolu ou relatif et, si oui, on crée (702, 711) une nouvelle branche dans l'arbre de navigation. 7 û Procédé selon la revendication 6, caractérisé en ce que, au cours de l'étape (444b) de structuration, on détermine (701, 707) si la cible de navigation compilée courante (862) appartient à un nouveau chemin absolu et, si oui, on crée (506) une structure de représentation d'une LocationPath comme nouvelle feuille de l'arbre d'évaluation (860), cette structure de représentation assurant le lien entre la branche courante de l'arbre d'évaluation et la nouvelle branche de l'arbre de navigation. 8 û Procédé selon l'une quelconque des revendications 6 ou 7, caractérisé en ce qu'il comporte une étape (704, 713) de création d'une cible d'évaluation associée à la cible de navigation compilée courante (862), ladite cible d'évaluation comportant des informations représentant un statut d'évaluation, une éventuelle solution rencontrée lors de l'évaluation et un lien entre la cible d'évaluation et la cible de navigation compilée courante. 9 û Procédé selon l'une quelconque des revendications 7 ou 8, caractérisé en ce que, dans le cas de LocationPath dont au moins un Step contient au moins un prédicat, l'arbre d'évaluation (860) descend jusqu'à l'entité Step afin de relier la sous-expression correspondant au prédicat à sa sous- expression parente, la cible de navigation compilée (862) courante étant insérée au début de cette nouvelle branche et un lien de cette cible de navigation compilée courante vers la LocationPath dont elle est issue est mis à jour ainsi qu'un type associé à cette cible de navigation compilée courante indiquant qu'elle représente le premier Step du chemin. 10 û Procédé selon l'une quelconque des revendications 3 à 9, caractérisé en ce que, au cours de l'étape (444, 444b) de classification, on réalise des simplifications sur l'arbre d'évaluation (860). 11 û Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que, au cours de l'étape (444, 444b) de classification, on effectue une étape (501-504) d'analyse grammaticale au cours de laquelle un analyseur sémantique (112) parcourt la liste de symboles des expressions et identifie lestypes d'expression définis par la syntaxe liée au langage XPath contenus dans l'expression à analyser. 12 û Procédé selon la revendication 11, caractérisé en ce que, au cours de l'étape (501-504) d'analyse grammaticale, pour au moins un symbole issu d'une analyse lexicale, on détermine, règle de grammaire par règle de grammaire, si le symbole répond à ladite règle. 13 û Procédé selon la revendication 12, caractérisé en ce que, au cours de l'étape (501-504) d'analyse grammaticale, si le symbole répond à une règle, on détermine si ladite règle est liée à une sous-expression de navigation et, si oui, on construit une sousexpression de navigation et, sinon, on construit une sous-expression de calcul. 14 û Procédé selon l'une quelconque des revendications 1 à 13, caractérisé en ce que, au cours de l'étape (444, 444b) de classification, on détermine si une sous-expression peut contenir d'autres sous-expressions et, si oui, la représentation de chaque dite sous-expression comporte une référence à un lien de parenté avec au moins une autre sous-expression. 15 û Procédé selon l'une quelconque des revendications 1 à 14, caractérisé en ce que, au cours de l'étape (444) de classification, on met en oeuvre une structure de représentation générique pour différents types de sous-expressions de calcul. 16 - Procédé d'évaluation d'une expression XPath sur un document structuré (300) en langage de balisage, caractérisé en ce qu'il met en oeuvre le procédé d'analyse d'expression selon l'une quelconque des revendications 1 à 15 et comporte une étape (446-448) d'évaluation de l'expression mettant en oeuvre l'évaluation des sous-expressions de navigation de l'expression sur des données du document structuré. 17 - Procédé selon la revendication 16, caractérisé en ce que, au cours de l'étape (446-448) d'évaluation de l'expression XPath, on évalue au moins une sous-expression de calcul et une sous-expression de navigation selon les étapes suivantes : - lancement (446) de l'exécution des sous-expressions de calcul en récupérant, depuis un arbre d'évaluation (860) représentant le sous-ensemble comportant des sous-expressions de calcul, une expression de calcul dite racine et en parcourant des noeuds dits fils jusqu'à atteindre toutes les feuilles de l'arbre d'évaluation, parcours (1204, 1208) du document structuré pour construire au moins 5 un résultat pour chaque sous-expression de navigation associée à une sous-expression de calcul feuille de l'arbre d'évaluation, transmission de chaque résultat de chaque sous-expression de navigation à la sous-expression de calcul associée, et, itérativement jusqu'à atteindre la sous-expression de calcul racine de l'arbre 10 d'évaluation : -application (1209) d'un traitement lié à la sous-expression de calcul sur le résultat, au cas où la sous-expression de calcul est un noeud fils, propagation (1318, 1402) du résultat dudit traitement à la sous- expression de calcul 15 parente. 18 û Procédé selon la revendication 17, caractérisé en ce que, au cours de l'étape de propagation, si la sous-expression de calcul parente possède au moins une sous-expression de calcul n'ayant pas encore subi l'étape d'application de traitement, l'itération est suspendue jusqu'à ce que chaque dite 20 sous-expression de calcul fille subisse ladite étape d'application de traitement. 19 - Dispositif d'analyse d'une expression XPath composée de sous-expressions à évaluer sur un document structuré (300), caractérisé en ce qu'il comporte : - un moyen (112, 211) de classification des sous-expressions de 25 ladite expression en un sous-ensemble comportant des sous-expressions de calcul et un sous-ensemble comportant des sous-expressions de navigation et - un moyen (112, 211) de liaison de chaque sous-expression de navigation à la sous-expression de calcul qui l'utilise. 20 - Programme d'ordinateur chargeable dans un système informatique, ledit 30 programme contenant des instructions permettant la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 18.21 - Support (224) d'informations lisibles par un ordinateur ou un microprocesseur, amovible ou non, conservant des instructions d'un programme informatique, caractérisé en ce qu'il permet la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 18.