Python中文网 - 问答频道, 解决您学习工作中的Python难题和Bug
Python常见问题
有人能解释一下为什么Java的正则表达式引擎在这个正则表达式上进入灾难性的回溯模式？据我所知，每一次交替都是相互排斥的。在
^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
\"(?:[^\"]+|\"\")+\"|
'(?:[^']+|'')+')
文本：'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])
在一些替换中添加所有格匹配可以解决这个问题，但我不知道为什么-Java的regex lib必须非常有缺陷才能在互斥分支上回溯。在
^{pr2}$Tags： 引擎文本lib分支模式dejavacar
热门问题
- 我想从用户inpu创建一个类的实例
- 我想从用户导入值，为此
- 我想从用户那里得到一个整数输入，然后让for循环遍历该数字，然后调用一个函数多次
- 我想从用户那里收到一个列表，并在其中执行一些步骤，然后在步骤完成后将其打印回来，但它没有按照我想要的方式工作
- 我想从用户那里获取输入，并将值传递给（average=dict[x]/6），然后在那里获取resu
- 我想从第一个列表中展示第一个词，然后从第二个列表中展示十个词，以此类推- Python
- 我想从第一个空lin开始解析文本文件
- 我想从简历、简历中提取特定部分
- 我想从给定字典（python）的字符串中删除\u00a9、\u201d和类似的字符。
- 我想从给定的网站Lin下载许多文件扩展名相同的Wget或Python文件
- 我想从网上搜集一些关于抵押贷款的数据
- 我想从网站上删除电子邮件地址
- 我想从网站上读取数据该网站包含可下载的文件，然后我想用python脚本把它发送给oracle如何？
- 我想从网站中提取数据，然后将其显示在我的网页上
- 我想从网页上提取统计数据。
- 我想从网页上解析首都城市，并在用户输入国家时在终端上打印它们
- 我想从色彩图中删除前n个颜色，而不丢失原始颜色数
- 我想从课堂上打印字典里的键
- 我想从费用表中获取学生上次支付的费用，其中学生id=id
- 我想从较低的顺序对多重列表进行排序，但我无法在一行中生成结果
热门文章
- Python覆盖写入文件
- 怎样创建一个 Python 列表？
- Python3 List append()方法使用
- 派森语言
- Python List pop()方法
- Python Django Web典型模块开发实战
- Python input() 函数
- Python3 列表(list) clear()方法
- Python游戏编程入门
- 如何创建一个空的set?
- python如何定义(创建)一个字符串
- Python标准库 [The Python Standard Library by Ex
- Python网络数据爬取及分析从入门到精通（分析篇）
- Python3 for 循环语句
- Python List insert() 方法
- Python 字典(Dictionary) update()方法
- Python编程无师自通 专业程序员的养成
- Python3 List count()方法
- Python 网络爬虫实战 [Web Crawler With Python]
- Python Cookbook（第2版）中文版
编辑：最后添加了Java版本——尽管它本身就很笨拙、不可读、不可维护。在
“不再有丑陋的图案了！在
您需要做的第一件事情是以一种能够经受住任何人类可读性和可维护性的希望的方式编写正则表达式。 你需要做的第二件事是分析它，看看它到底在做什么。在
这意味着您至少需要在
Pattern.COMMENTS模式（或前缀"(?x)"）下编译它，然后添加空格以提供一些可视空间。就我所能理解的，你实际想要匹配的模式是这样的：如你所见，我在可能的地方引入了垂直和水平空白，以便引导眼睛和大脑作为一种认知分块。我也删除了你所有多余的反斜杠。这些都是要么是彻头彻尾的错误，要么就是让读者迷惑的模糊剂。在
注意，在应用垂直空白时，我将从一行到下一行的相同部分放在同一列中，这样您就可以立即看到哪些部分是相同的，哪些部分是不同的。在
这样做了，我终于可以看到你在这里是一个锚定在开始的比赛，然后是三个备选方案的选择。因此，我将这三种选择标记为描述性注释，这样就不必猜测了。在
我还注意到，您的第一个备选方案有两个微妙的不同（否定）方括号字符类。第二种方法缺少第一种方法中的单引号排除。这是故意的吗？即使是这样，我发现这对于我的口味来说太多的重复；其中的一些或全部应该在一个变量中，这样就不会冒更新一致性问题的风险。在
分析
你必须做的两件事中的第二件也是更重要的一件事就是对这件事进行分析。您需要确切地看到该模式被编译到哪个regex程序中，并且您需要跟踪它在数据上运行时的执行情况。在
Java的
Pattern类目前还不能做到这一点，尽管我已经与OraSun的当前代码保管人详细地谈过了，他都很想将这个功能添加到Java中，并认为他知道如何做到这一点。他甚至给我寄了一个原型来做第一部分：编译。所以我希望有一天它能上市。在同时，让我们转而使用一种工具，其中regex是编程语言本身的一个组成部分，而不是一个笨拙的事后诸葛亮。尽管有几种语言符合这一标准，但模式匹配的艺术还没有达到Perl中的复杂程度。在
下面是一个等效程序。在
^{pr2}$如果我们运行这个程序，就会得到匹配失败的预期答案。问题是为什么和怎么做。在
我们现在要看两件事：我们想看看模式编译成什么样的正则表达式程序，然后我们要跟踪该正则表达式程序的执行情况。在
这两个都是用
pragma，也可以通过
-Mre=debug在命令行上指定。这就是我们在这里要做的，以避免对源代码的黑客攻击。在正则表达式编译
re调试杂注通常会显示模式的编译及其执行。为了分离这些，我们可以使用Perl的“compile only”开关-c，它不尝试执行它编译的程序。这样我们所看到的就是编译后的模式。是否会产生以下36行输出：如您所见，已编译的regex程序是用它自己的某种“regex汇编语言”编写的。（它看起来也很像Java原型所有的细节都不是必须的，但是我要指出的是，节点2的指令是一个分支，如果失败，它将继续执行另一个分支分支26。第二个分支是regex程序唯一的另一部分，它由一个TRIE-EXACT节点组成，因为它知道备选方案有不同的起始文本字符串。发生了什么事 关于这两个分支，我们稍后再讨论。在
正则表达式执行
现在是时候看看它运行时会发生什么。您使用的文本字符串会导致相当多的回溯，这意味着在最终失败之前，您将有大量的输出要处理。产量是多少？好吧，这么多：
我假设10000步就是你所说的“灾难性回溯模式”。让我们看看我们不能把它简化成更容易理解的东西。输入字符串的长度为61个字符。为了更好地了解发生了什么，我们可以将其缩减为
'pão，它只有4个字符。（好吧，在NFC中，也就是说，NFD中有5个代码点，但在这里没有任何变化）。结果是167行输出：事实上，以下是当您的字符串有这么多个字符时所得到的regex（compilation plus）执行评测行：
让我们看看当字符串是四个字符
'pão时的调试输出。这次我省略了编译部分，只显示执行部分：在最后一个引用后，你可以看到最后一个引用的分支。就是这个：
节点55是trie分支：
下面是执行跟踪，显示灾难性退避发生的位置：
节点58吞噬了字符串
pão中所有剩余的3个字符。这导致单引号的终止精确匹配失败。因此，它尝试您的替代方法，即一对单引号，但也失败了。在在这一点上，我不得不质疑你的模式。不应该
真的很简单吗？在
所以现在的情况是，有很多方法可以让it回溯到逻辑上永远不会发生的事情。你有一个嵌套的量词，这导致了各种无望和无意识的忙碌。在
如果我们将模式简化为：
现在，不管输入字符串的大小，它都提供相同数量的跟踪输出行：只有40行，这包括编译。在完整字符串上见证编译和执行：
我知道你在想占有匹配可能是这里的答案，但我认为真正的问题是原始模式中错误的逻辑。你看现在的情况有多正常？在
如果我们用你的所有格在旧模式上运行它，即使我认为这没有意义，我们仍然可以得到恒定的运行时间，但它需要更多的步骤。用这个图案
编译和执行配置文件如下：
我还是更喜欢我的解决方案。它比较短。在
编辑
似乎Java版本比Perl版本的相同模式要多出100倍的步骤，我不知道为什么——除了Perl regex编译器在优化方面比Java regex编译器聪明100倍，Java regex编译器从来没有做过任何事情，而且应该这样做。在
这是等效的Java程序。我已经拆下了主锚，这样我们就可以正常循环了。在
运行时，会产生以下结果：
如您所见，模式匹配在爪哇有很多话要说，绝对没有一个能通过便溺警察。这简直是皇室之痛
对于字符串：
看来，正则表达式的这一部分将是问题所在：
^{pr2}$匹配第一个
'，然后无法匹配结束的'，从而回溯嵌套量词的所有组合。在如果允许regex回溯，它将回溯（失败时）。使用原子群和/或所有格量词来防止这种情况发生。在
顺便说一句，你不需要那个正则表达式中的大部分转义。在字符类（
[]）中，唯一需要转义的是字符^-]。但通常你可以定位它们，这样它们也就不需要逃跑了。当然，\和任何你所使用的字符串仍然需要（双）转义。在我不得不承认这也让我很吃惊，但我在RegexBuddy中得到了相同的结果：它在经过一百万步后就放弃了尝试。我知道关于灾难性回溯的警告往往集中在嵌套量词上，但根据我的经验，交替使用至少同样危险。事实上，如果我将regex的最后一部分改为：
……对此：
^{pr2}$…它只需十一步就失败了。这是Friedl的“展开循环”技术的一个示例，他将其分解如下：
只要：
special和{special始终至少匹配一个字符，并且special是原子的（必须只有一种方法才能匹配）。在正则表达式将失败以匹配最小回溯，而成功根本没有回溯。另一方面，替代版本几乎可以保证回溯，在不可能匹配的情况下，随着目标字符串长度的增加，它会迅速失控。如果它在某些口味中没有过度回溯，那是因为它们有专门针对这个问题的优化，目前为止很少有口味能做到。在
相关问题 更多 >
编程相关推荐