代码之家 › 专栏 › 技术社区 › Brent.Longborough

python re中的贪婪与非贪婪匹配

non-greedy greedy regex python

1

Brent.Longborough · 技术社区 · 16 年前

请帮助我发现这是否是Python(2.6.5)中的一个bug,在我编写regex的能力中,或者在我对模式匹配的理解中。

(我接受一个可能的答案是“升级你的python”。)

我正在尝试解析一个Yubikey令牌,允许可选的附加项。

当我使用此regex来匹配一个没有任何可选附加项的令牌(即,仅包含与两个捕获组匹配的内容)时,匹配失败:

r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'

但是,如果我让第一组人不贪婪:

r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'

它成功了。

所以,好吧,这是可行的,但我想这两个正则表达式最终结果的唯一区别就是性能。

Expresso和Regex教练都喜欢这两种模式。

我错过了什么?

下面是我测试的两个字符串。

无可选附加项(可能失败的附加项):

"vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui"

使用可选的附加项(到目前为止还没有失败;实际选项卡在此处显示为“uu”):

"_!_8R5Gkruvfgheufhcnhllchgrfiutujfh_"
"_!1U4Knivdgvkfthrd_brvejhudrdnbunellrjjkkccfnggbdng_"

我试着用Alex Martelli的建议复制它,它在原始的python环境中不会失败,所以我将重新访问我的代码(实际上我正在对yubikey python进行黑客攻击);我将在一天左右后报告。

我向大家道歉。我无法再现这个问题。当它发生时,我正在通过 getpass 我怀疑是一个意外的外国键盘击中了我。

我要结束这个问题。如果反对者希望取消他们的投票,那是公平的。

非常抱歉。

2 回复 | 直到 16 年前

1

3

Alex Martelli 16 年前

我建议使用 yubikey-python 对于python与yubikey的接口——但是,这是一个侧面(并且严格实用主义)问题;-)。

理论上,在贪婪和非贪婪之间的选择不会导致在一种情况下重新匹配而在另一种情况下失败——它只会影响匹配的内容(正如您所提到的性能),而不会影响匹配是否成功,因为应为此目的回溯res。

问题是,我不能复制这个问题——我手头没有一辆雅致的自行车,测试也没有 this file 显示两个资源的匹配/不匹配行为之间没有差异。

请你张贴几个失败的例子(其中一个匹配,另一个不匹配),理想情况下编辑你的问题,这样我可以复制问题,并尽量减少到最低限度?听起来可能有一个重新bug,但是如果没有可复制的案例,我就无法检查它是否被修复,何时已经报告,或者什么。谢谢!

编辑 OP现在发布了一个失败的例子,但我仍然无法复制:

$ py26
Python 2.6.5 (r265:79359, Mar 24 2010, 01:32:55) 
[GCC 4.0.1 (Apple Inc. build 5493)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> r1 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$')
>>> r2 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'
... )
>>> nox="vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui"
>>> r1.match(nox)
<_sre.SRE_Match object at 0xcc458>
>>> r2.match(nox)
<_sre.SRE_Match object at 0xcc920>
>>>

也就是说,匹配在这两种情况下都是成功的,正如它应该的那样——这与OP使用的2.6.5 python版本完全相同。请看,在你的平台上显示这个简单的命令序列的结果,并告诉我们平台是什么,因为它看起来像一个奇怪的依赖于平台的错误…谢谢!

2

0

Alan Moore Chris Ballance 16 年前

您是对的:简单地从贪婪量词切换到非贪婪量词不应该导致regex停止工作。它可以改变regex匹配(或不匹配)的速度,以及 许多的 它匹配,哪些部分在哪些组中被捕获,就这些。

(以下“解决方案”不适用,但问题仍然不表示正在执行不区分大小写的匹配,因此我将保留它。)

您的问题是,具有可选附加项的字符串中也有大写字母,并且regex只允许使用小写字母。粘甲 (?i) 在前面或是雷吉士,它工作得很好。