RÉSUMÉ.
Un document structuré complexe est représenté intentionnellement sous
la forme d'une structure arborescente décorée par des attributs. Les structures
licites sont caractérisées par une grammaire algébrique
abstraite. Nous faisons ici abstraction des attributs ; ces derniers
sont liés à des aspects sémantiques qui peuvent être traités séparément
des aspects purement structurels qui nous intéressent ici. Cette représentation
intentionnelle peut être manipulée de façon indépendante et éventuellement
non synchronisée par divers outils d'édition et de manipulation qui
opèrent sur des vues partielles distinctes du même document. Pour
la re-synchronisation de ces vues partielles nous devons résoudre le
problème de leur cohérence : décider s'il existe un document correspondant
à ces différentes vues et dans l'affirmative produire un tel document.
Nous montrons comment résoudre ce problème dans le cas où chaque vue
est associée à un sous-ensemble des symboles grammaticaux : ceux qui
correspondent aux catégories syntaxiques visibles. L'algorithme proposé,
qui repose fortement sur le mécanisme d'évaluation paresseuse, résout
ce problème même dans le cas où chaque vue partielle correspond
à un nombre infini de documents possibles.
ABSTRACT.
A complex structured document is intentionnally represented as a tree
decorated with attributes. The set of legal structures is given
by an abstract context-free
grammar. We forget about the attributes; they are related with semantical
issues that can be treated independently of the purely structural
aspects that we address in this article. That intentional representation
may be asynchronously manipulated by a set of independent tools each
of which operates on a distinct partial view of the whole structure.
In order to synchronize these various partial views, we are faced to
the problem of their coherence: can we decide whether there exists
some global structure corresponding to a given set of partial views
and in the affirmative, can we produce such a global structure ? We
solve this problem in the case where a view is given by a subset of
grammatical symbols, those associated with the so-called visible syntactical
categories. The proposed algorithm, that strongly relies on the mechanism
of lazy evaluation, produces an answer to this problem even if partial
views may correspond to an infinite set of related global structures.
.
MOTS-CLÉS : DTD, XML, grammaire algébrique, représentation intentionnelle, cohérence de vues, évaluation paresseuse, co-algèbres, automates d'arbres, anamorphisme
KEYWORDS: DTD, XML, Contex-Free Grammar, Intentional Representation, Coherence of Views, Lazy Evaluation, Co-Algebra, Tree Automata, Anamorphism
|