RE: [xml-dev] Validate an XPath with regex

["Dare Obasanjo" <dareo@microsoft.com>]

> -----Original Message-----
> From: Gary Stephenson [mailto:garys@ihug.com.au] 
> Sent: Monday, April 08, 2002 5:33 PM
> To: xml-dev@lists.xml.org
> Subject: Re: [xml-dev] 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.