正则表达式贪婪的解析方向

2018-06-04 01:20:03

我发现关于如何执行贪婪正则表达式有两种不同的观点：

一个是，读取所有输入字符串并从后面匹配模式，首先匹配整个输入，第一次尝试是整个字符串。一些文章支持这个观点是Oracle官方的Java教程：

贪婪的量词被认为是“贪婪的”，因为它们强制匹配器在尝试第一次匹配之前读入或吃掉整个输入字符串。如果第一次匹配尝试（整个输入字符串）失败，则匹配器将输入字符串退回一个字符，然后再次尝试，重复该过程直到找到匹配或者没有更多字符需要退出。

也看到这篇文章：贪婪与懒惰正则表达式量词的表现

另一个是从前面匹配，第一个匹配尝试来自左侧的0索引。当发现匹配时，引擎不停止，保持匹配，直到它失败，然后它会回溯。文章支持这个意见，我发现是：

重复使用Star，并加上Looking Inside The Regex Engine部分讨论<.+> ：

正则表达式中的第一个标记是<。这是一个文字。正如我们已经知道的那样，匹配的第一个地方是字符串中的第一个<。

我想知道哪一个是正确的？这很重要，因为它会影响正则表达式的效率。我添加了各种语言标签，因为我想知道它在每种语言中的实现方式是否有所不同。

“匹配器将输入字符串退回一个字符并再次尝试”仅仅是描述回溯，所以“然后回溯”就是说同样的事情。既然你对贪婪的言论都说同样的话，两者都是正确的。（你的第三个引语与贪婪无关。）

我们来举个例子。

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*)bb/;

尝试在pos 0。

[ab]*匹配0个字符“”。

在pos 0， bb不能匹配⇒回溯。

[ab]*无法匹配⇒回溯。

试试pos 1。

[ab]*匹配0个字符“”。

在pos 1， bb不能匹配⇒回溯。

[ab]*无法匹配⇒回溯。

尝试在pos 2。

[ab]*匹配6个字符“ abbbbb ”。

在pos 8， bb不能匹配⇒回溯。

[ab]*匹配5个字符“ abbbb ”。（退一个）

在pos 7， bb不能匹配⇒回溯。

[ab]*匹配4个字符“ abbb ”。（退一个）

在pos 6， bb匹配。

成功。

所以$ 1是“abbb”。（不是abbbbbbb 。“贪婪”并不意味着“可能的最长匹配”。）

现在，让我们看看如果我们让“*”不贪婪会发生什么。

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*?)bb/;

尝试在pos 0。

[ab]*? 匹配0个字符“”。

在pos 0， bb不能匹配⇒回溯。

[ab]*无法匹配更多⇒回溯。

试试pos 1。

[ab]*? 匹配0个字符“”。

在pos 1， bb不能匹配⇒回溯。

[ab]*无法匹配更多⇒回溯。

尝试在pos 2。

[ab]*? 匹配0个字符“”。

在pos 2， bb不能匹配⇒回溯。

[ab]*? 匹配1个字符“ a ”。（添加一个）

在pos 3， bb匹配。

成功。

所以1美元是“a”。

具体的实现可能会以不同的方式进行优化，只要它提供与此处所示相同的结果即可。你可以在工作中看到Perl

perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*)bb/;'
perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*?)bb/;'

假设它们在功能上是等价的（并且基于我的Java正则表达式的使用，它们就是），但这只是引擎实现方面的差异。正则表达式在所有语言中的执行方式都不完全相同，根据您使用的语言可能会有所不同。

第二个链接描述Perl，所以我相信甲骨文在Java方面的事情。

两者都试图获得最大的可能比赛。

通过添加?量化懒人键将尝试尽可能小的比赛。

在不同环境和编程语言中实现正则表达式不一定是相同的，所以对于你的问题没有确切的答案。

如果你使用Perl ，那么你应该知道regex实现是非常优化的 ，因为这是这种编程语言最强大的功能之一。所以，不要担心效率:)

链接地址: http://www.djcxy.com/p/13415.html

上一篇: Regex greedy parse direction

下一篇: Why does regex not match when there are more then one #?