How to print all expressions that match a regular expression
steve at REMOVE-THIS-cybersource.com.au
Sun Feb 7 01:26:36 CET 2010
On Sat, 06 Feb 2010 16:05:15 -0800, hzhuo1 at 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.
(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
[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".]
More information about the Python-list