Introduction

XML (Extensible Mark-up Language) [28] is a meta-language recommended by W3 Consortium in order to create structured documents. In XML document structure, content and presentation are strictly separated. Unlike plain text, it contains special tags, which decompose document into logical parts. Therefore we say that XML belongs to the group of mark-up languages. Presentation of XML document can be described by several languages, usually in external file. Most common are XSL (Extensible Stylesheet Language) and CSS (Cascading Stylesheet).

Nowadays the usage of XML is growing very fast. It is a suitable tool in every field, where it is necessary to create document standards. Furthermore it has become very popular as a format for data exchange among applications since for programs it is necessary to mark semantics of data explicitly.

For this reasons various transformations are needed. Many transformation systems for structured documents have been implemented, some of them are based on formal models while others were created only ad-hoc. We have seen several reviews of existing transformation systems ( [19,18,20,11]). The author in [20] introduces also some basic categorization, however in none of these works a complete classification system has been defined.

The rest of this paper is organized as follows: After defining some notions used through-out the paper we introduce defined classification system in Section 3. We discuss reasons for choosing particular criteria and we assign implemented transformations systems for structured documents into defined groups. In section 4, we are dealing with one specific group of transformations, namely type transformations. We are examining formal models on which these transformations are based and we define them in a common framework. At last we present several results obtained by comparing these formal models. Section 5 contains a brief conclusion and outlines our future research.

Notions and notations

XML document

Basic logical unit of an XML document is an element. The content of an element is delimited by a start-tag and an end-tag. It can contain text and other nested elements as well. Variables called attributes can be assigned to an element. Obviously, an XML document has a hierarchical structure and it can be represented by a tree, where internal nodes are elements and leaves contain textual content.

The framework considered in this paper is restricted in two ways. Firstly, we do not consider element attributes of XML documents since we are concerned mainly with transformations at the level of elements. Secondly, we assume that element names of XML documents are from a finite and known set denoted by E. This enables us to define XML documents as trees over finite alphabets, which is the most natural way as far as we consider XML documents transformation. Furthermore we will use symbol Char for alphabet of characters allowed to appear in the textual content of XML document. Char is specified in W3C recommendation [28].

Definition 1. Let Σ, Γ be alphabets. The set of trees over (Γ, Σ) denoted by T Γ (Σ) is defined as follows:

-a ∈ Σ, then t = a ∈ T Γ (Σ) and root(t) = a. -A ∈ Γ , t 1 , . . . , t k ∈ T Γ (Σ), k > 0, then t = A(t 1 , . . . , t k ) ∈ T Γ (Σ) and root(t) = A. -nothing else belongs to T Γ (Σ).

We call Σ a leaf alphabet and Γ an internal node alphabet. Alphabets Σ, Γ do not need to be disjoint.

Obviously the set of XML documents denoted by D equals to the set of trees over (E, Char), i.e., D = T E (Char).

DTD

An XML document type is a class, which contains XML documents with similar structure. It is specified by a type definition, which describes the set of elements, that should be contained in the document as well as relationships among the elements. W3C has defined two ways of notation -DTD and XML schema. DTD is simpler and describes particularly syntax of the type while XML schema introduces more aspects like namespaces, restrictions for attribute values, etc. However, syntactic features of both models can be easily captured by contextfree grammar. We will use this concept in the rest of this paper. Now we will define context-free grammars and their subset -type grammars, which describe XML document types. Definition 2. Context-free grammar (CFG) is a 4-tuple G = (N, T, P, S), where N is an alphabet of nonterminal symbols, T an alphabet of terminal symbols, P ⊆ N × (N ∪ T ) * is a finite set of production rules and S ∈ N is a starting symbol.

Definition 3. Let G = (N, T, P, S) to be a CFG, then a set of derivation subtrees of G denoted by S G is defined as follows:

-a ∈ T , then t = a ∈ S G . -A ∈ N , t 1 , . . . , t k ∈ S G and A → root(t 1 ), . . . , root(t k ) ∈ P , then t = A(t 1 , . . . , t k ) ∈ S G . -nothing else belongs to S G . A set of derivation trees of G -T G is a subset of S G such that t ∈ T G ⇔ t ∈ S G and root(t) = S.

A type grammar is a context free grammar G = (N, T, P, S), such that N = E, T = Char. We denote its set of derivation trees D G since we consider documents rather then general trees. Obviously it holds D G ⊆ D. Nonterminals of a type grammar represent element names and the set of terminals equals to the text alphabet.

If we have a given type grammar, it generates a class of XML documents, which equals to the set of its derivation trees. Validation of XML document against a grammar is a process, which gives us as a result an answer, whether given XML document belongs to the class of documents generated by given grammar. If the answer is yes, we say that the XML document is valid for a given type grammar (or correct).

XML transformations

A transformation of an XML document takes some source documents as an input, it processes them according to the transformation specification and it gives target documents as an output.

It is reasonable to define a transformation of XML documents as a relation on the set of XML documents rather then a function 1 . As usual we begin with more general definition, i.e., tree transformation. Definition 4. Let Σ, Σ , Γ , Γ be alphabets. A tree transformation from (Γ, Σ)

to (Γ , Σ ) is a relation τ ⊆ T Γ (Σ) × T Γ (Σ ).

If we apply previous definition on XML documents, we obtain restricted case again. Thus, an XML documents transformation is a relation τ ⊆ D × D. Obviously if we consider any XML document transformation, the source leaf alphabet equals to the target leaf alphabet.

Tree properties

Now we introduce several definitions related to trees that we will need later in this paper.

Let Σ, Σ , Γ, Γ be alphabets. Let X = {x 1 , x 2 , . . .} be a set of variable symbols. For each k > 0, we denote by X k a set of first k variables, thus X k = {x 1 , . . . , x k }. We denote by T Γ (Σ ∪X), T Γ (Σ ∪ X k ) sets of trees with these variables, where it must hold Σ ∩ X = ∅.

Definition of a tree substitution follows. Let

t ∈ T Γ (Σ ∪ X k ), k > 0 and t 1 , . . . , t k ∈ T Γ (Σ ). Then t[x 1 ← t 1 , . . . , x k ← t k ]

is a tree obtained from t by replacing each occurrence of x i by a tree t i , 1

≤ i ≤ k 2 .

Let Z = {z 1 , z 2 , . . .} be a set of variables disjoint to X and k > 0. A set of (Γ, Σ, k)-contexts denoted C Γ (Σ, k) is the set of trees t from T Γ (Σ ∪ Z k ), such that for each 1 ≤ i ≤ k the symbol z i appears exactly once in t.

We will use a simpler notation for context substitution. Let t to be a (Γ, Σ, k)context and t 1 , . . . , t k trees. Then we use t

[t 1 , . . . , t k ] instead of t[z 1 ← t 1 , . . . , z k ← t k ].

Let t, t ∈ T Γ (Σ). Then t is a subtree of t if there exists such a context

β ∈ C Γ (Σ, 1) that t = β[t ].

For each tree t ∈ T Γ (Σ) path(t) ⊆ {1, 2, . . .} * is a set of all paths of the tree t, so that each of them unambiguously identifies a node of the tree t. Then symbol ε represents root(t). For each path w ∈ path(t), we denote by label t (w) a label of the node identified by w and by t| w a subtree under this node.

Let

t ∈ T Γ (Σ), t ∈ T Γ (Σ ). We obtain tree t[w ← p t ] ∈ T Γ ∪Γ (Σ ∪ Σ ) from t by replacing subtree in w ∈ path(t) by tree t . Let t ∈ T Γ (Σ), patt ∈ T Γ (Γ ∪ Σ). We say, that t and patt match, if there is such a context γ ∈ C Γ (Σ, k) that t = γ[t 1 , . . . , t k ] for some t 1 , . . . , t k ∈ T Γ (Σ) and it holds patt = γ[root(t 1 ), . . . , root(t k )].

Classification hierarchy

There are several possibilities, how to divide XML document transformations into categories. According to the driving element of the transformation we obtain three basic categories as follows. In each of them different techniques for implementing particular transformation systems are used, thus, it is reasonable to start with this criterion.

1. Source grammar transformations -Transformation process is driven by the source structure. First, the source document is parsed and then according to recognized syntactic elements parts of the output documents are constructed. Usually it is possible to check correctness of input documents, but target correctness is not ensured in this case. If necessary, user must perform validation explicitly. Next we can divide this category into two more specific groups according to the way how the source document is parsed:

• Event-driven transformations -The source document is read as a data stream. As the result, we obtain a list of recognized events. The event can be an occurrence of a start-tag, an end-tag, an attribute, etc. The transformation system reads the list o events and performs corresponding actions. If we allow side-effect functions, an output can be generated already at parsing time. As a formal model, an attribute grammar is often used. Event-driven models require little memory, and provide fast and effective way of accessing XML data. On the other hand, only simple transformations can be performed since it is not possible to return to an earlier part of the document. In some document transformers (e.g. CoST [12,7], OmniMark [8]) the list of recognized events is represented by ESIS (Element Structure Information Set), which is the part of ISO SGML standard [13]. However, currently especially SAX (Simple API for XML) [26] is more and more in use as event-driven mechanism for parsing XML documents. It generates specific SAX events and sends them to the application.

• Tree-based transformations -First, an internal syntactic tree of the source document is constructed and a target document is generated via queries on this tree. In most of the cases transformation systems are based on tree pattern matching and replacement. We can assign widely used XSLT [29] and its predecessor DSSSL [14] as well as systems Scrimshaw [2], Metamorphosis [22], Balise [3] and TranSID [20] to this group.

XSLT, a recommendation of W3 Consortium, has become very popular recently. It is a language, itself written in XML, with powerful capabilities for specifying transformations of XML documents. XSLT program (called stylesheet) consists of a set of template rules. A template rule associates a pattern, which matches nodes in the source document with corresponding template that can be instantiated to form the target tree.

Although XSLT is a powerful transformation language, it has several drawbacks. Firstly, it appears to be a complex language and therefore transformation specification must be written by an expert. Secondly, XSLT processor cannot guarantee the correctness of target documents as well as other systems in this group. However, an XSLT stylesheet can be produced as an output of some two-grammars systems (see next section). Then it is ensured, that generated stylesheet specifies a type transformation and XSLT processor can be used to perform transformation. 2. Target grammar transformations -Target document is created according to the rules of a given target grammar while relevant data from a source document are extracted via queries. This ensures target correctnes. However, we do not need to have any information about source document type. We found only one transformation system, which belongs to this group -TREX [30]. 3. Two grammar transformations (type transformations) -Documents of a given source type are translated into documents of a given target type. Transformation systems are mostly based on one of these formal models -syntax directed translation schema, tree transformation grammar, descending tree transducer and higher order attribute grammar. We discuss these models as well as two grammar transformation systems in detail in the next section. However, there are few systems, which performed two-grammars transformations, but underlying formal model cannot be clearly recognized. These are Grif [25] and Thot [4].

From a different point of view, we distinguish static type transformations, which translate whole documents, and dynamic type transformations, which are used to perform dynamic operations on XML documents. An example is cut and paste operation, which is a standard operation in XML document editors. Unlike in common editors, in this case it is necessary to preserve document structure. Thus, a local transformation must be performed in the place, where a part of another document has been pasted.

Type transformations

The group of type transformations (or two-grammar transformations) is a specific one. In this case there must be only correct documents taken as an input and correct documents must be generated on the output side. To satisfy these conditions, it is usually inevitable to implement transformation system performing this kind of transformations on some underlying formal model. In this section we introduce four formal models on which some of the implemented transformation systems are based. We developed common framework in which we define these models. Our intention was to create a formal base, so that the models can be studied and mutually compared later. We also present current results obtained by comparing some of them according to their transformational power.

Obviously there is a direct proportion between the complexity of transformation specification and the set of possible transformations. Thus, the more powerful particular model is, the more complex specification the user is supposed to write. In a rule A → α, β with each nonterminal from α there is associated an identical nonterminal of β. If there is a multiple occurence of some nonterminal, we indicate association by using integer superscripts. Obviously if we extend definition of a SDTS by a renaming homomorphism for nonterminals, we can use this model also in the case, when it is neccesary to associate nonterminals with different names.

A context-free grammar G s = (N, Σ, P s , S), where

P s = {A → α | ∃β ∈ (N ∪ ∆) * , A → α, β ∈ R}

is a a source grammar and G t = (N, ∆, P t , S), where

P t = {A → β | ∃α ∈ (N ∪ Σ) * , A → α, β ∈ R} is a target grammar of SDTS Ω.

Now we mentioned two modifications of SDTS, which differ from the basic model in a definition of rules:

• Simple SDTS -SSDTS R is a finite set of rules of the form A → α, β, where α ∈ (N ∪ Σ) * , β ∈ (N ∪ ∆) * ,

nonterminals in α, β are identical and the order of nonterminals is preserved.

• Extended SDTS -ESDTS R is a finite set of rules of the form A → α, β, where α ∈ (N ∪ Σ) * , β ∈ (N ∪ ∆) * and nonterminals in β are a permutation of a subset of nonterminals in α.

A syntax-directed translation schema simulates derivations of two contextfree grammars with similar set of rules simultaneously. While using a SDTS in the domain of syntax analysis it was sufficient to store only frontiers of the derivation trees in configurations, if we consider tree transformations it is more natural to keep the whole derivation tree. Then a transformation consists of pairs of trees, where the first one is a derivation tree of the source grammar and the second one is a derivation tree of the target grammar. We started from an algorithm for structured documents transformations using an ESDTS presented in [19]. We skip an operation of adding new nodes into the source tree since authors do not specify exactly what subtree is embedded to the newly created node. Definition 6. A configuration of SDTS (SSDTS, ESDTS) Ω is a tree from the set T N ∪{ } (Σ ∪ ∆). Definition 7. We say, that a pair of trees (A(t 1 , . . . , t n ), A(s 1 , . . . , s m )), A ∈ N , t 1 , . . . , t n , s 1 , . . . , s m ∈ T N ∪{ } (Σ∪∆) realizes a rule A → u 1 . . . u n , v 1 . . . v m ∈ R if the following holds:

1. u 1 . . . u n = root(t 1 ) . . . root(t n ) and v 1 . . . v m = root(s 1 ) . . . root(s m ),

2. h N (u 1 . . . u n ) = u i1 . . . u ir and h N (v 1 . . . v m ) = v j1 . . . v jp = u i k 1 . . . u i kp , i 1 , .

. . , i r ∈ {1, . . . , n} (different), j 1 , . . . , j p ∈ {1, . . . , m} (different), k 1 , . . . , k p ∈ {1, . . . , r} (different), 3. s j l = t i k l for l ∈ {1, . . . , p}, s l = v l , v l ∈ ∆ ∪ {ε} for l / ∈ {j 1 , . . . , j p } and t l = u l , u l ∈ Σ ∪ {ε} for l / ∈ {i 1 , . . . , i r }.

Definition 8. A translation step of SDTS (SSDTS, ESDTS) Ω is a relation ⇒ Ω over the set of configurations defined as follows:

1. β[ (a)] ⇒ Ω β[a], a ∈ ∆ ∪ {ε}. 2. β[ (A(t 1 , . . . , t n ))] ⇒ Ω β[A( (s 1 ), . . . , (s m ))

] and a pair of trees (A(t 1 , . . . , t n ), A(s 1 , . . . , s m )) realizes some rule r ∈ R.

In both cases β is a context from C N ∪{ } (Σ ∪ ∆, 1).

t β z 1 β z 1 1 u u n A A 1 t 1 s n s m v v 1 m Ω 1 ... ... A m v ... 1 v , u ... u n

Fig. 1. A translation step of a SDTS

An input tree is processed from the root to the leaves, while unprocessed subtrees are marked by symbol . Initially, the whole source tree is marked as unproccessed. If the root of a currently processed subtree has a label from output alphabet or ε, then it is a leaf and we stop translation in this branch by removing the symbol . If we are processing a subtree, whose root is an internal node, first we reorder and delete children subtrees according to corresponding rule. Subsequently, if there are some leaf childrens, we reorganize them in such a way, that the result adheres to the output side of the rule.

Definition 9. A transformation generated by a SDTS (SSDTS, ESDTS)Ω is a set τ (Ω) = {(t s , t t ) | t s ∈ T N (Σ), root(t s ) = S, t t ∈ T N (∆), (t s ) ⇒ * Ω t t }.

A SSDTS enables very simple transformations of trees. It does not change structure of the source tree, it is only possible to delete, add or reorder leaves. A SDTS enables reordering of subtrees connected to the same node moreover. An ESDTS is the most powerful modification, unlike SDTS it enables also deleting of arbitrary subtree in the source tree.

A transformations performed by SSDTS as well as SDTS satisfy the definition of the type transformation. In the case of ESDTS a problem arises, because if we delete a subtree in the source tree, it is not processed anymore. Thus, it is not possible to check, whether this part of the source tree was correct.

There are several implemented transformation systems that are using SDTS and its modifications as underlying model. System SynDoc [19] is based on ES-DTS, and SDTT [5], ICA [21], HST [16] are based on SDTS.

Tree transformation grammar

A tree transformation grammar is similar to SDTS, however in this case we associate two groups of production rules. The first group -a source subgrammar contains some of the source grammar production rules and the second one -a target subgrammar conatins some of the target grammar production rules. Unlike in SDTS, nonterminals in the source and target subgrammar must be associated explicitely. This means, that it is possible to associate also nonterminals with different names. Additionally, tree-transformation grammars work with as many levels in the source tree as necessary. Definition 10. A tree transformation grammar -TTG is a 6-tuple G = (G s , G t , Sub s , Sub t , P A, SA), where -G s = (N s , Σ s , P s , S s ) and G t = (N t , Σ t , P t , S t ) are the source and target grammars, -Sub s ⊆ 2 Ps and Sub t ⊆ 2 Pt are sets of source and target subgrammars, -P A ⊆ Sub s × Sub t is a set of production group associations, -SA ⊆ N s × N t is a set of symbol associations.

There are some restrictions put on the source subgrammar. It must contain a single start nonterminal, and every other nonterminal in the source subgrammar must be derivable from this start nonterminal. Source subgrammars represent subtree patterns to be matched against in the source tree; target subgrammars represent subtrees, that are to be generated as part of the target tree. A target subgrammar can contain several start nonterminals, thus we can obtain a forest of target subtrees as a result. Transformation via TTG is performed by processing source tree nodes one by one. For a particular node we look for matching source subgrammars. If there is some, corresponding target subtrees are constructed and links among nodes in source subgrammar and target subgrammar are marked according to symbol associations. After the whole source tree has been processed, target subtrees can join to bigger trees according to the marked symbol associations.

Tree transformation grammars are described in [15]. Authors' intention was to define a powerful two-grammar transformations model and, at the same time, provide simple and natural way to write transformation specification.

Several modifications of tree transformation grammars have been implemented:

• Dual grammar translation scheme (DGTS) -system SSAGS [24].

• Single input production-explicitely qualified (SIPEQ) -system SIPEQ [15].

• TT grammar -system Alchemist [20].

However, semantics of the model remains unclear as no formal definitions have been introduced in any of the resources mentioned. Now we present definitions, that we created according to the alghorithm of tree transformation via TT grammars mentioned in [20].

Definition 11. A configuration of TTG Ω is a pair (t s , T t ), t s ∈ T Ns∪{ } (Σ s ) and T t ⊆ {(t, W ) | t ∈ T Nt (N t ∪ Σ t ), W ⊆ 2 (path(t)×path(t)) }.

A tree t s is the source tree with marked unprocessed nodes. T t is a set of target linked trees, i.e., it contains pairs of the form (t, W ), where t is a particular target tree and W is a set of path pairs that we call a set of links of a tree t. We use the notation W t as well.

Definition 12. A translation step of TTG Ω is a relation ⇒ Ω over configura- tions defined by (t s , T t ) ⇒ Ω (t s , T t ) ⇐⇒ (1) generating step -there is such a path w s in a tree t s that t s | ws = (A(t 1 , . . . , t n )), -t s = t s [w s ← p A( (t 1 ), . . . , (t n ))],

there is such a source subgrammar sg ∈ Sub s that t sg (a derivation tree corresponding to the rules sg) and A(t 1 , . . . , t n ) match, -there is such a target subgrammar tg ∈ Sub t that (sg, tg) ∈ P A and T tg = {r 1 , . . . r m } (derivation trees corresponding to the rules tg). Let us denote

R i = (r i , {(w 1 , w s w 2 ) | (label ri (w 1 ), label tsg (w 2 )) ∈ SA}), i ∈ {1, . . . , m}. Then T t = T t ∪ 1≤i≤m R i .

(2) connecting step

-t s = t s , -there are such R 1 , R 2 ∈ T t , R 1 = (r 1 , W 1 ), R 2 = (r 2 , W 2 ) that -root(r 2 ) = A ∈ N t , -there is such a path w ∈ path(r 1 ) that r 1 | w = A, -there is such a path w s ∈ path(t s ) that (w, w s ) ∈ W 1 and (ε, w s ) ∈ W 2 . Let r 3 = r 1 [w ← p r 2 ], W 3 = W 1 ∪ {(ww 1 , w 2 ) | (w 1 , w 2 ) ∈ W 2 } a R 3 = (r 3 , W 3 ). Then T t = T t − R 1 − R 2 ∪ R 3 .

Transformation works in similar way as with SDTS. The source tree is passed in the top-down manner, while unprocessed nodes are marked by symbol , initially the whole source tree is marked.

During the generation step, we first choose such a source subgrammar (pattern), that matches a subtree under currently processed node (Fig. 2). The model is nondeterministic, i.e., there can be more suitable source subrammars. Then we add target subtrees (corresponding to the associated target subgrammar) together with links to the set of linked target trees. Links are created according to symbol associations (Fig. 3). At last we remove symbol from current subtree and again we mark all connected subtrees to indicate they need to be processed.

If we apply connecting step (Fig. 4), we first choose two subtrees r 1 and r 2 from the set of target linked trees. These trees must satisfy some conditions; the root of the first one and a leaf of the second one must have the same label and must be linked to the same node in the source tree. Consequently, the set of target linked trees is updated so that subtrees r 1 , r 2 are removed and a new subtree created by connection of r 1 , r 2 is added. Links between this new subtree and the source tree will be updated as well according to the links in old subtrees. However, we want to obtain one tree as a result of transformation. Therefore in following definition of tree transformation via TTG we require the last configuration to consist of a single element.

Definition 13. A transformation generated by TTGΩ is a set τ (Ω) = {(t s , t t ) ⊆ T Ns (Σ s ) × T Nt (Σ t ) | ( (t s ), ∅) ⇒ * Ω (t s , {(t t , W )})}.

Descending tree transducer

A descending tree transducer is an automaton, which passes a source tree from the root to the leaves and performs changes according to the current state, node and lookeahead. Unlike previous formal models, it works with trees, where labels of internal nodes are from a ranked alphabet. Basically, ranked alphabet is a pair (Γ, rank), where Γ is an alphabet and rank : Γ → N is a ranking function, which assigns positive integer to each symbol in Γ . We usually omit the function rank in the notation and we say that Γ is a ranked alphabet. If Σ is an alphabet and Γ a ranked alphabet, then each internal node in a tree over (Γ, Σ) must have exactly as many children as is the value of the rank of its label. We will not introduce formal definitions here, all of them can be found in [10] and the notation is very similar to that one used in previous cases.

A DTT does not represent a model for two-grammars transformations since it works on higher level of abstraction. However, it is easy to restrict definitions in such a way, that we obtain DTT, which transforms derivation trees of a given source grammar into derivation trees of a given target grammar.

A DTT with finite and regular lookahead has been used in the transformation system SynDoc [17]. This system generates also an XSLT stylesheet as an output and it is possible to use existing tools for XSLT if further processing is needed. However, in that case the target correctness is not guaranteed anymore.

Higher order attribute grammar

Basically, an attribute grammar is a context free grammar, such that each rule is associated with a set of semantics rules. These rules have a form X.b := f (Y 1 .c 1 , . . . , Y n .c n ), where X, Y i are nonterminals, b, c i are attributes and f is an n-ary function.

All definitions presented in this section results from [27].

Definition 14. An attribute grammar -AG is a triple AG = (G, A, R), where

• G = (N, Σ, P, S) is a context-free grammar,

• A = X∈N ∪Σ AIS(X) is a finite set of attributes, where AIS(X) is a set of attributes associated with nonterminal X,

• R = p∈P R(p) is a finite set of attribute rules. If AIS(X) ∩ AIS(Y ) = 0, then X = Y . For every occurrence of a nonterminal in a derivation tree of G there must be exactly one attribute rule applicable for computation of a value for an attribute a ∈ A. Rules in R(p) have a form α = f (. . . , γ, . . .), where f is a name of the function, α and γ are attributes of a form X.a.

Definition 15. For each p : X 0 → X 1 . . . X n ∈ P we define a set of attribute evaluation occurrences as AF (p) = {X i .a | X i .a = f (. . .) ∈ R(p)}. An attribute X.a is called a synthetized attribute if there is a rule r : X → χ and X.a ∈ AF (r); an inherited attribute, if there is a rule q : Y → µXν and X.a ∈ AF (q). We denote by AS(X) a set of synthetized attributes of a nonterminal X and by AI(X) a set of inherited attributes of a nonterminal X. After evaluation process these attributes contain a subtree as a computed value. Thus, unlike in AG, in HAG the domain of the derivation tree and the domain of attributes overlap.

A higher-order attribute grammar (HAG) is an extended attribute grammar. A special type of attribute -nonterminal attribute is introduced. Definition 16. For each p : X 0 → X 1 . . . X n ∈ P a set of nonterminal attributes is defined:

N T A(p) = {X j |X j := f (. . .) ∈ R(p)}.

An unevaluated nonterminal attribute represents a leaf node of the actual tree. At this point we call it virtual nonterminal, since there is no subtree connected to it. After the evaluation is performed, a subtree is computed as a value for nonterminal attribute and consequently it is connected to this attribute (leaf node). Evaluated nonterminals and common nonterminals we also call instatiated nonterminals since they have got an instance, i.e. connected subtree. The set of instantiated nonterminals represents internal nodes of the actual tree.

A HAG has been implemented in transformation system SIMON [9], which takes advantage of the power of this model and enables several complex transformations. However, there is one major drawback. System requires a user to write a complete HAG as a transformation specification and this is usually a nontrivial task.

For HAG there has been defined formal model -a higher-order attribute tree transducer [23], which represents some abstraction and therefore it is more suitable for studying its properties.

Comparison results

Finally, we briefly introduce results obtained by comparing formal models for type transformations according to their transformational power. Since we defined transformations as relations over sets of trees, we can consider them as sets containing pairs of trees as elements. Thus, we can also compare them as sets. See Table 1 for comparison results. Symbol N indicates that transformations of two corresponding formal models are not comparable. More details and all formal proofs can be found in [6].

Conclusion and future work

In this paper we introduced a system for classification of XML documents transformations. Our intention was to simplify choosing of appropriate transformation system according to given requirements for transformation. We defined categories in bottom-up way, i.e. first we were examining implemented transformation systems and consequently we abstracted from them to higher-level groups of transformations sharing similar features. We were examining in detail formal models used for type transformation. We defined common framework for these models and we introduced current results of their mutual comparison. In our future work, we plan to make more comparisons according to transformational power and complexity as well. We intend to include also other models, which might appear to be suitable for XML document transformations.