Генерация списка значений, которые регулярное выражение МОЖЕТ соответствовать в Python

Question

Я пытаюсь использовать регулярное выражение в качестве входных данных, и оттуда генерировать все возможные значения, которым регулярное выражение будет соответствовать.

Так, например, если регулярное выражение является «трехбуквенными словами, начинающимися с a и заканчивающимися на c», то код будет генерировать список со значениями [aac, abc, acc, adc, a1c ... .].

Есть ли простой способ сделать это? Я использую Python.

Answer 1

Вот решение грубой силы, которое должно работать. Время работы O (L ^ max_length) (где L - размер алфавита), поэтому используйте его на свой страх и риск.

def all_matching_strings(alphabet, max_length, regex):
"""Find the list of all strings over 'alphabet' of length up to 'max_length' that match 'regex'"""

if max_length == 0: return 

L = len(alphabet)
for N in range(1, max_length+1):
    indices = [0]*N
    for z in xrange(L**N):
        r = ''.join(alphabet[i] for i in indices)
        if regex.match(r):                
           yield(r)

        i = 0
        indices[i] += 1
        while (i<N) and (indices[i]==L):
            indices[i] = 0
            i += 1
            if i<N: indices[i] += 1

return

пример использования:

alphabet = 'abcdef1234567890'
import re
regex = re.compile('f*[1-3]+$')
for r in all_matching_strings(alphabet, 5, regex): 
    print r

, который будет выводить все строки длиной до 5, начиная с последовательности f, затем непустой последовательности 1-3, затем заканчивая:

1
2
3
f1
11
21
31
f2
12
22
32
f3
13
23
33
ff1
[more output omitted...]

Answer 2

Ты не хочешь этого делать. Большинство наборов результатов будут огромными, а некоторые - бесконечными. Вместо этого используйте последовательность тестовых векторов и примените регулярное выражение к каждому по очереди:

vectors = (
  'foo',
  'bar',
  ...
)

for result in (re.match(someregex, entry) for entry in vectors):
  ...

Answer 3

Набор совпадающих строк бесконечен тогда и только тогда, когда в вашем регулярном выражении есть квантификатор (+ или *). Ваш вопрос, похоже, не нацелен на эти паттерны. Я скорее верю, что функция product из itertools может помочь здесь.

Вы можете, например, ввести специальный символ, обозначающий произвольную букву (например, подчеркивание), а затем построить шаблон, подобный этому

patt = 'a_c'

и определите свой алфавит

youralphabet = 'abcde...'

и определите функцию, генерирующую все возможные экземпляры, подобные этой

def genInstances(patt):
    elems = [c if c != '_' else youralphabet for c in patt]
    return itertools.product(*elems)

Затем вы можете расширить этот подход, чтобы он соответствовал реальному регулярному выражению, проанализировав ваш шаблон для \d или [a-zA-Z] или чего угодно.

Answer 4

Некоторые регулярные выражения соответствуют конечному количеству входных строк, но многие (большинство?) Соответствуют бесконечному количеству входных строк. Это все равно что спрашивать «учитывая грамматику языка Python, генерировать все возможные программы Python». Вы, вероятно, могли бы написать программу, чтобы перечислить их все в последовательности, если бы вы попытались (хотя для запуска потребовалось бы бесконечное время), но вы уверены, что хотите? Почему вы хотите?

Я почти уверен, что движок регулярных выражений в стандартной библиотеке не предоставляет способ генерирования нужного вам результата. Вам нужно будет получить доступ к внутренним структурам данных более низкого уровня или самостоятельно внедрить какой-нибудь механизм DFA.