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' 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],  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
set of characters (
- Supports escaped special characters (
Basically what this does is locate all parts of a regular expression that could match a single character (
\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?