Reverse regular expression in Python

Question

this is a strange question I know... I have a regular expression like:

rex = r"at (?P<hour>[0-2][0-9]) send email to (?P<name>\w*):? (?P<message>.+)"

so if I match that like this:

match = re.match(rex, "at 10 send email to bob: hi bob!")

match.groupdict() gives me this dict:

{"hour": "10", "name": "bob", "message": "hi bob!"}

My question is: given the dict above and rex, can I make a function that returns the original text? I know that many texts can match to the same dict (in this case the ':' after the name is optional) but I want one of the infinite texts that will match to the dict in input.

Answer 1

Using inverse_regex:

"""
http://www.mail-archive.com/python-list@python.org/msg125198.html
"""
import itertools as IT
import sre_constants as sc
import sre_parse
import string

# Generate strings that match a given regex

category_chars = {
    sc.CATEGORY_DIGIT : string.digits,
    sc.CATEGORY_SPACE : string.whitespace,
    sc.CATEGORY_WORD  : string.digits + string.letters + '_'
    }

def unique_extend(res_list, list):
    for item in list:
        if item not in res_list:
            res_list.append(item)

def handle_any(val):
    """
    This is different from normal regexp matching. It only matches
    printable ASCII characters.
    """
    return string.printable

def handle_branch((tok, val)):
    all_opts = []
    for toks in val:
        opts = permute_toks(toks)
        unique_extend(all_opts, opts)
    return all_opts

def handle_category(val):
    return list(category_chars[val])

def handle_in(val):
    out = []
    for tok, val in val:
        out += handle_tok(tok, val)
    return out

def handle_literal(val):
    return [chr(val)]

def handle_max_repeat((min, max, val)):
    """
    Handle a repeat token such as {x,y} or ?.
    """
    subtok, subval = val[0]

    if max > 5000:
        # max is the number of cartesian join operations needed to be
        # carried out. More than 5000 consumes way to much memory.
        # raise ValueError("To many repetitions requested (%d)" % max)
        max = 5000

    optlist = handle_tok(subtok, subval)

    iterlist = []
    for x in range(min, max + 1):
        joined = IT.product(*[optlist]*x) 
        iterlist.append(joined)

    return (''.join(it) for it in IT.chain(*iterlist))

def handle_range(val):
    lo, hi = val
    return (chr(x) for x in range(lo, hi + 1))

def handle_subpattern(val):
    return list(permute_toks(val[1]))

def handle_tok(tok, val):
    """
    Returns a list of strings of possible permutations for this regexp
    token.
    """
    handlers = {
        sc.ANY        : handle_any,
        sc.BRANCH     : handle_branch,
        sc.CATEGORY   : handle_category,
        sc.LITERAL    : handle_literal,
        sc.IN         : handle_in,
        sc.MAX_REPEAT : handle_max_repeat,
        sc.RANGE      : handle_range,
        sc.SUBPATTERN : handle_subpattern}
    try:
        return handlers[tok](val)
    except KeyError, e:
        fmt = "Unsupported regular expression construct: %s"
        raise ValueError(fmt % tok)

def permute_toks(toks):
    """
    Returns a generator of strings of possible permutations for this
    regexp token list.
    """
    lists = [handle_tok(tok, val) for tok, val in toks]
    return (''.join(it) for it in IT.product(*lists))



########## PUBLIC API ####################

def ipermute(p):
    return permute_toks(sre_parse.parse(p))

---

You could apply the substitutions given rex and data, and then use inverse_regex.ipermute to generate strings that match the original regex:

import re
import itertools as IT
import inverse_regex as ire

rex = r"(?:at (?P<hour>[0-2][0-9])|today) send email to (?P<name>\w*):? (?P<message>.+)"
match = re.match(rex, "at 10 send email to bob: hi bob!")
data = match.groupdict()
del match

new_regex = re.sub(r'[(][?]P<([^>]+)>[^)]*[)]', lambda m: data.get(m.group(1)), rex)
for s in IT.islice(ire.ipermute(new_regex), 10):
    print(s)

yields

today send email to bob hi bob!
today send email to bob: hi bob!
at 10 send email to bob hi bob!
at 10 send email to bob: hi bob!

---

Note: I modified the original inverse_regex to not raise a ValueError when the regex contains *s. Instead, the * is changed to be effectively like {,5000} so you'll at least get some permutations.

Answer 2

This is one of the texts that will match the regex:

'at {hour} send email to {name}: {message}'.format(**match.groupdict())'