Как в питоне сгенерировать все возможные строки, соответствующие регулярному выражению?

#python #регулярные_выражения

Есть некое регулярное выражение, например, "[a-z][0-9]{3}|[a-z]{3}". Как получить
список всех возможных строк, соответствующих этому выражению? Примерно такой:
['a781', 'b000', 'c476', 'u132', 'd997', 'exe', 'use' и т.д.]
    

Ответы

Ответ 1

Кроме самых простых случаев (без *+), кол-во строк, соотвествующих заданному регулярному
выражению, может быть бесконечно.

Обратить регулярное выражение достаточно легко, например, re модуль позволяет получить
регулярное выражение в виде дерева, обходя которое можно cгенерировать подходящую строку:

import re
from pprint import pprint

regex = "[a-z][0-9]{3}|[a-z]{3}"
pprint(re.sre_parse.parse(regex).data)


Результат:

[('branch',
  (None,
   [[('in', [('range', (97, 122))]), ('max_repeat', (3, 3, [('in', [('range', (48,
57))])]))],
    [('max_repeat', (3, 3, [('in', [('range', (97, 122))])]))]]))]


bjmc написал rstr.xeger функцию, которая возвращает (одну, любую) строку, удовлетворяющую
заданному regex:

import rstr # $ pip install rstr

regex = "[a-z][0-9]{3}|[a-z]{3}"
print(rstr.xeger(regex)) # print a single string that matches the regex
# -> ycu


Paul McGuire (pyparsing) упомянул 
сайт Инвертер регулярных выражений, основанный на invRegex.py примере:

from itertools import islice
from invRegex import invert # http://pyparsing.wikispaces.com/file/view/invRegex.py

regex = "[a-z][0-9]{3}|[a-z]{3}"
print("\n".join(islice(invert(regex), 10000))) # print < 10000 matching strings


Результат:

a000
a001
a002
a003
a004
a005
a006
a007
a008
a009
a010
a011
a012
a013
a014
a015
a016
a017
a018
a019
a020
a021
a022
a023
a024
...


Примеры взяты из ответов к Reversing a regular expression in python.


Ответ 2

Для начала нужно проанализировать выражение с целью выявления, можно ли вообще перебрать
все варианты для него. Потом уже составить варианты перебора. Потом посмотреть на замечательный
модуль itertools и, собственно, перебрать все нужные варианты.
Для указанного регулярного выражения это будет выглядеть примерно вот так:
from string import digits, ascii_lowercase
from itertools import product

# [a-z][0-9]{3}
l1 = list( product(ascii_lowercase, digits, digits, digits) )

# [a-z]{3}
l2 = list( product(ascii_lowercase, ascii_lowercase, ascii_lowercase ) )

# concatenate
l = l1 + l2

# and join inner lists
res = [''.join(i) for i in l]