generating strings from a regular expression

[indapa]

My brain was wandering this afternoon... Is it possible to generate strings given a regular expression?

Most of the time I have a string, and I want to run it through a regex to see if it matches or not. But coming from the opposite direction, given a regular expression R, is it possible to generate the set of all strings that match R?

[kvale]

In general, no: /a+/ generates the language (a, aa, aaa, ...) and is infinite in size. For regexes that generate a finite language, one proven method is to test all possible strings up to a chosen length to see if they match the regex. But that is slow.
Another approach is rewrite the regex as a BNF-style grammar. One can then parse the grammar into a tree and walk all possible paths in this tree. This will generally be faster than the exhaustive method.
-Mark

[traveler]

While it is not exactly what you are looking for, you might want to check out Grail+ which has tools to do something very close to what you are asking.

As was pointed out already it is not possible to generate an exhaustive list. It should be possible, though, to generate the shortest strings to match a particular RE within reason. Clearly /a.b/ matches a<any single char>b so there are lots of possibilities. I seem to recall using such a tool years ago, but cannot find it now. However you can check out AAAAA which generates short and long strings. Unfortunately, I do not think it uses Perl REs...

Oh, and don't confuse the re "a" which matches a single 'a' with the perl m/a/ which will match "any" string with an 'a' in it.

HTH, --traveler

[robobunny]

it would depend on the regex. it certainly isn't possible to generate the set of all strings that match /.*/, for example, because it is infinite.

[dws]

But coming from the opposite direction, given a regular expression R, is it possible to generate the set of all strings that match R?

No, for the reason cited above in this thread. The best you can do is generate representative strings. Methings japhy did something along these lines a while back, but da*ned if I can find it.

[Cody Pendant]

I'm just wondering what your actual "strings" are. If they're strings of alphanumeric characters of fixed or finite length, of course that's the kind of thing that Perl can do very well.

Something like

$inverse_regex = 'a.b';
for (0..9,a..z){
($result = $inverse_regex) =~ s/\./$_/;
print $result;
}

would be simple.
--


($_='jjjuuusssttt annootthheer
     pppeeerrrlll haaaccckkeer')=~y/a-z//s;print;