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

Re: Validate an XPath with regex


regex validate date
> Does your "regular expression engine" handle the following grammar?
>     A ::= 'x' | '(' A ')'
> I suspect it does.

Wow, I had just finished writing a reply saying that it did _not_ handle
such a grammar, but then I thought I'd better just check first - and lo and
behold:  you are quite correct - it does indeed!    So, what I thought was
my "regular expression engine" is in fact my "context-free grammar" engine.

> Specifically, a PDA
> includes a stack of unbounded size, which can be used (for instance) to
keep
> track of how many '(' have been seen (to an arbitrary depth), and thus how
> many ')' must follow. A finite automaton can't do that. (Although you
could
> define one to recognize balanced parens up to a pre-specified depth.)

This is the "regular expressions can't count" thingie again - yes?   I think
I can see now what has happened.  I originally got my regexp processor
working fine (and reasonably fast too), but then found it wouldn't backtrack
properly when trying to get it to also process BNF grammars. Due to my
seemingly unbounded ignorance, I jumped to the conclusion that this was
highlighting a flaw in my regexp processor.  So I went to a lot of trouble
to implement this "unbounded stack" to allow for perfect backtracking,
without ever twigging to the fact that the original regexp processor was in
fact fine all along, and that the BNFs actually represented a somewhat
different class of problem!  Had I realised this, I would have kept my
original (much faster) regexp implementation, and developed a separate "PDA"
processor altogether.

In the end, I guess there's much to be said for having a theoretical basis
for what one is doing, instead of just hacking away until you get the
results you're looking for. ;-)

cheers and thanks for the insights,

gary


PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
 

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.


Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.