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