Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

2.1.2. Conformité d'un document structuré vis-à-vis de sa grammaire

Soient une grammaire algébrique G et un arbre t (document) ; le document t est conforme à la grammaire G (on note t ? G) si chacune des étapes de décomposition hiérarchique de t obéit à une des productions de G. On dit dans ce cas que t est un arbre de dérivation pour la grammaire G. L'ensemble des arbres de dérivation pour la grammaire G en utilisant le symbole X comme axiome est noté Der(G,X) et est défini formellement comme suit :

Définition 10 L'ensemble noté Der(G,X) des arbres de dérivation suivant la grammaire G associés au symbole grammatical X est constitué des arbres de la forme X[t1,··· ,t_n] pour lesquels il existe une production P = (XP(0),XP(1) ···XP(n)) telle que X = XP(0), |P| = n et ti E Der(G,XP(i)) pour tout 1 < i < n.

2.1.2.1. Vérification de la conformité d'un document : les AST

Dans un arbre de dérivation, les noeuds sont étiquetés par des symboles grammaticaux. De la même manière on peut définir les arbres de syntaxe abstraite (Abstract Syntax Tree - AST -) qui sont des arbres dont les noeuds sont étiquetés par des productions de la grammaire.

Définition 11 L'ensemble noté AST(G,X) des arbres de syntaxe abstraite suivant la grammaire G associés au symbole grammatical X est constitué des arbres de la forme P[t1,··· ,t_n]

2.1. Documents structurés, conformité et édition 22

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

oÙ P = (XP(0),XP(1) ···XP(n)) est une production telle que X = XP(0), |P| = n et ti ? AST(G,XP(i)) pour tout 1 = i = n.

Les AST peuvent être utilisés comme preuve de la conformité d'un document. En effet, si pour un document t donné on peut trouver un AST u équivalent, alors le document en question est conforme à la grammaire. Ceci est garanti par le fait que les AST ont des noeuds étiquetés par des productions de la grammaire et que leur décomposition hiérarchique obéit à ces productions par définition (définition 11). On dit dans ce cas que u détermine t et on note u ` t ; la relation ` étant définie formellement par P[u1,··· ,u_n] ` X[t1,··· ,t<sub>m</sub>] si X = XP(0), n = m et ui `ti pour tout 1 = i = n. Étant donné que chaque production de la grammaire est caractérisée par la donnée conjointe de sa partie gauche et de sa partie droite, il existe une correspondance bijective entre l'ensemble des arbres de dérivation d'une grammaire et l'ensemble de ses arbres de syntaxe abstraite. Le passage d'un AST à un arbre de dérivation se fait juste par remplacement des productions dans l'AST par leurs symboles en partie gauche. La figure 2.2 présente un AST et l'arbre de dérivation équivalent sur la grammaire Gexpl.

FIGURE 2.2 - Un AST et l'arbre de dérivation qu'il détermine.

2.1.2.2. Vérification de la conformité d'un document : les automates d'arbre

La conformité d'un arbre vis-à-vis d'une grammaire peut être vérifiée grâce à un auto-mate¹ d'arbre descendant. En effet, quand on regarde les productions d'une grammaire, on peut remarquer que chaque sorte est associée à un ensemble de productions. On peut de ce point de vue, considérer une grammaire comme une application

gram : symb ? [(prod, [symb])]

qui associe à chaque sorte une liste de couples formés d'un nom de production et de la liste des sortes en partie droite de cette production. Une telle observation suggère qu'une grammaire peut être interprétée comme un automate d'arbre (descendant) utilisable pour la reconnaissance ou pour la génération de ses instances.

1. Les automates d'arbres sont des outils formels qui ont plusieurs applications scientifiques. Le lecteur intéressé pourra consulter [CDG+08] dans lequel il trouvera des définitions formelles, des démonstrations et des applications possibles des automates d'arbre.

2.1. Documents structurés, conformité et édition 23

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Définition 12 Un automate d'arbre (descendant) défini sur L est la donnée A = (L,Q,R,F,q0) d'un ensemble L de symboles; ses éléments sont les étiquettes des transitions de l'automate A, d'un ensemble Q d'états, d'un état particulier q0 ? Q appelé état initial, d'un ensemble F ? Q des états finals et d'un ensemble fini R ? Q × L × Q^* de transitions.

-- Un élément de R est noté q ? (a,[q1,··· ,q_n]) : intuitivement, il s'agit de la liste des états [q1,··· ,q_n] accessibles à partir d'un état q donné en franchissant une transition

-- Si q ? (a1,[q¹

étiquetée a ; ₁,··· ,q¹ _n1]),··· ,q ? (ak,[q^k ₁,··· ,qk _nk]) désigne l'ensemble des transitions associées à l'état q, on note next q = [(a1,[q¹ ₁,··· ,q¹ _n1]),··· ,(ak,[q^k ₁,··· ,qk _nk])] la liste formée des couples (ai,[qⁱ ₁,··· ,qi _ni]). Dans le cas où q est un état terminal (c-à-d. aucune transition n'est franchissable depuis l'état q), next q = [];

-- Un état q ? Q appartient à F s'il contient une transition de la forme q ? (a,[]).

On peut interpréter une grammaire G = (S,P,A) comme un automate d'arbre (descendant) [CDG⁺08] A = (L,Q,R,F,q0) en considérant que:

1. q0 = A;

2. L = P est le type des étiquettes des transitions de l'automate A ; 3. Q = S est le type des états et,

4. q ? (a,[q1,··· ,q_n]) est une transition de l'automate lorsque la paire (a,[q1,··· ,q_n]) apparaît dans la liste (gram q)² ;

5. F = {N ? S, N ? E ? P}, c'est à dire l'ensemble des symboles possédant une E-production. On notera AG l'automate d'arbre dérivé à partir de G. Reconnaissance d'un arbre à partir de l'automate d'arbre

Pour reconnaître un arbre à l'aide d'un automate d'arbre, à partir d'un état initial, il suffit :

1. D'associer l'état initial à la racine de l'arbre;

2. Si un noeud étiqueté X est associé à l'état q, alors la transition q ? (p,[q1,··· ,q_n]), n = 0 avec p une X-production ³, est une transition de l'automate. Si ce noeud possède n successeurs non encore associés à des états, alors n > 0 et on associe les états de q1 jusqu'à q_n à chacun de ces n successeurs;

3. L'arbre est reconnu si on a réussi à associer un état à chacun des noeuds de l'arbre, et que les noeuds feuilles sont tous associés à des états finals.

On note A ` t q le fait que l'automate d'arbre A accepte l'arbre t à partir de l'état initial q, et 2' (A,q) (langage d'arbre) l'ensemble des arbres acceptés par l'automate A à partir de l'état initial q. Ainsi, (A ` t I>q) ? (t ? 2' (A,q)). Les arbres (documents) acceptés par l'automate AG à partir d'un état q quelconque sont conformes à la grammaire G; le procédé de construction de l'automate AG et l'algorithme de reconnaissance nous le garantissent.

2. Rappel : gram est l'application obtenue par abstraction de G et a pour type : gram : symb ? [(prod, [symb])].

3. Une production ayant X en partie gauche.

2.1. Documents structurés, conformité et édition 24

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Exemple 13 L'automate d'arbre 91Gexpl = (E,Q,R,q0) dérivé de la grammaire Gexpl est défini par E = / ³¹= {P1,P2,··· ,P7}, Q = S = {A,B,C}, F = {A,C}, q0 = A et ses transitions sont les

suivantes :

A -+ (P1,[C,B]) B -+ (P3,[C,A]) C -+ (P5,[A,C])

A -+ (P2,[]) B -+ (P4,[B,B]) C -+ (P6,[C,C])

C -+ (P7,[])

La figure 2.3 illustre la procédure de vérification de la conformité d'un arbre vis-à-vis de la grammaire Gexpl grâce à l'automate _91Gexpl à partir de l'état q0 = A. Au final, le dit arbre est conforme _(91Gexpl I- t L> A) car tous ses noeuds ont été associés à des états de l'automate, et ses feuilles associées à des états finals.

FIGURE 2.3 - Illustration de la procédure de vérification de la conformité d'un arbre à partir d'un automate d'arbre.