RE: New XSL Optimization

[S Manimaran <mani@xxxxxxxxxxxxxxxxx>]

Hi,

On Thu, 24 Jun 1999, Kay Michael wrote:

> Date: Wed, 23 Jun 1999 15:07:17 +0100
> From: Kay Michael <Michael.Kay@xxxxxxx>
> Subject: RE: New XSL Optimization
> 
> > 	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?
> 

	Still my thesis report is not fully over. Once it is done, I will
make it available.

> >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?
> 

	Actually it is a matter of generating a new Context Free Grammar
(CFG) for the new patterns defined in the April,1999 XSL WD standard. I
had a look at the SAXON(4.3) patterns which has the April,1999 XSL
standard. I don't see any difficulty in generating a CFG for it. BTW I
have used the ANTLR LL(k) parser for generating the CFG from the match
patterns. 
	The qualifiers in any case does not affect the CFG in anyway
because qualifiers are tested separately at the nodes reported by the
Earley parser.

> > 	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?
> 

	No, it does not perform n*m tests. Because Earley parser reports
only those nodes which has to be tested for the qualifiers for nodes which
satisfies the match pattern otherwise i.e Earley parser goes ahead
asssuming the qualifier will be satisfied and finally when a match pattern
matches at a node, it indicates that the match pattern matches at this
node provided the qualifiers are satisfied at the nodes reported by it.
A nice one-to-one correspondence is maintained between the number of
qualifiers in a match pattern and the number of nodes reported by Earley
parser for checking against the qualifiers.

> > 
> > 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
> 

	Yes, infact right now, I have used the SAXON 4.2 patterns which is
the December,1998 XSL WD standard. But anyway as I said it is not
difficult to get a CFG for the new standard as well, using the SAXON 4.3
patterns.

-S.Manimaran,

-------------------------------------------------------------------------------
URL::http://www2.csa.iisc.ernet.in/~mani/
Indian Internet Chess Server IICS::telnet 144.16.67.53 5000
Join frenchlist by sending a mail to french@xxxxxxxxxxxxxxxxx
f16    Fingerprint16 = EC FF 4D 6C 3A 09 84 30  AA B5 F0 A2 38 A0 4C A4


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