ERE - 在包含内部组和反向引用的组中添加量词

Question

我试图找到具有连续重复字母出现两次或三次的单词。但是我无法找到一种使用ERE量词和捕获组的方法。

$ grep --version | head -n1
grep (GNU grep) 2.25

$ # consecutive repeated letters occurring twice
$ grep -m5 -xiE '[a-z]*([a-z])\1[a-z]*[a-z]*([a-z])\2[a-z]*' /usr/share/dict/words
Abbott
Annabelle
Annette
Appaloosa
Appleseed

$ # no output for this, why?
$ grep -m5 -xiE '([a-z]*([a-z])\2[a-z]*){2}' /usr/share/dict/words

虽然这个问题可以使用-P解决

$ grep -m5 -xiP '([a-z]*([a-z])\2[a-z]*){2}' /usr/share/dict/words
Abbott
Annabelle
Annette
Appaloosa
Appleseed

$ grep -m5 -xiP '([a-z]*([a-z])\2[a-z]*){3}' /usr/share/dict/words
Chattahoochee
McConnell
Mississippi
Mississippian
Mississippians

感谢Casimir et Hippolyte提供更简单的输入和正则表达式来测试这个行为。

$ echo 'aazbb' | grep -E '(([a-z])\2[a-z]*){2}' || echo 'No match'
aazbb
$ echo 'aazbbycc' | grep -E '(([a-z])\2[a-z]*){2}([a-z])\3[a-z]*' || echo 'No match'
aazbbycc
$ echo 'aazbbycc' | grep -P '(([a-z])\2[a-z]*){3}' || echo 'No match'
aazbbycc

$ # failing case
$ echo 'aazbbycc' | grep -E '(([a-z])\2[a-z]*){3}' || echo 'No match'
No match

使用 sed 同样看到了相同的行为

$ sed --version | head -n1
sed (GNU sed) 4.2.2

$ echo 'aazbb' | sed -E '/(([a-z])\2[a-z]*){2}/! s/.*/No match/'
aazbb    
$ echo 'aazbbycc' | sed -E '/(([a-z])\2[a-z]*){2}([a-z])\3[a-z]*/! s/.*/No match/'
aazbbycc

$ # failing case
$ echo 'aazbbycc' | sed -E '/(([a-z])\2[a-z]*){3}/! s/.*/No match/'
No match

相关搜索链接，我查看了其中一些，但没有找到与此问题相似的内容

• https://savannah.gnu.org/bugs/?group=grep
• http://lists.gnu.org/archive/html/bug-sed/

如果这个问题在更新版本的 grep 或者 sed 中已经解决，请让我知道。同时，如果这个问题出现在非GNU实现中，请告诉我。

- Sundeep

---

请注意：命令 echo 'aazbb' | grep -m5 -xiE '(([a-z])\2[a-z]*){2} 可以正常工作，但命令 echo 'aazbbycc' | grep -m5 -xiE '(([a-z])\2[a-z]*){3} 则不能。我怀疑 grep 会在模式复杂度太高时悄悄地终止匹配。 - Casimir et Hippolyte

@CasimiretHippolyte 看起来是这样的，感谢您的建议。我今天会尝试更多地搜索这些方面 :) - Sundeep

关于您在Ed Morton答案中的评论，BRE和ERE模式下的grep工作方式与-P完全不同，它不使用回溯机制（简而言之，所有可能的路径都被存储，最长的路径获胜）。 - Casimir et Hippolyte

提醒一下，gnu 3文档指出反向引用是有问题的，并且由于堆栈溢出可能会悄悄死掉。还可能存在递归深度限制为2。 - user557597

@Sundeep - 是的，我认为就是这样。但是，关于人为限制。很多时候，作者会将该限制设置为默认值，而不是等待指数时间来找出答案。你的第二个组构造很简单，但他们通常不会区分，可能会很复杂。我认为问题在于嵌套组构造中的反向引用。您可以配置全局grep环境参数来更改它们，即堆栈大小，递归限制等。但是我不确定。 - user557597

Answer 1

我认为 -E 不支持量词符号，这就是为什么它只能与 -P 一起使用的原因。

---

匹配两个或多个连续重复字母组：

grep -P '(?:([a-z])\1*([a-z])\2){1}' /usr/share/dict/words

匹配3个或更多连续重复字母组：

grep -P '(?:([a-z])\1*([a-z])\2){2}' /usr/share/dict/words

选项:

-P, --perl-regexp         PATTERN is a Perl regular expression

- Pedro Lobito

---

-E switches to ERE (extended regular expressions) and the quantifiers available are: ?, *, +, {n}, {m,n} - Casimir et Hippolyte

ERE允许量词... echo 'ac abc abbc abbbc' | grep -Eo 'ab{1,2}c'，也允许使用分组... grep -xE '([a-d][r-z]){3}' /usr/share/dict/words。 - Sundeep

我不太确定，所以我用了“我想”这个词，我会更新我的回答。谢谢。 - Pedro Lobito

@PedroLobito 感谢您的建议。我对为什么 ERE 版本无法工作很感兴趣，问题已经编辑以添加更多示例和信息。 - Sundeep

Answer 2

$ # no output for this, why?
$ grep -m5 -xiE '([a-z]*([a-z])\2[a-z]*){2}' /usr/share/dict/words

因为您正在搜索具有（至少）双字母的双组（两次相同）。类似于abbcabbc [(...) = "abbc" 2次]，而不是具有每个双字母的2个（可能相似的）组，例如abbcdeef。

使用2个后向引用：

$ grep -iE '[a-z]*([a-z])\1{1,}[a-z]*([a-z])\2{1,}[a-z]*`

- NeronLeVelu

---

我无法理解你的回答... ([a-z]*([a-z])\2[a-z]*){2} 旨在匹配像 Abbott, Annette 等单词，而不仅仅是 abbcabbc... 我看不出如何在不使用反向引用的情况下完成这个任务... [a-z]{2,} 表示任意字母重复2次或更多次... 这将匹配像 ab 或 xyz这样的重复字母，而不仅仅是 ee 或 oo。 - Sundeep

你是对的，抱歉。反向引用是必须的（因为我正在处理另一个使用相同问题类型但使用变量的项目[所以内容总是相同]。我删除了第一个（非反向引用正则表达式）。 - NeronLeVelu

没有问题... 扩展版本为 [a-z]*([a-z])\1[a-z]*[a-z]*([a-z])\2[a-z]*，如问题中所提到的... 或者使用 [a-z]*([a-z])\1[a-z]*([a-z])\2[a-z]* 来删除中间的冗余字符类... 对于三个这样的重复对，可以使用 [a-z]*([a-z])\1[a-z]*([a-z])\2[a-z]*([a-z])\3[a-z]* 等等... 我的问题是为什么 ([a-z]*([a-z])\2[a-z]*){2} 或 ([a-z]*([a-z])\2[a-z]*){3} 不能工作... 因为它们更加简洁和清晰。 - Sundeep

也许我的问题表述不够清晰，但我并不是在寻找 ([a-z])\1{1,} ... 只需要 ee 或 oo 即可，不需要 eee 或 eeee 等等... Abbott 包含两个重复字母 bb 和 tt... 而 Chattahoochee 则包含三对重复字母... tt、oo 和 ee。 - Sundeep

你还在说捕获组上的量词重复匹配的字符串而不是正则表达式本身吗？请参考我问题后半部分中的例子...还有，对于简单的情况，echo 'aacddf' | grep -xE '(([a-z])\2[a-z]){2}' 和 echo 'aacddfeex' | grep -xE '(([a-z])\2[a-z]){3}'。 - Sundeep

Answer 3

我已经提出了一个问题https://debbugs.gnu.org/cgi/bugreport.cgi?bug=26864，现在手册已经更新以反映这些问题。

来自https://www.gnu.org/software/grep/manual/grep.html#Known-Bugs：

回溯引用会大大降低匹配速度，因为它们可以生成指数级的匹配可能性，这些可能性会消耗时间和内存来探索。此外，在 POSIX 规范中，对于回溯引用有时不太清楚。此外，许多正则表达式实现具有回溯引用错误，可以导致程序返回不正确的答案甚至崩溃，修复这些错误通常不是优先考虑的事情：例如，截至 2020 年，GNU C 库缺陷数据库 包含回溯引用错误 52、10844、11053、24269 和 25322，并且几乎没有即将发布的修复迹象。幸运的是，回溯引用很少有用，因此在实际应用中避免它们应该不会带来太多麻烦。

- Sundeep

Answer 4

更新

在搜索一番后，我在我的Windows电脑上安装了gnugrep32，然后进行了一些测试：

我从一个旧的SO帖子中读到了这个：

非贪婪匹配不是grep支持的扩展正则表达式语法的一部分

因此，我们使用[a-z]{0,20}作为测试，而不是[a-z]*或[a-z]*?其中?被忽略（什么鬼？）

以下是使用总体(){n}的增量测试，以查看在回溯停止之前它会走多远。

---

开始工作

(([a-z])\2[a-z]{0,20}){1}   len = 2    rr
(([a-z])\2[a-z]{0,20}){2}   len = 4    rrrr
(([a-z])\2[a-z]{0,20}){3}   len = 25   rrrrrrrrrrrrrrrrrrrrrrrrr
(([a-z])\2[a-z]{0,20}){4}   len = 47   rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
(([a-z])\2[a-z]{0,20}){5}   len = 69   rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
(([a-z])\2[a-z]{0,20}){6}   len = 91   rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr

从{3}到{6}的增量长度都等于22。

这恰好是捕获框架表达式([a-z])\2[a-z]{0,20}的完整长度，当它不回溯到之前的框架时。

结论是它在2个框架后自动停止回溯。

这很有道理，例如，在20个框架中，它到达第16个框架，并发现无法匹配。它应该回到第1个框架进行调整，然后再尝试一遍。

当然，没有(([a-z])\2[a-z]*){3}的测试用例，因为贪婪量词*如果它们全部是[a-z]，将在第二帧上消耗整行并且永远不会开始第三帧。

- user557597

---

@Sundeep - ERE代表什么？也许你没有看到我的回答中的这一部分 It didn't work with (([a-z])\2[a-z]*){3}，但是你可以随意给我点踩，我不在乎。 - user557597

我没有点踩... ERE是扩展正则表达式，你可以查看这个手册来获取文档... 因此，如果你使用echo 'aazbbycc' | grep -E '(?:([a-z])\1[a-z]*){2}'，你会在GNU grep上得到语法错误。 - Sundeep

嘿，能再解释一下这部分吗？你是怎么测试的？“帧”指的是什么？看起来你已经找到了一种了解引擎内部发生情况的方法...此外，Casimir 在评论中提到 grep 不使用回溯机制(简而言之，所有可能的路径都被存储，最长的路径获胜)。 - Sundeep

@Sundeep - 这毫无意义。 echo "aabbXcc" | grep -E "(([a-z])\2.{0,3}){3}" 没有匹配 echo "aabbXXcc" | grep -E "(([a-z])\2.{0,3}){3}" "aabbXXcc" - user557597