具有交替和重复的非greedy正则表达式[重复]

Question

我正在尝试使用扩展正则表达式（例如使用 awk）匹配 AB 和 BA 之间的内容。

考虑两个示例字符串AB12BABA和AB123BABA，我尝试了以下正则表达式

AB([^B]|([^B][^A]|B[^A]|[^B]A))*BA

但它匹配两个示例的整个字符串（贪婪）。

谁能解释一下正则表达式引擎在这种情况下是如何工作的，以及我应该如何更改我的正则表达式以使其正常工作。

Answer 1

使用环顾四周和不贪婪的量词：

(?<=AB).*?(?=BA)

如果您也想匹配分隔符，只需：

AB.*?BA

Answer 2

BRE 和 ERE 引擎将与最左边的最长规则匹配，这与 Perl 和其他基于 NFA 的正则表达式引擎匹配正则表达式的方式不同。

Boost库的文档在技术方面更详细，所以我在这里引用它:

通常有不止一种方法可以在特定位置匹配正则表达式，对于POSIX基本和扩展正则表达式，“最佳”匹配确定如下：

1. 找到最左边的匹配，如果在这个位置只有一个匹配，那么返回它
2. 找到最长的匹配，以及任何领带。如果只有一个这样的可能匹配，则返回它
3. 如果没有标记的子表达式，那么剩下的所有备选方案都无法区分；返回找到的第一个
4. 查找与最左侧位置的第一个子表达式匹配的匹配项，以及任何连接。如果只有这样的匹配，则返回它
5. 查找与第一个子表达式匹配时间最长的匹配项，以及任何连接。如果只有一个这样的匹配，则返回它
6. 对每个其他标记的子表达式重复步骤4和5
7. 如果还剩下一个以上的可能匹配，则它们是不可区分的；返回找到的第一个

文中提到的标记子表达式是指 （） 捕获组。请注意，它们仅执行捕获，不支持反向引用。

因此，为了进行延迟匹配，需要构造一个正则表达式，使其匹配重复的部分，同时避免在最后匹配尾部。由于ERE和BRE等价于理论正则表达式，因此只要您能够构造DFA，就存在一个等价的正则表达式（只是在某些情况下构造它不是一项简单的任务）。

根据您的要求，此正则表达式将起作用：

AB([^B]|B+[^AB])*B*BA

部件 （[^B]|B [^AB]）*B* 匹配不包含字符串“BA”的任何字符串。

这是用于匹配不包含字符串“BA”的字符串的DFA。

这里的符号不标准，所以我解释一下：

• 状态q1/B表示状态被命名为q1（就像您如何命名变量一样），B是匹配BA的当前进度
• *表示字母表中的任何字符[^B]表示字母表中除B以外的任何字符

在DFA中，q0和q1是最终状态，q0是初始状态。请注意，q2是一个陷阱状态，因为它是一个非最终状态，并且没有从这个状态过渡出来。

使用此处的步骤，或者仅使用 JFLAP 派生正则表达式。（在 JFLAP 中，您应该使用一些字符，例如 C 来表示 [^AB]）。

由于q2是陷阱态，我们可以将其从公式中排除:

R0 =  [^B]R0 + BR1 + λ
R1 = [^AB]R0 + BR1 + λ

将Arden定理应用于R1：

R1 = B*([^AB]R0 + λ)

将R1替换为R0:

R0 = [^B]R0 + BB*([^AB]R0 + λ) + λ

将BB*分布在（[^AB]R0λ）上：

R0 = [^B]R0 + BB*[^AB]R0 + BB*λ + λ

组合在一起:

R0 = ([^B] + BB*[^AB])R0 + (BB* + λ)

将雅顿定理应用于 R0：

R0 = ([^B] + BB*[^AB])*(BB* + λ)

(< code>BB*或< code>λ(空字符串))等效于< code>B*:

R0 = ([^B] + BB*[^AB])*B*

让我们把它改写成< code>awk的语法:([^B]|B [^AB])*B*，如上所示。