* Steven D'Aprano:
On Sat, 06 Feb 2010 16:05:15 -0800, hzh...@gmail.com wrote:
Thanks for your reply.
So there isn't such a routine just because some of the regular
expressions cannot be enumerated. However, some of them can be
enumerated. I guess I have to write a function myself.
How do you expect to tell the ones that can be enumerated apart from
those that can't be?
Regular expressions are programs in a "regex" programming language. What
you are asking for is the same as saying:
"Is there a program that can enumerate every possible set of data that is
usable as valid input for a given program?"
This, in turn, is equivalent to the Halting Problem -- if you can solve
one, you can solve the other. You might like to google on the Halting
Problem before you spend too much time on this.
Hm, well, text editors /regularly/ do repeated regular expression searches,
producing match after match after match, on request.
To use that /expression/, it seems that Theory is yet again up against Hard
Reality.
In such a contest where something doesn't quite /match/, is the Map, the
Terrain, or perhaps the Interpretation of how the Map applies to Terrain, at fault?
(Note, however, it isn't necessary to solve the Halting Problem for *all*
cases in order to have a useful Endless Loop Detector program.)
Why do you think you need this? Seems to me you're starting on an
extraordinarily difficult job. I hope the benefit is equally
extraordinary.
Depending on the application there may be more efficient ways than applying a
general purpose regexp matcher.
Don't know about modern *nix but in the old days there were different greps for
different purposes, egrep, fgrep, whatever.
Aside: the only article by Niklaus Wirth that I can remember reading was about
how to transform algorithms to more efficient ones by exploiting the invariants,
and one of his examples was simple text searching, where you can advance the
pattern a number of characters depending on the current non-matching character.
[Aside: Python regexes aren't Turing Complete. I'm not sure about Perl
regexes. Either way, this might actually be less difficult than the
Halting Problem, as in "amazingly difficult" rather than "impossible".]
Cheers,
- Alf
--
http://mail.python.org/mailman/listinfo/python-list
