[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...>
• Subject: Re: Validate an XPath with regex
• From: Michael Dyck <michaeldyck@s...>
• Date: Mon, 08 Apr 2002 23:24:55 -0700
• Cc: xml-dev@l...
• Organization: intermittent
• References: <3B1C9D22-47A6-11D6-8473-000502CB905D@n...><200204080834.JAA03071@p...><003701c1df5e$281acf10$0fc8198a@gateway>

Gary Stephenson wrote:
> 
> I have been unsuccessfully trying to trip my XPath parser up, by feeding
> it expressions containing unbalanced parens and/or square brackets.

Then your parser is probably not a finite automaton. That is, the language
it recognizes is not a regular language.

Does your "regular expression engine" handle the following grammar?
    A ::= 'x' | '(' A ')'
I suspect it does. But this is not a regular expression, and cannot be
transformed into a regular expression. It is a context-free grammar, and
defines a context-free language.

> BNF grammars must be inherently more powerful than regular expressions

Yes.

> But aren't they both simply forms of regular grammars cum finite automata?

Nope. BNF (context-free) grammars are equivalent in expressive power to
push-down automata, which are not finite automata. 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.)

-Michael Dyck

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

• References:
  • Validate an XPath with regex
    • From: Niels Peter Strandberg <nielspeter@n...>
  • Re: Validate an XPath with regex
    • From: David Carlisle <davidc@n...>
  • Re: Validate an XPath with regex
    • From: "Gary Stephenson" <garys@i...>

• Prev by Date: Re: ?porting DTD namespace support to java [Re: WD for Namespaces 1.1
• Next by Date: Re: WD for Namespaces 1.1
• Previous by thread: Re: Validate an XPath with regex
• Next by thread: Re: Validate an XPath with regex
• Index(es):
  • Date
  • Thread