regex - 如何订购正则表达式替代品以获得最长匹配？

Question

我有多个正则表达式 regex1 , regex2 , ..., regexN合并为一个正则表达式 regex1|regex2|...|regexN .我想重新排序组件表达式，以便组合表达式在给定字符串的开头给出最长的可能匹配。

我相信这意味着重新排序正则表达式，以便“如果 regexK 匹配前缀 regexL ，则 L < K ”。如果这是正确的，是否可以找出一般情况下 regexK可以匹配前缀 regexL ?

Answer 1

使用正确的正则表达式 flavor !

在某些正则表达式风格中，提供最长匹配的交替是使用的交替(“贪婪交替”)。请注意，这些正则表达式中的大多数都是旧的(但今天仍在使用)，因此缺少一些现代结构，例如反向引用。

Perl6 是现代的 ( and has many features )，但默认为 POSIX 风格的最长交替。 (您甚至可以切换样式，因为 || 会创建一个交流发电机，该交流发电机会短路以进行第一次匹配。)请注意，需要使用 :Perl5/:P5 修饰符才能使用“传统”正则表达式样式。

此外，PCRE 和较新的 PCRE2 具有相同的功能。在 PCRE2 中，它是 pcre2_dfa_match 。 (有关 DFA 的更多信息，请参阅我的有关正则表达式引擎设计部分的相关信息部分。)

这意味着，您可以在管道中使用任何顺序的语句，并且结果将始终是最长的。

(这与“绝对最长”匹配不同，因为在交替中重新排列术语不会改变所有正则表达式引擎从左到右遍历字符串的事实。显然，.NET 除外，它可以从右到左。但向后遍历字符串也不能保证“绝对最长”匹配。)如果您真的想(仅)在字符串的开头找到匹配项，您应该 anchor 定表达式: ^(regex1|regex2|...) 。

根据 this page*:

The POSIX standard, however, mandates that the longest match be returned. When applying Set|SetValue to SetValue, a POSIX-compliant regex engine will match SetValue entirely.

* 注意:我没有能力测试每个 POSIX 风格。此外，一些正则表达式风格 (Perl6) 具有这种行为，但总体上不符合 POSIX 标准。

举一个我在自己电脑上验证过的具体例子:
echo "ab c a" | sed -E 's/(a|ab)/replacement/'
正则表达式是 (a|ab) 。当它在字符串 ab c a 上运行时，您会得到: replacement c a ，这意味着您实际上得到了交流发电机可以提供的 最长匹配 。

这个正则表达式，对于更复杂的例子， (a|ab.*c|.{0,2}c*d) 应用于 abcccd ，将返回 abcccd 。

Try it here!

更多说明:正则表达式引擎将不会继续(在搜索字符串中)查看是否存在更长的匹配项，一旦它可以匹配某些内容。它只会查看当前的更改列表，以查看另一个更改列表是否会匹配更长的字符串(从初始匹配开始的位置)。

换句话说， 无论更改中选择的顺序 ，符合 POSIX 的正则表达式都使用匹配最多字符的正则表达式。

具有此行为的其他 flavor 示例:

Tcl 是

POSIX ERE

GNU BRE

GNU ERE

regex引擎设计相关信息

This question 询问有关设计引擎的问题，但答案可能有助于了解这些引擎的工作原理。本质上，基于 DFA 的算法 确定了不同表达式的常见重叠， 尤其是在交替中的那些。可能值得检查 this page 。它解释了如何将替代方案组合成一条路径:


注意:在某些时候，您可能只想考虑使用实际的编程语言。正则表达式不是一切。