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

RE: Validate an XPath with regex

• To: "Gary Stephenson" <garys@i...>,<xml-dev@l...>
• Subject: RE: Validate an XPath with regex
• From: "Dare Obasanjo" <dareo@m...>
• Date: Mon, 8 Apr 2002 18:08:36 -0700
• Thread-index: AcHfXuBi3wtiDZFxRT6wzHTNint3JwAAp8NA
• Thread-topic: Validate an XPath with regex

> -----Original Message-----
> From: Gary Stephenson [mailto:garys@i...] 
> Sent: Monday, April 08, 2002 5:33 PM
> To: xml-dev@l...
> Subject: Re:  Validate an XPath with regex
> 
> 
> > > Shouldn't it be possible to validate the syntax of an 
> XPath string 
> > > using regular expressions.
> >
> > No. You at least need to be able to match () pairs, this requires 
> > counting, so can't be done with a regular expression.
> 
> I"m afraid I simply don't understand.  :-(  Are you sure 
> about this?  Is there perhaps a qualitative difference 
> between "counting" and (recursively) detecting balancing delimiters?
> 
> Since reading the above I have been unsuccessfully trying to 
> trip my XPath parser up, by feeding it expressions containing 
> unbalanced parens and/or square brackets.  Could you perhaps 
> provide some examples that you would expect to cause problems.
> 
> Hmmm..., BNF grammars are used ubiquitously to generate 
> parsers which are in turn quite capable of detecting 
> unbalanced delimiters in their input.  So, if what you say is 
> correct, then BNF grammars must be inherently more powerful 
> than regular expressions - yes?  But aren't they both simply 
> forms of regular grammars cum finite automata?
> 

I may have barely made it out of my CS Theory class without flunking but
I do seem to remember that regular expressions and DFAs were equivalent
while the more powerful PDAs were equivalent to context free grammars. I
also faintly remember something about context free grammars being higher
on the Chomsky hierarchy than regular expressions. Hmmmm, I think I need
some links...

http://www.mri.mq.edu.au/ltg/slp803D/class/Guan/slp803ws-19.htm#item24
http://www.wikipedia.com/wiki/Chomsky_hierarchy

...found 'em.



-- 
PITHY WORDS OF WISDOM 
A journey of a thousand miles begins with a cash advance.
 
This posting is provided "AS IS" with no warranties, and confers no
rights. 
You assume all risk for your use. (c) 2002 Microsoft Corporation. All
rights reserved.

• Follow-Ups:
  • Re: Validate an XPath with regex
    • From: "Gary Stephenson" <garys@i...>

• Prev by Date: Re: Validate an XPath with regex
• Next by Date: Re: Validate an XPath with regex
• Previous by thread: XML in C
• Next by thread: Re: Validate an XPath with regex
• Index(es):
  • Date
  • Thread