Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

generating strings from a regular expression

by indapa (Monk)
on Jun 21, 2002 at 21:08 UTC ( #176403=perlquestion: print w/replies, xml ) Need Help??

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

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?

  • Comment on generating strings from a regular expression

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

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

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; }
    would be simple.
    --
    ($_='jjjuuusssttt annootthheer pppeeerrrlll haaaccckkeer')=~y/a-z//s;print;

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://176403]
Approved by FoxtrotUniform
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (6)
As of 2019-12-12 08:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?