How to generate random strings that match a given regexp?

Question

Duplicate:

Random string that matches a regexp

No, it isn't. I'm looking for an easy and universal method, one that I could actually implement. That's far more difficult than randomly generating passwords.

---

I want to create an application that takes a regular expression, and shows 10 randomly generated strings that match that expression. It's supposed to help people better understand their regexps, and to decide i.e. if they're secure enough for validation purposes. Does anyone know of an easy way to do that?

One obvious solution would be to write (or steal) a regexp parser, but that seems really over my head.

I repeat, I'm looking for an easy and universal way to do that.

Edit: Brute force approach is out of the question. Assuming the random strings would just be [a-z0-9]{10} and 1 million iterations per second, it would take 65 years to iterate trough the space of all 10-char strings.

Answer 1

Parse your regular expression into a DFA, then traverse your DFA randomly until you end up in an accepting state, outputting a character for each transition. Each walk will yield a new string that matches the expression.

This doesn't work for "regular" expressions that aren't really regular, though, such as expressions with backreferences. It depends on what kind of expression you're after.

Answer 2

if your only criteria are that your method is easy and universal, then there ain't nothing easier or more universal than brute force. :)

for (i = 0; i < 10; ++i) {
    do {
        var str = generateRandomString();
    } while (!myRegex.match(str));
    myListOfGoodStrings.push(str);
}

Of course, this is a very silly way to do things and mostly was meant as a joke.

I think your best bet would be to try writing your own very basic parser, teaching it just the things which you're expecting to encounter (eg: letter and number ranges, repeating/optional characters... don't worry about look-behinds etc)

Answer 3

The 'easiest' way would be to generate all possible strings of length 'n' where n is 0 and goes to infinity. Test each string with the reg-exp. Once 10 matches are found, stop.

This is obviously very inefficient.

Answer 4

Take a look at Perl's String::Random.

Answer 5

For an easy way to visualize regular expressions, try this:

Str Friend

If it's strictly for teaching, this visualization of a reg exp is certainly nice.

Answer 6

The universality criterion is impossible. Given the regular expression "^To be, or not to be -- that is the question\:$", there will not be ten unique random strings that match.

For non-degenerate cases:

moonshadow's link to Perl's String::Random is the answer. A Perl program that reads a RegEx from stdin and writes the output from ten invocations of String::Random to stdout is trivial. Compile it to either a Windows or Unix exe with Perl2exe and invoke it from PHP, Python, or whatever.

Also see Random Text generator based on regex

Answer 7

One rather ugly solution that may or may not be practical is to leverage an existing regex diagnostics option. Some regex libraries have the ability to figure out where the regex failed to match. In this case, you could use what is in effect a form of brute force, but using one character at a time and trying to get longer (and further-matching) strings until you got a full match. This is a very ugly solution. However, unlike a standard brute force solution, it failure on a string like ab will also tell you whether there exists a string ab.* which will match (if not, stop and try ac. If so, try a longer string). This is probably not feasible with all regex libraries.

On the bright side, this kind of solution is probably pretty cool from a teaching perspective. In practice it's probably similar in effect to a dfa solution, but without the requirement to think about dfas.

Note that you won't want to use random strings with this technique. However, you can use random characters to start with if you keep track of what you've tested in a tree, so the effect is the same.

Answer 8

If you want to see how a parser would read a regular expression (an honest-to-goodness one, not Perl's regex) and generate a random string, I have some python code that does it.