在Python中生成正则表达式可能匹配的值列表

Question

我想用正则表达式作为输入，然后从中生成所有可能匹配这个正则表达式的值。

举个例子，如果这个正则表达式是“以a开头，c结尾的三个字母的单词”，那么代码就会生成一个包含 [aac, abc, acc, adc, a1c....] 这些值的列表。

有没有简单的方法可以做到这一点？我在用Python。

Answer 1

如果你的正则表达式中有量词（比如 + 或 *），那么匹配的字符串组合就是无限的。看起来你的问题并不是针对这些模式。我觉得可以使用 itertools 里的 product 函数来帮助你。

比如，你可以引入一个特殊字符来表示任意字母（比如下划线），然后构建一个这样的模式：

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 2

你不想这样做。大部分结果集会非常庞大，有些甚至是无限的。相反，应该使用一系列测试向量，然后逐个应用正则表达式来检查它们：

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

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

Answer 3

这里有一个简单粗暴的解决方案，应该可以用。它的运行时间是 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...]