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

What class of grammars is an =?UTF-8?Q?XPath=3F?=

• From: rjelliffe <rjelliffe@allette.com.au>
• To: <xml-dev@lists.xml.org>
• Date: Thu, 27 Jan 2011 19:45:53 +1100

 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

• Follow-Ups:
  • Re: What class of grammars is an XPath?
    • From: Dimitre Novatchev <dnovatchev@gmail.com>
  • 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>