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

Question

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

我相信这意味着重新排序正则表达式,"如果regexK匹配前缀regexL,那么L < K".如果这是正确的,通常是否regexK可以找出是否可以匹配前缀regexL？

Answer 1

使用正确的正则表达风味!

在一些正则表达式中,提供最长匹配的交替是使用的交替("贪婪交替").请注意,大多数这些正则表达式都是旧的(现在仍然使用),因此缺少一些现代结构,如反向引用.

Perl6是现代的(并且具有许多功能),但默认为POSIX风格的最长交替.(您甚至可以切换样式,因为||创建一个短路到第一个匹配的交流发电机.)请注意,:Perl5/:P5需要修改器才能使用"传统"正则表达式样式.

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

这意味着,您可以在管道中拥有任何语句顺序,结果将始终最长.

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

根据这个页面*:

但是,POSIX标准要求返回最长的匹配.申请Set|SetValue时SetValue,符合POSIX标准的正则表达式引擎将SetValue完全匹配.

*注意:我没有能力测试每种 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.

试试吧!

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

换句话说,无论更改中的选择顺序如何,POSIX兼容的正则表达式都使用与大多数字符匹配的正则表达式.

具有此行为的其他味道的其他示例:

• Tcl ARE
• POSIX ERE
• GNU BRE
• GNU ERE

有关正则表达式引擎设计的相关信息

这个问题询问设计引擎,但答案可能有助于理解这些引擎的工作原理.基本上,基于DFA的算法确定不同表达式的共同重叠,尤其是在交替中的那些表达式.可能值得查看此页面.它解释了如何将替代方案组合到一条路径中:

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

Answer 2

Longest Match

不幸的是,没有明确的逻辑可以告诉正则表达式
引擎获得最长的匹配.

这样做会/可能会创建一个疯狂的级联回溯剧集.
根据定义,它的复杂性太大而无法应对.

所有正则表达式都是从左到右处理的.
发动机可以先匹配任何东西,然后拯救.

这是交替,其中尤其如此, this|this is|this is here
总是会匹配' this是这里的第一和
将永远不会永远一致this is,也不this is here

一旦你意识到这一点,你可以重新排序
this is here|this is|this每次给出最长匹配的交替.

当然,这可以减少到this(?:(?: is)? here)?
获得最长匹配的聪明方式.

没有看到你想要结合的正则表达式的任何例子,
所以这只是一些一般信息.

如果您显示正在尝试合并的正则表达式,则可以
提供更好的解决方案.

交替内容确实相互影响,以及
群集之前或之后的任何内容都可以影响交替匹配.

如果你有更多问题,请问.

附录:

对于@Laurel.这总是可以使用Perl 5正则表达式(> 5.10)来完成,
因为Perl可以从正则表达式子表达式中运行代码.
由于它可以运行代码,因此可以计算并获得最长的匹配.

然而,最左边的规则永远不会改变.
如果正则表达式是热力学,那么这将是第一定律.

Perl是一个奇怪的实体,因为它试图在正则表达式
和代码执行之间创建协同作用.

因此,可以重载它的运算符,将
自定义注入语言本身.
他们的正则表达式引擎没有什么不同,可以以相同的方式定制.

因此,从理论上讲,下面的正则表达式可以构成一个正则表达式构造,
一个新的Alternation构造.

我不会在这里详述,但足以说明,它不适合胆小的人.
如果您对此类事物感兴趣,请参阅 " 创建自定义RE引擎 " 部分下的perlre联机帮助页

Perl的:

注-正则表达式交替形式是基于@Laurel 复杂的例子
(a|ab.*c|.{0,2}c*d)应用到abcccd.

在视觉上,如果制作成自定义的正则表达式构造,看起来类似于
交替(?:rx1||rx2||rx3),我猜这是
在将regex引擎直接集成到语言方面很多Perl6的完成方式.

此外,如果按原样使用,则可以根据需要动态构造此正则表达式.
请注意,Perl正则表达式构造的所有丰富性都可用.

产量

Longest Match Found:  abcccd

码

use strict;
use warnings;

my ($p1,$p2,$p3) = (0,0,0);
my $targ = 'abcccd';

# Formatted using RegexFormat7 (www.regexformat.com)

if ( $targ =~
/
   # The Alternation Construct
     (?=
          ( a )                         # (1)
          (?{ $p1 = length($^N) })
     )?
     (?=
          ( ab .* c )                   # (2)
          (?{ $p2 = length($^N) })
     )?
     (?=
          ( .{0,2} c*d )                # (3)
          (?{ $p3 = length($^N) })
     )?
   # Check At Least 1 Match
     (?(1)
          (?(2)
               (?(3)
                 |  (?!)
               )
          )
     )
   # Consume Longest Alternation Match
     (                                  # (4 start)
          (?(?{
               $p1>=$p2 && $p1>=$p3
            })
               \1 
            |  (?(?{
                    $p2>=$p1 && $p2>=$p3
                 })
                    \2 
                 |  (?(?{
                         $p3>=$p1 && $p3>=$p2
                      })
                         \3 
                    )
               )
          )
     )                                  # (4 end)
/x ) {

    print "Longest Match Found:  $4\n";
} else {
    print "Did not find a match!\n";
}