[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: What class of grammars is an XPath?

• From: Dimitre Novatchev <dnovatchev@gmail.com>
• To: rjelliffe <rjelliffe@allette.com.au>
• Date: Thu, 27 Jan 2011 05:26:01 -0800

> Anyway, it is an interesting question. I think the same question could be
> asked, rephrased, as "what is the smallest class of formal grammars that
> every Xpath (evaluating to boolean) belongs to?"

It isn't a regular expression -- XPath expressions may have an
unlimited nestedness.

It is definitely a context-free (CF) grammar and even more
specifically, it is an LR(1) grammar.

Three years ago I defined the full XPath 2.0 grammar (with one
exception -- I wasn't aware at that time of nested XPath comments --
but adding comments nestedness doesn't change the picture at all) as a
set of rules describing an LR(1) language and providing these as input
to YACC I get the set of tables necessary to drive a general LR(1)
parser.

The rules are all written in XML, the parser is pure (and quite short)
XSLT 2.0 function.

If anybody is interested in the XML rules for XPath 2.0, I can provide
them, as I already have to people who expressed interest. The modified
YACC that generates the set of rules and the parsing tables as XML is
available in the FXSL CVS. Also there is the f:lr-parse() general
LR(1) parser, that works directed by such kind of YACC-generated
tables.


-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.





On Thu, Jan 27, 2011 at 12:45 AM, rjelliffe <rjelliffe@allette.com.au> wrote:
> A correspondent recently asked me what formal class of grammars Schematron
> schemas belonged to.
>
> He was interested, I gather, because I gather he expected to be able to know
> what data structures would be needed for writing an implementation, since
> the position in a Chomsky hierarchy can tell you the minimum class of
> automaton.
>
> I told him first that I thought Schematron was not a useful fit in the
> Chomsky hierarchy,  see
>  http://broadcast.oreilly.com/2010/07/validating-operator-grammars-i.html
>
> (You could also say it was an indexed tree grammar implementable with a
> branching automaton, perhaps.)
>
> Anyway, it is an interesting question. I think the same question could be
> asked, rephrased, as "what is the smallest class of formal grammars that
> every Xpath (evaluating to boolean) belongs to?"
>
> Anyone got any pointers or ideas on this? Pointers to any academic work
> would be really interesting.
>
> Cheers
> Rick Jelliffe
>
>
>
>
> _______________________________________________________________________
>
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
>
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
> subscribe: xml-dev-subscribe@lists.xml.org
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>
>



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.

• Follow-Ups:
  • Re: What class of grammars is an XPath?
    • From: Michael Kay <mike@saxonica.com>

• References:
  • Which algorithm do XML Schema validators use to decide if a stringmatches a regular expression?
    • From: "Costello, Roger L." <costello@mitre.org>
  • Re: Which algorithm do XML Schema validators use to decideif a string matches a regular expression?
    • From: Michael Kay <mike@saxonica.com>
  • What class of grammars is an =?UTF-8?Q?XPath=3F?=
    • From: rjelliffe <rjelliffe@allette.com.au>