Enumerating Regular Expressions

[blair.bethwaite at gmail.com]

Michael J. Fromberger wrote:
> > You see the difficulty don't you? How will the computer know in advance
> > that the regex matches only a finite set of possible strings?
>
> You don't.  Hence, you want something that behaves like a generator, and
> will produce the strings one at a time.  Preferably, for the purposes of
> useful computation, in some canonical order.

Precisely, probably in order of length and value.

> I'm sorry to say I don't know of an existing Python module to do this,
> although you could write one for at least the basic regular expression
> operators if you wanted.  The basic problem isn't all that hard to
> solve, though the full generality of the re module's input syntax is far
> more expressive than truly "regular" expressions from language theory.

I thought that was the case, I've found a paper on the topic at least.
Maybe once I've finished some other work I'll give it a shot.  It seems
like a fairly useful thing to be able to do with a regular expression
so I just guessed that somebody must have done it already.  Perhaps I
can find it for another language.  I'm not so sure I fancy the idea of
digging around in the re module in order to add the functionality
there...

-Blair