为什么星号 (*) 在此正则表达式中充当惰性结构？

Question

为了好玩，我正在编写一个简单的正则表达式引擎，但这破坏了对

*\**

的理解。 正则表达式：

/a*abc/

输入：

abc

在我的脑海和引擎中

/a*abc/

• a*

  是0或更多的时间

• a

  一次

• b

  一次

• c

  一次

所以，当我在

abc

上执行时，我认为第一个

a*

首先消耗

a

和

bc

，不再有

a

并进入下一个FSM状态，需要

a

的

abc

但是输入是

bc

，结果不匹配。

像这样：

1)
regex:
  a*abc
  ^^
input
  abc
  ^

a* consume a {0,N}

2)
regex:
  a*abc
    ^
input
  abc
   ^

no match.

如果在这个匹配中添加一个惰性运算符：

/a*?abc/

• a*?

  是下一个状态不满足时的0次或多次

• a

  一次

• b

  一次

• c

  一次

所以，当我在

abc

上执行时，我认为第一个

a*?

不会首先消耗

a

，因为

abc

满足下一个规则。

像这样：

1)
regex:
  a*?abc
  ^^^
input
  abc
  ^

a*? not consume a because a satisfied next rule a

2)
regex:
  a*?abc
     ^
input
  abc
  ^

3)...4)... match

但是什么？在现实世界中，例如，PCRE 引擎，

*

更像是惰性运算符： 首先

a*

不消耗

a

，跳过状态直接匹配

abc

。 所以，

/a*abc/

应该在

abc

上匹配 true。

为什么第一个贪心状态

a*

不消耗输入？

{0,}

像懒惰的操作员一样工作吗？

Answer 1

当你的第一个正则表达式在第二步不匹配时，它将回到第一步（匹配

a*

部分），并返回一个匹配的符号并尝试继续。

贪婪与懒惰在这种情况下意味着尽可能多（尽可能少）可能。由于先拿

a

但仍然无法匹配，它会把它还给它。

您所描述的是 PCRE 的 possessive 修饰符行为：

a*+abc

将完全按照您描述的方式工作：它获取所有匹配的内容并且不返回任何内容。

忠告：如果你正计划

写一个简单的正则表达式引擎

考虑彻底至少学习this.