python - 生成一个正则表达式可以在 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...]