How to print all expressions that match a regular expression

[Steven D'Aprano]

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 
extraordinary.


[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".]


-- 
Steven