Re: [xsl] XPath and Recursive Descent Parsers

[Jeff Kenton <jkenton@xxxxxxxxxxxxx>]

martin@xxxxxxxx wrote:
> hi,
>
> has anyone tried using recursive descent to parse XPath expressions?

It has certainly been done.  There are quite a few XSLT processors in the world -- I'd bet at least half of them use recursive descent.
> I've written a recursive descent parser generator in XSLT, i want to
> generate an XPath parser, but wondering if i'm going to run into problems
> with my left-recursion eliminations.
>
> to avoid infinite recursion i've rewritten left-recursive rules, for
> example, from ->
>
> relativeLocationPath ::= step
> 		| relativeLocationPath '/' step
> 		| relativeLocationPath '//' step
>
> to ->
>
> relativeLocationPath ::= step relativeLocationPathRest
>
> relativeLocationPathRest ::= '/' step relativeLocationPathRest
> 		| '//' step relativeLocationPathRest
> 		|

Note that the corresponding part of the XPath 2.0 WD has:

   RelativePathExpr ::= StepExpr ( ( "/" | "//" ) StepExpr ) *

This is clearer, and avoids any possible infinite recursion.


I'm amazed that you've actually done this using XSLT.  I'd love to see what you've done.

--

--------------------------
Jeff Kenton
DataPower Technology, Inc.



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