这个正则表达式是如何工作的？

Question

从这篇文章中， /^1?$|^(11+?)\1+$/检查一个数（在一元下的值）是否为质数。

使用此方法，perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;'返回一个质数列表。

我对Perl不够熟悉，但我理解的是公式将对非质数产生真正的结果。因此，如果我们列印所有未与此表达式产生真正结果的数字，则会得到一个质数列表。这就是perl查询试图做的事情。

关于正则表达式部分， ^1?$部分用于将1计算为非质数 ^(11+?)\1+$用于匹配从4开始的非素数。

---

我不明白的是为什么正则表达式中需要?。

据我所知，/^1$|^(11+)\1+$/应该足够了，实际上 perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++ $_;'给我相同的质数集。 我的正则表达式理解有什么缺陷？为什么需要?？ ?不应该匹配前面的表达式的零或一个出现吗？

- Lazer

Answer 1

第一个?是为了匹配空字符串（即0）作为非素数。如果您不在意正则表达式是否匹配0，则这不是必要的。

第二个?只是为了提高效率。+通常是“贪婪”的，这意味着它匹配尽可能多的字符，然后在剩余的正则表达式无法匹配时回溯。+?使其成为非贪婪的，因此它只匹配1个字符，然后如果剩余的正则表达式无法匹配，则尝试匹配更多字符。（有关贪婪vs.非贪婪匹配的更多信息，请参见perlre的量词部分。）

在这个特定的正则表达式中，(11+?)表示它测试被2('11')、3('111')、4等整除。如果使用(11+)，它将测试N（该数字本身）、N-1、N-2等整除。由于约数必须不大于N/2，没有?它将浪费时间来测试许多不可能工作的“潜在”约数。它仍然匹配非素数，只是速度更慢。（此外，$1将是最大的约数而不是最小的。）

- cjm

---

@cjm：这是使表达式非贪婪的标准方法吗？除了 +? 和 *?，它还可以在哪些地方使用？我认为 ? 表示匹配零次或一次。 - Lazer

@Lazer：在量词（如“+”或“*”）后面的问号与在标记后面的问号完全不同。 - Borealid

在正则表达式中，一个跟在另一个量词后面的 ? 会使得该量词变成非贪婪模式。请参考 http://perldoc.perl.org/perlre.html#Quantifiers。 - cjm

@cjm @Borealid：“在另一个量词后面的？会使该量词变为非贪婪模式。”这对所有POSIX正则表达式都适用吗？ - Lazer

@Lazer：不是所有的编程语言都支持由Perl 5首次引入的扩展语法（并被许多其他程序复制） 。 - cjm

@Laser: {n,}?或者{n,m}?也可以（更倾向于较低的重复次数而不是较高的）。 - ysth

Answer 2

第一个问号会使得空字符串（一元零）不是质数。0被定义为非质数。

第二个问号则不同，它防止正则表达式进行贪婪匹配。这将大大提高匹配性能，因为该部分的第一部分((11+))在回溯之前就不会消耗几乎整个字符串。如果省略问号，则实际上测试的是奇数n是否能够被n-1整除，以此类推；如果包含问号，则首先测试可被2整除等更大的数。显然，数字更容易被较小的因子整除，所以匹配速度会更快。

- Borealid

---

好的，这解释了为什么在 ^1?$ 中需要 ?。但是为什么在表达式的后半部分也需要它呢？ - Lazer

@Lazer：不，第二个更长的段落是关于第二个“？”的。你在perlre页面中忽略的是，在+或*后面的“？”表示非贪婪匹配（一旦找到匹配项就停止扫描）。 - reinierpost

@reinierpost，那个评论写完之后才添加了第二段。 - cjm

@cjm：是的，不过你在写回答之前 :-P。无论如何，感谢您的评论。 - Borealid

好的。你在我开始写答案和完成它之间更新了你的答案。老实说，我认为我的答案略微更好，但是我有偏见。 :-) - cjm