generating strings from a regular expression

indapa has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: generating strings from a regular expression by kvale (Monsignor) on Jun 21, 2002 at 21:18 UTC
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	[reply]
Re: generating strings from a regular expression by traveler (Parson) on Jun 21, 2002 at 22:11 UTC
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	[reply]
Re: generating strings from a regular expression by robobunny (Friar) on Jun 21, 2002 at 21:20 UTC
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.	[reply]
Re: generating strings from a regular expression by dws (Chancellor) on Jun 21, 2002 at 21:34 UTC
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.	[reply]
Re: generating strings from a regular expression by Cody Pendant (Prior) on Jun 22, 2002 at 00:42 UTC
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; }` [download] would be simple. -- `($_='jjjuuusssttt annootthheer pppeeerrrlll haaaccckkeer')=~y/a-z//s;print;` [download]	[reply] [d/l] [select]