**量词到底做什么

  • 本文关键字:量词 regex quantifiers
  • 更新时间 :
  • 英文 :


懒惰和贪婪的概念很容易理解,但我在正则表达式(在Java中)[A]|[^B]*+(?!C)(A、B、C是任意值)中只见过/使用过*+一次,因为当懒惰修饰符导致StackOverflow错误时,它就起作用了。

由于大多数搜索引擎无法搜索符号,我找不到任何关于这方面的文档。那么,**究竟是做什么的,它是如何做到的呢?

贪婪的量词匹配它所能匹配的一切,然后模式回溯,直到匹配成功。

懒惰的量词向前跟踪,直到匹配成功。

所有格量词匹配它所能匹配的一切,并且从不回溯

+表示所有格量词。If可以用作例如++*+

这种防止回溯的能力意味着它可以阻止灾难性的回溯。

正如其他答案所指出的,*+是一个"所有格量词"。它尽可能多次地匹配前一个元素,就像贪婪的量词一样,但从不回溯。

为什么这有用作为性能优化。此外,当正则表达式不匹配时,作为性能优化。这是了解正则表达式的一个重要点:当不匹配时,它们的最坏性能总是发生。

根据所使用的正则表达式引擎以及正则表达式本身的详细信息,最坏情况下的性能有时会非常糟糕。举一个简单的例子,用这个正则表达式:a*a*a*b,与这个字符串:aaaaac匹配。

面对这种情况,标准的"NFA"类型正则表达式引擎将执行以下操作:

  1. 尝试匹配第一个a 5次,第二个a 0次,第三个a 0次
  2. 尝试将bc进行匹配--失败
  3. "回溯"并匹配第一个a 4次、第二个1次和第三个0次
  4. 再次尝试匹配b,但失败
  5. 再次回溯,尝试第一次a 4次,第二次0次,第三次1次
  6. 回溯,尝试第一个a 3次,第二个2次,第三个0次

(我想你可以自己填写接下来的几百步。)

如果正则表达式是a*+a*a*b,那么这种情况就永远不会发生。它更像是:

  1. 尝试匹配第一个a 5次、第二个零次和第三个零次
  2. 尝试匹配b——它失败了
  3. 由于第一个a是"所有格",一旦匹配了5次,它就永远无法尝试匹配更少的次数。由于字符串中没有剩余的as可供其他a*s匹配,因此它们只能匹配零次。没有什么可尝试的了,所以整个比赛失败了
  4. 没有步骤4。你完了。当你的朋友们在等待他们的regexp完成执行时,你可以放松一下,打开你选择的冷饮

X*+表示X,零次或多次(拥有)

所有格量词总是吃掉整个输入字符串,尝试一次(并且只尝试一次)匹配。与贪婪的量词不同,所有格量词从不退缩,即使这样做会使整体匹配成功。

相关内容

  • 没有找到相关文章

最新更新