RE: New XSL Optimization

[Kay Michael <Michael.Kay@xxxxxxx>]

> 	As my ME project, I have implemented a new technique for finding
> the matching patterns of a XSL stylesheet at all the nodes of a XML
> document. 

Sounds like a useful bit of research, will it be published?

>Basically I implemented the new technique for finding the
> matching patterns over the Xt-XSL engine by James Clark which uses the
> December-1998 XSL WD standard.

There are some simplifying features in the April 1999 draft which eliminate
some of the pathological (and poorly-defined) cases. But there are also some
new complications, notably variables and positional qualifiers. Do the
differences affect the algorithm?

> 	Briefly the technique is as follows:
> 
> 1. First I extracted out the match patterns to be matched from the XSL
> stylesheet. Then the match patterns are converted to a context-free
> grammar whose language is the matching trees in pre-order 
> linearized form.

Sounds good, I wish I understood it!
> 
> 2. The input XML document is linearized by pre-order 
> traversal of the XML document.
> 
> 3. An Earley parser built using the Context free grammar 
> devoloped in 1 is given the linearized input got in 2. This earley parser 
> reports all the match patterns that are matched at all the nodes of the
XML 
> document. If the match patterns have qualifiers, then the earley parser 
> also outputs the nodes at which the qualifiers has to be checked.

Does this perform n*m tests, where n is the number of nodes and m the number
of match patterns? If so, how is it an improvement?

> 
> Also in my implementation I have used the SAXON patterns for 
> simplicity.
> 
Presumably not the latest version (SAXON 4.3), which implements the April
1999 pattern syntax in its entirety (I believe). 

Mike Kay


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list