# All possible values that will match a regular expression

This is a similar question to this, but I am looking for the set of all possible values that will match a regular expression pattern.

To avoid an infinite set of possible values, I am willing to restrict the regular expression pattern to a subset of the regular expression language.

Here's the approach I took (Python code):

def generate_possible_strings(pattern):
'''
input: 'K0[2468]'
output: ['K02', 'K04', 'K06', 'K08']

generates a list of possible strings that would match pattern
ie, any value X such that re.search(pattern, X) is a match
'''
query = re.compile(pattern, re.IGNORECASE)
fill_in = string.uppercase + string.digits + '_'

# Build a re for a language subset that is supported by reverse_search
bracket = r'$[^$]*\]' #finds [A-Z], [0-5], [02468]
symbol = r'\\.' #finds \w, \d
expression = '|'.join((bracket,symbol)) #search query

tokens = re.split(expression, pattern)
for c in product(fill_in, repeat=len(tokens)-1):
candidate = ''.join(roundrobin(tokens, c)) #roundrobin recipe from itertools documentation
if query.match(candidate):
yield candidate


Supported subset of regular expressions language

• Supports [] set of characters ([A-Z], [0-5], etc)
• Supports escaped special characters (\w, \d, \D, etc)

Basically what this does is locate all parts of a regular expression that could match a single character ([A-Z] or [0-5] or [02468] or \w or \d), then for all of the valid replacement characters A-Z0-9_ test to see if the replacement matches the regular expression.

This algorithm is slow for regular expressions with many fields or if fill_in is not restricted to just A-Z0-9_, but at least it guarantees finding every possible string that will match a regular expression in finite time (if the solution set is finite).

Is there a faster approach to solving this problem, or an approach that supports a larger percentage of the standard regular expression language?

• Are you looking to exhaustively test all possible inputs to this regex? That could get quickly out of hand, and some regex's could literally have an infinite number of possible inputs (you'll run out of memory or time before you test them all). How about some representative sample that covers all the things you want to test? It might even be possible to automatically generate such coverage (your intent, I believe).
– Phil Perry
Mar 10, 2014 at 18:08
• In line with comment from @PhilPerry - if your regex uses any "closure" type operations (e.g. + meaning one-or-more or * for zero-or-more), the set of possible matches will not be finite.
– twalberg
Mar 10, 2014 at 18:10
• Using a generator function, itertools.product, and itertools.roundrobin resolves the infinite memory problem, but you're right that this could require infinite time. I have do not need to support closure operators * or +. @PhilPerry I need the full solution set. A sample will not satisfy the problem I am solving.
– IceArdor
Mar 10, 2014 at 18:12
• This is quite a challenge. Even short regexes with no closure operations can produce more strings than you could possibly store. For instance, "\d\d\d\d\d\d\d\d\d\d\d\d" matches a trillion different strings. Mar 10, 2014 at 18:21
• Why do you call query.match(candidate)? Does your algorithm generate candidates that don't match? Mar 11, 2014 at 6:48

A major inefficiency in your solution is that you try every fill_in character as a replacement for any character class in the pattern. Instead, you could use the character class to select matching characters from fill_in and only loop over those.
>>> pattern = 'K0[2468]'