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

我试图使用正则表达式作为输入，并从那里生成正则表达式匹配的所有可能的值。例如，如果正则表达式是“以a开头并且以c结尾的三个字母的单词”，则该代码将生成具有值[aac，abc，acc，adc，a1c ..的列表。 ..]。在Python中生成正则表达式COULD匹配的值列表

有没有简单的方法来做到这一点？我正在使用python。

来源

2010-03-17 mlissner

其中一些结果集将会很大。 – 2010-03-17 20:44:34

其中一些结果集将会是无限的。 – 2010-03-17 20:49:35

是的，我打算让人们把他们想要的任何正则表达式，然后测试它有多少点击。如果它超过给定的数字，则抛出错误。 – mlissner 2010-03-18 18:28:47

这是一个应该可以工作的强力解决方案。它的运行时间为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...]

来源

2010-03-18 08:01:25

您可以通过从字母串中过滤任何不在正则表达式中出现的字符来加速它，因为它们永远不会匹配。您也可以检查正则表达式是否必须匹配不在字母表中的字符，如果是，则返回空列表，因为它永远不会成功。但这更复杂，因为您只能考虑必须始终匹配的字符，例如如果你的例子中的正则表达式是'x + [1-3] + $'，但不是'x * [1-3] + $'。 – 2010-03-18 08:36:50

这看起来像一个合理的解决方案。我宁愿不必定义我的字母表，但我同意这似乎是必要的。 – mlissner 2010-03-18 18:32:15

你不想这样做。大多数结果集将是巨大的，有些将是无限的。而是使用测试向量的序列，进而应用正则表达式对每个：

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

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

来源

2010-03-17 20:49:25

一些正则表达式匹配的输入字符串的数量有限，但许多（大多数？）匹配输入字符串的无限数量。这有点像问'给定python语法语法，生成所有可能的python程序'。如果你尝试过了，你可能会编写一个程序按顺序列出它们（尽管这需要无限的时间来运行），但是你确定你想要吗？你为什么想要？

我很确定标准库中的正则表达式引擎没有公开生成你想要的输出的方法。您必须获得较低级别的内部数据结构访问权限，或者自行实施一些DFA引擎。

来源

2010-03-17 20:53:50

当且仅当您的正则表达式中存在一个量词（+或*）时，匹配字符串的集合才是无限的。你的问题似乎并不针对这些模式。我宁愿相信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]或其他什么来扩展这种方法来匹配真正的正则表达式。

来源

2010-03-18 08:42:41

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

回答

相关问题