[
Lists Home |
Date Index |
Thread Index
]
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
|
