xsl-list
[Top] [All Lists]

Re: [xsl] Are XPath expressions parsed using compiler parsing techniques?

2022-05-10 05:07:22
On 08/05/2022 22:20, Roger L Costello costello(_at_)mitre(_dot_)org wrote:
An XPath expression is a query. Not against a database, but against an XML 
document. Are XPath expressions parsed using compiler parsing algorithms? Is a 
syntax tree constructed for an XPath expression? Is the syntax tree traversed?

In my work with Saxonica I've implemented XPath expression parsers both by using a parser-generator and transcription/tweaking of an extant recursive descent/precedence parser originated by and described by Michael Kay earlier.

I used Gunther Rademacher's excellent  REx parser generator ( https://www.bottlecaps.de/rex/) first to generate an XPath parse tree for  streamability analysis (see https://www.balisage.net/Proceedings/vol13/html/Lumley01/BalisageVol13-Lumley01.html ) where I really just wanted a parse tree to analyse. REx made the process of building the parse tree very simple.

Later, when adding dynamic XPath support (xsl:evaluate) to SaxonJS (see https://archive.xmlprague.cz/2017/files/xmlprague-2017-proceedings.pdf#page=13 ) I again used the REx-generated parser, adding a 'compiler/analyser/code-generator' written in Javascript to generate the appropriate SaxonJS execution plan.

Eventually SaxonJS expanded to being able to support the fn:transform() function, which required the development of a complete XSLT compiler, written mostly in XSLT with a (Javascript-coded) extension function compile-XPath(). (See https://www.balisage.net/Proceedings/vol19/author-pkg/Lumley01/BalisageVol19-Lumley01.html and http://archive.xmlprague.cz/2019/files/xmlprague-2019-proceedings.pdf#page=235 )

At this stage we started again with the REx-based parser, but after getting the main compiler running rewrote the parser by transcribing the Java-based parser/compiler that Saxonica had developed over many years into a Javascript version, which was probably an order-of-magnitude more efficient than the REx-based predecessor.

The real differences in the two approaches are that:

 * Using a parser-generator can get you running much more quickly and
   able to adapt to changes in the grammar much more rapidly, but
   diagnostics at the parse stage are at most very generic ("Expecting
   'foo' at line 17, character 6, got 'bar'") and when you're running
   outside development you're running a much less time-efficient parser.
 * Writing a specific parser (assuming the grammar isn't full of
   ambiguity traps) takes much longer, but gives you much better
   control over the results and diagnostics. Error messages can be much
   better tailored ("The cardinality indicator for a sequence type must
   be one of *|+|? - provided '$') and concurrent type analysis,
   small-scale static error detection and small-scale optimisation
   (e.g. arithmetic constant expression reduction as Dimitre has shown)
   can be incorporated.
   But if the grammar changes drastically, you might have to do a lot
   of rework, dependent upon the architecture of your parser. (As an
   example adding some support for putative XPath4 operators (e.g.
   'otherwise') needed some changes to the tokenizer and additional
   cases in some of the parse function switches, but where the new
   operator fitted into the class-based parser was fairly straightforward.)

Having recently done some similar work on parsing InvisibleXML, these lessons still stand - a purpose-written parser will give much better control and performance than a generated one, at the cost of reduced 'flexibility'. But I should also finish with a caution, that most of us working in this area would echo strongly:

   *Don't build your parser without investing (heavily) in a
   test-driver and test-suite* - the more tests you can add, the
   better, even the really weird ones, which may eventually occur 'in
   nature'. (As Michael Kay hinted, 'or and not' is a valid XPath
   expression, only one of whose tokens is an operator - I think!)

--
*John Lumley* MA PhD CEng FIEE
john(_at_)saxonica(_dot_)com
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--

<Prev in Thread] Current Thread [Next in Thread>