How to print all expressions that match a regular expression

[Alf P. Steinbach]

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

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