☰

有没有办法在交替时选择最短的匹配？

tag-icon • tag-icon awk grep regular-expression
有没有办法在交替时选择最短的匹配？

我的印象是 grep 和 awk 使用 NFA（非确定性）正则表达式机器。
本页中间的图片是关于正则表达式匹配可以简单而快速确认情况确实如此。

众所周知，当第一个交替匹配时，NFA 实现可能会停止。例如，链接文章中的这个 NFA 机器例如，考虑 abab|abbb 的 NFA：

在此输入图像描述

对应的正则表达式在匹配第一个 时abab|abbb会达到与字符串右侧的匹配状态。此时它将在到达终点时停止，到达匹配状态(S10)。即使可能存在另一场匹配，也无需测试更多输入。ababbbbabababbb

也就是说，在这段代码中：

echo 'catfish' | grep -Eo 'cat|catfish'

结果应该是，cat但是却是catfish。无论交替与否，结果都是一样的。

是什么让 grep 正则表达式引擎总是找到最长的匹配项？

并且，是否可以更改默认值？

答案1

我认为没有办法用 POSIX 兼容的grepor来做到这一点awk，因为标准确实需要最长的匹配（例如参见regex(7)联机帮助页）。

例如，您可以通过修改程序和正则表达式来awk获得所需的输出awk

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

在这种情况下，我会使用pcregrep（pcre perl 兼容正则表达式库的一部分），它允许您使用以下命令指定编号子组-o：

echo SetValue | pcregrep -o1 '(Set)(Value)?'

或者，因为 PCRE 具有非贪婪匹配的语法，

echo SetValue | pcregrep -o0 'Set(Value)??'

答案2

据我所知，事实证明，事实上，两台 NFA 机器：

  • 传统 NFA 引擎
    一种可回溯的 NFA 机器最长的最左边的匹配并不总是受到尊重。

  • POSIX NFA 引擎
    一种非回溯 NFA 引擎，并行处理所有状态，并可以选择输入字符串中的任何匹配项。选择最左边、最长的匹配是 POSIX 的要求。

然而，DFA 回溯机（Perl）可能会指数级爆炸 (2^n)由文本（而不是正则表达式）驱动，并且可以选择（或不选择）交替中的第一个。

据说还有一个DFA 并行识别所有可能的匹配。

并且，从问题中链接的文章的作者来看，re2 实现将交替定义为： x|y ==> x 或 y （首选 x），即：更喜欢交替中的第一个。

因此，总而言之，没有办法真正将 NFA 或 DFA 与将选择交替的哪一部分相关联，这取决于具体的实现。

而且，不，我还没有找到一种方法来告诉特定的实现更改其默认值。

有关的：

相关内容