[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Validate an XPath with regex
> 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! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|