Enumerating Regular Expressions

[blair.bethwaite]

Hi all,

Does anybody know of a module that allows you to enumerate all the
strings a particular regular expression describes?

Cheers,
-Blair

[James Stroud]

bl************* @gmail.com wrote:

Hi all,

Does anybody know of a module that allows you to enumerate all the
strings a particular regular expression describes?

Cheers,
-Blair

You mean like re.compile(r'.* ') ?

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/

[blair.bethwaite]

James Stroud wrote:

You mean like re.compile(r'.* ') ?

No. I mean like:

regex = re.compile(r'a| b')
regex.enumerate () a
b

[James Stroud]

bl************* @gmail.com wrote:

James Stroud wrote:

You mean like re.compile(r'.* ') ?

No. I mean like:

regex = re.compile(r'a| b')
regex.enume rate()

a
b

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?

James

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/

[blair.bethwaite]

James Stroud 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?

Well sure it might be a little difficult to figure _that_ out, although
probably not all that hard if you converted to an FSA or something. I
imagine detecting looping would be as simple as applying the right
graph algorithm.

But that's not the point, you don't strictly need to know in advance
whether the regex represents a finite or infinite language. I just
want to enumerate it, if it's going to take longer than the life of the
universe and a stack size to match to do it, then so be it. It's
surely up to the user to be careful about how they form their
expressions. One way to get around it would be to disallow the *
operator in enumerations.

Cheers,
-Blair

[Michael J. Fromberger]

In article <e3**********@d aisy.noc.ucla.e du>,
James Stroud <js*****@ucla.e du> wrote:

bl************* @gmail.com wrote:

James Stroud wrote:

You mean like re.compile(r'.* ') ?

No. I mean like:

>regex = re.compile(r'a| b')
>regex.enume rate()

a
b

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.

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.

Cheers,
-M

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[blair.bethwaite]

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

[Dale Strickland-Clark]

Any regular expression that has an asterisk in it has an infinite number of
possible matches.

If it has two asterisks, that's an infinite number squared and that's a
really big number.

You wouldn't want to print them out.
bl************* @gmail.com wrote:

Hi all,

Does anybody know of a module that allows you to enumerate all the
strings a particular regular expression describes?

Cheers,
-Blair

--
Dale Strickland-Clark
Riverhall Systems - www.riverhall.co.uk

[blair.bethwaite]

Dale Strickland-Clark wrote:

Any regular expression that has an asterisk in it has an infinite number of
possible matches.

If it has two asterisks, that's an infinite number squared and that's a
really big number.

You wouldn't want to print them out.

We've been over this already. Why are people getting stuck on infinite
regular languages? I've made it quite clear that I'm only really
interested in doing this for finite languages, but that shouldn't
matter anyway. Maybe I should phrase it differently; I want a tool
that can enumerate a regex, with support for generating each string
described by the regex in some predefined order. So something like:
# pattern is the regex representing language L
reg_lang_gen = re.compile('pat tern').enumerat or()
while len(s) < n:
s = reg_lang_gen.ne xt() # get next string in L
...

It's easy to imagine a problem where you'd want to enumerate a regex
that represents an infinite regular language. E.g. a particularly dumb
bruteforce password cracker, you might want to keep generating strings
from the language of choice until you find one that matches your
encrpyted version, naturally you might want to stop if you hadn't found
it within 10 characters or so.

Cheers,
-B

[Diez B. Roggisch]

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

Just wandering: whatfor do you perceive it useful? I've been done quite a
few things with rexes - yet never it occured to me that I'd be in need of
enumeration all the gazillion of possible matches. YMMV - so what for?

Regards,

Diez