OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



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

[ Lists Home | Date Index | Thread Index ]

> 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

Apologies for being more than a little "CS Theory" challenged! ;-)

Whilst BNF is used to describe context-free grammars in general, that surely
doesn't prevent particular instances from also being regular - does it?
Thus, the original question comes down to:

Is the XPath grammar equivalent to a regular grammar (ie Chomsky Type 3 )?

I think the answer is "yes" - simply because my XPath processor works for
all the tests I've thrown at it so far (But I'm still by no means certain).

<out-of-my-depth>'ly yrs,



News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS