[xquery-talk] XQuery static typing algorithms?
mike at saxonica.com
Mon Nov 24 17:01:23 PST 2008
There's a useful paper by Henry Thompson:
This algorithm is implemented very directly in the Saxon schema processor.
The hardest part is where he refers to Aho & Ullmann for determinizing the
FSA; the A&U algorithm requires very careful reading.
He also published a refinement to handle content models with numeric limits
other than 1 and infinity more efficiently:
I found that one tough to implement directly because he hand-waves about the
rules for determinizing the FSA, which seems to be the tough part. I ended
up doing my own thing with counters - which is highly dangerous in this
space, there is a tendency to find a fundamental flaw in your algorithm
after 3 years exposure in the field.
> -----Original Message-----
> From: talk-bounces at x-query.com
> [mailto:talk-bounces at x-query.com] On Behalf Of Per Bothner
> Sent: 24 November 2008 15:30
> To: talk at x-query.com
> Subject: Re: [xquery-talk] XQuery static typing algorithms?
> Thanks to both Jens Teubner and Bas de Bakker for your suggestions!
> Jens Teubner wrote:
> > My personal impression is that, if you want to be
> > the best way to start is to literally implement all the
> judgments in
> > the W3C Formal Semantics.
> In general that is good advice, but when it comes to
> subtyping, then the Formal Semantics doesn't provide
> judgements that are implementable, as far as I can tell:
> 8.3.2 Subtyping (<:)
> The above definition, although complete and precise, does not
> give a simple means to compute subtyping. Notably the
> definition above refers to values, which are not available at
> static type checking time.
> The structural component of the [XPath/XQuery] type system
> can be modeled by regular expressions. Regular expressions
> can be implemented by means of finite state automata.
> Computing subtyping between two types can then be done by
> computing if inclusion holds between their corresponding
> finite state automata.
> Finite state automata and how to compute operations on those
> automata, such as inclusion, emptiness or intersection, have
> been extensively studied and documented in the literature.
> The interested reader can consult the relevant literature on
> tree grammars, for instance [Languages], or [TATA].
> --Per Bothner
> per at bothner.com http://per.bothner.com/
> talk at x-query.com
More information about the talk