A formal model of a subset of XSLT is analyzed with extensive examples.
From a "language theoretic point of view" XSLT is shown to
"correspond to tree-walking tree transducers with registers."
Four XSLT language features are the key to its expressiveness:
...Modes enable XSLT to act differently upon arrival at the same element types
Variables can be used...to perform joins between data values.
A less apparent application is to use them as a 'look-ahead'.
...we give a fragment of an XSLT program evaluating the truth value
of a binary tree which represents a Boolean circuit.
Essentially, the use of variables allows for a bottom-up
computation. In brief, when arriving at an or-labeled node, the program returns
the correct truth value based upon the truth values of the first and second subtree.
Passing of data values to other template rules can be crucial for performing joins
if the items to be joined do not occur at the same node. Moreover, when node IDs
are present in the XML document, we can use this mechanism to place 'pebbles'
on the input document which enables us to do complicated grouping operations...
XPath can also select siblings and ancestors.
Exactly these four features render XSLT into a quite
powerful transformation language.
A semantics of the sub-language is derived with rewrite relations
and several properties of XSLT are proven:
XSLT0 [the sub-language], and hence XSLT, is quite expressive in the sense that
it can simulate most other current XML query languages, and that it can express all join-
free MSO [Monadic Second Order Logic] patterns. The latter even implies that XSLT is strictly more expressive than
other XML query languages. On the negative side we obtain that deciding termination
is undecidable and that XSLT0 is not closed under composition.
Personally, I find that
concise mathematical descriptions
accompanied by examples like this,
that hone in on a language's key features,
provide more insight into how a language works
than verbose language specifications that are hard to grasp
as a whole.
Interesting survey papers]
(A Formal Model for an Expressive Fragment of XSLT,
Bex, Maneth, and Neven, 2000)
Posted to xml by jon fernquest on 10/17/02; 12:35:08 AM