正则表达式的最大匹配长度

Question

怎样才能最简单地找出正则表达式的最大匹配长度呢？

具体来说，我在用Python的re模块。

比如，对于foo((bar){2,3}|potato)这个表达式，最大匹配长度是12。

显然，使用像*和+这样的操作符的正则表达式在理论上是没有上限的；在这种情况下，返回一个错误信息或者其他的提示也是可以的。对于使用(?...)扩展的正则表达式，返回错误也是可以接受的。

我也可以接受得到一个大致的上限，只要这个上限总是大于实际的最大长度，但不要差得太多。

Answer 1

使用 pyparsing 的 invRegex 模块：

import invRegex
data='foo(bar{2,3}|potato)'    
print(list(invRegex.invert(data)))
# ['foobarr', 'foobarrr', 'foopotato']    
print(max(map(len,invRegex.invert(data))))
# 9

另一种选择是使用 ipermute，这个功能来自于 这个模块。

import inverse_regex
data='foo(bar{2,3}|potato)'
print(list(inverse_regex.ipermute(data)))
# ['foobarr', 'foobarrr', 'foopotato']
print(max(map(len,inverse_regex.ipermute(data))))
# 9

Answer 2

我想我解决了这个问题。感谢unutbu让我注意到sre_parse！

import sre_parse

def get_regex_max_match_len(regex):
    minlen, maxlen = sre_parse.parse(regex).getwidth()
    if maxlen >= sre_parse.MAXREPEAT: raise ValueError('unbounded regex')
    return maxlen

结果是：

>>> get_regex_max_match_len('foo((bar){2,3}|potato)')
12
>>> get_regex_max_match_len('.*')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in get_regex_max_match_len
ValueError: unbounded regex