正则表达式中的顺序环视会影响可以匹配哪些语言吗？

Question

正则表达式中的顺序环视会影响可以匹配哪些语言吗？

regexlookbehindregex-lookarounds

81

现代正则表达式引擎中有一些功能，使您能够匹配在没有该功能的情况下无法匹配的语言。例如，以下使用反向引用的正则表达式匹配由重复的单词组成的所有字符串的语言：(.+)\1。这种语言不是正则的，不能被不使用反向引用的正则表达式匹配。

环视是否也影响正则表达式可以匹配的语言？即，是否有任何语言可以使用环视进行匹配而无法以其他方式进行匹配？如果是这样，那么对于所有类型的环视（负面或正面前瞻或后顾），还是仅适用于其中一些类型呢？

- sepp2k

4

据http://www.regular-expressions.info/lookaround.html所述，回顾界定符允许您创建无法在没有它们的情况下创建或使用它们可能变得非常冗长的正则表达式。但是，该方向上唯一的示例是关于无法查找和匹配未跟随_u_的_q_。这并没有说明是否可以判断输入字符串是否包含未跟随_u_的_q_（而不仅仅是匹配该_q_）。 - Christian Semrau

7

可能这并不是一个纯粹的编程问题，但要求只是“与编程有关”，我认为这符合要求。对于我来说，这个问题实际上从实践的角度来看非常有趣，因为它在编程过程中出现了。 - sepp2k

2

@Christian Semrau: 我对“与编程有关”的主要标准是，如果问题在类似的会计网站上（进行明显的简单替换），是否适合。正则表达式通常是一个严格的编程事物。我个人认为这是主题内的内容。 - David Thornley

5

显然，关于CS是否应该出现在StackOverflow上的问题已经被讨论过：http://meta.stackexchange.com/questions/26889/is-there-a-stackoverflow-like-site-for-computer-science。就个人而言，我希望在这里看到更多关于CS的问题，或者如果必要的话，建立一个姊妹网站来进行讨论。 - polygenelubricants

1

http://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto - Ciro Santilli OurBigBook.com

显示剩余2条评论

4个回答

26

正如其他答案所说，回顾先行断言并没有为正则表达式增加任何额外的功能。

我认为我们可以通过以下方式来展示：

一个鹅卵石2-NFA（参见引用该文件的介绍部分）。

鹅卵石2NFA不涉及嵌套的前瞻，但是，我们可以使用多鹅卵石2NFAs的变体（见下面的章节）。

介绍

2-NFA是一种非确定性有限状态自动机，具有在其输入上向左或向右移动的能力。

单个鹅卵石机器是指该机器可以在输入带上放置一个鹅卵石（即使用一个鹅卵石标记特定的输入符号），并根据当前输入位置是否存在鹅卵石执行可能不同的转换。

众所周知，一个鹅卵石2-NFA与常规DFA具有相同的功能。

非嵌套前瞻

基本思路如下：

2NFA允许我们通过在输入带上向前或向后移动来回溯（或“前溯”）。因此，对于前瞻，我们可以执行前瞻正则表达式的匹配，然后回溯我们已经消耗掉的内容，以匹配前瞻表达式。为了确切地知道何时停止回溯，我们使用鹅卵石！在进入前瞻DFA之前，我们将鹅卵石丢弃以标记需要停止回溯的位置。

因此，在运行我们的字符串通过卵石2NFA之后，我们知道是否匹配了前瞻表达式，剩余的输入（即需要消耗的内容）正好是匹配剩余所需的内容。

所以对于形式为u(?=v)w的前瞻，

我们有u，v和w的DFAs。

从DFA u的接受状态（是的，我们可以假设只有一个）开始，我们将e转换为v的起始状态，并用卵石标记输入。

从v的接受状态开始，我们将e转换为一个状态，该状态一直向左移动输入，直到找到卵石，然后转换为w的起始状态。

从v的拒绝状态开始，我们将e转换为一个状态，该状态一直向左移动，直到找到卵石，并且转换为u的接受状态（即我们离开的地方）。

用于展示r1 | r2或r*等常规NFAs的证明也适用于这些单卵石2NFAs。有关如何将组件机器组合成r*表达式等更大的机器，请参见http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa获取更多信息。

以上关于r*等的证明之所以有效，是因为回溯确保了在我们进入重复组件nfas时输入指针总是在正确的位置。此外，如果使用了一个pebble，则它正在被一个向前看组件机器处理。由于从向前看机器到向前看机器没有转换而不完全回溯并取回pebble，因此只需要一个pebble机器。

例如考虑([ ^ a] | a(? = ... b))*和字符串abbb。

我们有abbb通过peb2nfa进行a(? = ... b)，在其末尾，我们处于状态：(bbb，matched)（即在输入中仍有bbb，并且已匹配'a'后跟'..b'）。现在由于*，我们回到开头（请参见上面链接中的构造），并进入[ ^ a]的dfa。匹配b，返回开始，再次输入[^a]两次，然后接受。

处理嵌套的向前看

为了处理嵌套的向前看，我们可以使用这里定义的k-pebble 2NFA的受限版本：Two-Way and Multi-Pebble Automata及其Logics的复杂性结果（请参见Definition 4.1和Theorem 4.2）。

通常情况下，2个鹅卵石自动机可以接受非正则集合，但有以下限制：k个鹅卵石自动机可以被证明是正则的（上述论文中的定理4.2）。如果鹅卵石是P_1、P_2、...、P_K：

- 只有在P_i已经在磁带上时，才能放置P_{i+1}，只有在P_{i+1}不在磁带上时，才能拿起P_i。基本上，鹅卵石需要以LIFO方式使用。 - 在放置P_{i+1}和拿起P_i或放置P_{i+2}之间的时间内，自动机只能遍历位于P_{i}当前位置和朝向P_{i+1}方向上输入单词结尾之间的子串。此外，在这个子串中，自动机只能作为一个带有鹅卵石P_{i+1}的1鹅卵石自动机。特别地，禁止抬起、放置或感知其他鹅卵石的存在。

因此，如果v是深度为k的嵌套前瞻表达式，则(?=v)是深度为k+1的嵌套前瞻表达式。当我们进入其中的前瞻机器时，我们知道到目前为止必须放置多少个小石头，因此可以准确地确定何时放置小石头，而当我们退出该机器时，我们知道要提起哪个小石头。所有深度为t的机器都是通过放置小石头t进入的，并通过移除小石头t（即返回到深度为t-1的机器的处理）退出。完整机器的运行看起来像树的递归dfs调用，并且可以满足多小石头机器的上述两个限制。

现在，当您组合表达式时，对于rr1，由于进行了连接操作，r1的小石头编号必须增加r的深度。对于r*和r|r1，小石头编号保持不变。

因此，任何具有前瞻的表达式都可以转换为具有上述放置小石头限制的等效多小石头机器，因此是正则的。

结论

这基本上解决了Francis原始证明中的缺点：能够防止前瞻表达式消耗将来需要匹配的任何内容。

由于回顾只是有限的字符串（不是真正的正则表达式），因此我们可以首先处理它们，然后再处理前瞻。

抱歉写得不完整，但完整的证明需要绘制很多图形。

我认为这看起来没问题，但如果有任何错误（我似乎喜欢犯错误:-)），我会很高兴知道。

- Aryabhatta

我不确定这个处理多个前瞻，例如 u(?=v)(?=w)(?=x)z，可以吗？ - Francis Davey

当我们退出Pebble 2NFA以进行前瞻时，我们回到了输入带状态，其中我们输入了一个可用的pebble，并且根据前瞻是否匹配，我们处于两种不同的状态之一（即我们可以判断是否有匹配）。因此，似乎通过仅串联自动机（使用我们添加的具有e转换的额外状态），它将起作用，因为我们总是会得到pebble。但我想这取决于您如何解释该表达式。它是否与u(?=vwx)z相同？还是((u(?=v))?=w)...等？ - Aryabhatta

该表达式匹配一个 u，后面必须跟着（非消耗性的）v、w和x三个正则表达式（其中v、w和x都是通用正则表达式），最后再跟一个 z。尝试构建解决方案后，我相当确信你不能通过组合解决它（即通过连接解决方案）。 - Francis Davey

@Francis：如果需要匹配它们所有，那么连接就可以了（我想）。我们将其连接为dfa(u) -> peb2ndfa(v) -> peb2ndfa(w) -> dfa(x)。如果在匹配u之后，我们没有匹配v或w，我们回到u并从我们离开的地方继续。如果我们匹配v，那么因为我们在v完成后回溯，我们可以再次匹配w（再次回溯），然后匹配x。关键是2NDFA允许我们回溯，而pebble则允许我们知道何时停止回溯。 - Aryabhatta

@sepp2k：我已经编辑了答案，以便更清楚地说明如何使用带有约束条件的多Pebble机器。如果您有问题，请告诉我。 - Aryabhatta

显示剩余4条评论

11

我同意其他帖子的观点，即回溯是正则表达式的一部分（这意味着它不会为正则表达式添加任何基本功能），但我有一个比我看到的其他观点更简单的论据。

我将通过提供DFA构造来展示反向引用是正则的。如果一个语言有一个可以识别它的DFA，则该语言是正则的。请注意，Perl实际上并没有在内部使用DFA（有关详细信息，请参见本文：http://swtch.com/~rsc/regexp/regexp1.html），但是为了证明目的，我们构建了一个DFA。

构建正则表达式的DFA的传统方法是首先使用Thompson算法构建NFA。给定两个正则表达式片段r1和r2，Thompson算法提供了连接（r1r2）、交替（r1|r2）和重复（r1*）正则表达式的构造方法。这样，您可以逐位地构建一个NFA，该NFA识别原始的正则表达式。有关更多详细信息，请参见上面的文章。

为了展示正向和负向前瞻是正则的，我将提供一个用于正则表达式u与正向或负向前瞻相连的构造：(?=v)或(?!v)。只有连接需要特殊处理；通常的交替和重复构造可以很好地工作。

u(?=v)和u(?!v)的构造如下：

换句话说，将u的现有NFA的每个终态连接到一个接受状态和一个NFA for v，但进行修改，如下所示。函数f(v)定义为：

定义函数 aa(v) 作用于 NFA v，将每个接受状态变为“反接受状态”。反接受状态是指对于给定字符串s，如果任何经过 NFA 的路径以这个状态作为终点，则匹配失败，即使另一个经过v的路径以接受状态作为终点也无济于事。
定义函数 loop(v) 作用于 NFA v，在任何接受状态上添加自我转移。换句话说，一旦路径导致到达接受状态，那么该路径无论后面输入什么都可以永久停留在接受状态。
对于负向先行断言，f(v) = aa(loop(v))。
对于正向先行断言，f(v) = aa(neg(v))。

为了提供一个直观的例子来说明为什么这样做有效，我将使用正则表达式(b|a(?:.b))+，这是我在 Francis 的证明评论中提出的正则表达式的稍微简化版本。如果我们将我的构造方法与传统的 Thompson 构造结合起来，就会得到：

alt text

e代表 epsilon 转移（在不消耗任何输入的情况下进行转移），反接受状态用 X 标记。在图的左半部分，你可以看到 (a|b)+ 的表示方式：任何一个a或b都会使得图进入接受状态，但也允许回到开始状态以便我们能够再次匹配。但是请注意，每次我们匹配一个a时，我们也会进入图的右半部分，在那里我们处于反接受状态，直到我们匹配到“any”后面跟着一个b。

这不是传统的NFA，因为传统的NFA没有反接收状态。然而，我们可以使用传统的NFA->DFA算法将其转换为传统的DFA。该算法的工作方式与通常相同，我们通过使我们的DFA状态对应于可能处于的NFA状态的子集来模拟NFA的多个运行。唯一的区别是我们稍微修改了决定DFA状态是否为接受（终止）状态的规则。在传统算法中，如果任何 NFA状态是接受状态，则DFA状态为接受状态。我们将其修改为仅当以下条件成立时，DFA状态才为接受状态：

=1个 NFA状态是接受状态，且
0个NFA状态为反接受状态。

该算法将为我们提供一个可以识别具有前瞻的正则表达式的DFA。因此，前瞻是正则的。请注意，后顾需要单独证明。

- Josh Haberman

在你提供的机器中，你接受了a。但是它不在（b | a(?=.b)）中。同时，反接受状态是一个匹配失败的接受状态？那么根据接受状态的定义，就不存在反接受状态！或者我漏掉了什么？ - Aryabhatta

@Moron：我认为你错过了我的反接受状态的意义。这是同一张图，但有编号的状态: http://imgur.com/ho4C8.png 我的机器不接受 a，因为在匹配 a 后，我们可以使用 NFA->DFA 算法转换到状态 4、3、1 和 5。但是，状态 5 是一个反接受状态，所以根据我写的底部规则，与状态 4、3、1 和 5 相对应的 DFA 状态不是接受状态。 - Josh Haberman

@Josh：aa(v)的定义不是依赖于字符串s吗？也就是说，集合aa(v)可以随着s的变化而变化。同时，你说反接受状态起初是一个接受状态。如果机器最终进入该状态，那么任何匹配都将失败。如果我理解错了，对不起。 - Aryabhatta

@Josh：那是因为你的定义太疯狂了:-)。还有几个问题。即使考虑到反接受状态，你添加的新接受状态是否对应于你构建的DFA中的接受状态，并且是否会接受不应该被接受的字符串？此外，你如何处理嵌套的前瞻？或者像(u(?=v)w)和(u(?=v)w)*这样的东西？抱歉问了这么多问题，我很难理解这个（我怪自己睡眠不足:-P）。 - Aryabhatta

+1 这看起来很清晰、正确，是展示等价性的一种简洁方式。 - Francis Davey

显示剩余9条评论

2

我感觉这里有两个不同的问题：

1. 使用“lookaround”的正则表达式引擎是否比不使用的更强大？ 2. “lookaround”能否使正则表达式引擎具备解析比Chomsky Type 3 - Regular grammar生成的语言更复杂的语言的能力？

实际上，对于第一个问题的答案是肯定的。使用Lookaround将使得使用此功能的正则表达式引擎比不使用此功能的引擎具有更强大的功能。这是因为它为匹配过程提供了更丰富的“锚点”。Lookaround可以将整个正则表达式定义为可能的锚点（零宽度断言）。您可以在这里了解到此功能的强大概述。

虽然Lookaround功能强大，但并不能使正则表达式引擎超越由Type 3 Grammar放置在其上的理论限制。例如，您永远无法可靠地使用装备有Lookaround的正则表达式引擎来解析基于Context Free - Type 2 Grammar的语言。正则表达式引擎仅限于Finite State Automation的能力，这从根本上限制了它们可以解析的任何语言的表达能力，使其仅限于Type 3 Grammar的水平。无论您向正则表达式引擎添加多少“技巧”，使用Context Free Grammar生成的语言始终超出其功能范围。解析Context Free - Type 2 Grammar需要推入自动机来“记住”递归语言结构中的位置。任何需要递归评估语法规则的内容都不能使用正则表达式引擎进行解析。

总结一下：Lookaround为正则表达式引擎提供了一些实际的好处，但在理论层面上并未“改变游戏规则”。

编辑：

是否存在某种复杂度介于Type 3（Regular）和Type 2（Context Free）之间的语法？

我认为答案是否定的。原因是在描述正则语言所需的NFA/DFA大小上没有理论限制。它可能变得任意大，因此不实用（或无法指定）。这就是“环视”等规避方法有用的地方。它们提供了一种简洁机制来指定否则会导致非常大/复杂的NFA/DFA规范的内容。它们并没有增加正则语言的表达能力，只是使其更实用。一旦你明白了这一点，就会发现有很多“功能”可以添加到正则表达式引擎中，以使它们在实际意义上更有用——但没有什么能使它们超越正则语言的限制。

正则语言和上下文无关语言的基本区别在于正则语言不包含递归元素。为了评估递归语言，您需要一个下推自动机来“记住”递归的位置。NFA/DFA不会堆叠状态信息，因此无法处理递归。因此，给定非递归语言定义，将存在一些NFA/DFA（但不一定是实用的正则表达式）来描述它。

- NealB

1

一个比正则文法更强大的文法一定和上下文无关文法一样强大吗？也就是说，已知不存在介于这两者之间的文法吗？ - BlueRaja - Danny Pflughoeft

@BlueRaja：正是我所想的：“语法连续假说” :-) - Aryabhatta

@Moron @BlueRaja - 我已经为你们编辑了我的答案。希望它有所帮助。 - NealB

5

当然，在正则语法和上下文无关语法之间，有许多语法类别是严格介于两者之间的，包括一些简单的例子，比如将正则语法与平衡括号语言的语法组合在一起。其中一个更有用的例子是确定性上下文无关语法。 - Christian Semrau

一个NFA/DFA不会堆叠状态信息，因此无法处理递归。是的，请停止尝试使用正则表达式解析HTML！ - Cruncher

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Francis Davey · Accepted Answer

你所问的问题的答案是：不能用增强的正则表达式来识别比常规语言更大的语言。证明相对简单，但将包含环视的正则表达式转换为不包含环视的正则表达式的算法则比较麻烦。

首先：请注意，您始终可以否定一个正则表达式（在有限字母表上）。给定一个识别该表达式生成的语言的有限状态自动机，您只需将所有接受状态替换为不接受状态，即可得到一个FSA，用于识别该语言的否定形式，其等效于一组等效的正则表达式。

其次：由于正则语言（因此也是正则表达式）在否定下是封闭的，因此它们在交集下也是封闭的，因为A交B = neg(neg(A) union neg(B))根据德摩根定律。换句话说，给定两个正则表达式，您可以找到另一个正则表达式，使其匹配两者。

这使您可以模拟环视表达式。例如u(?=v)w仅匹配与uv和uw都匹配的表达式。

对于负向先行断言，您需要集合论A\B的正则表达式等价物，即A intersect(neg B)，或等价地，neg(neg(A) union B)。因此，对于任何正则表达式r和s，您都可以找到一个正则表达式r-s，它匹配那些匹配r但不匹配s的表达式。用负向先行断言来说：u(?!v)w仅匹配与uw-uv匹配的表达式。

环视之所以有用，有两个原因。

首先，因为否定正则表达式可能会导致更混乱的结果。例如q(?!u)=q($|[^u])。

其次，正则表达式不仅仅用于匹配表达式，它们还可以从字符串中消耗字符 - 或者至少我们喜欢这样认为。例如在Python中，我关心.start()和.end()，因此当然会使用：

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

第三，我认为这是一个相当重要的原因，正则表达式的否定不能很好地覆盖连接。neg(a)neg(b)不等同于neg(ab)，这意味着您不能将lookaround从找到它的上下文中翻译出来-您必须处理整个字符串。我想这使得人们难以使用，并破坏了人们对正则表达式的直觉。

我希望我已经回答了你的理论问题（现在很晚了，所以如果我不清楚，请原谅）。我同意一位评论者的观点，他说这确实有实际应用。当我尝试爬取一些非常复杂的网页时，我遇到了同样的问题。

编辑

对不起，我的表述不够清晰：我不相信您可以通过结构归纳证明正则表达式+lookaround的正则性，我的u(?!v)w示例只是一个例子，而且还是一个简单的例子。结构归纳无法奏效的原因是lookaround的行为方式不具有组合性-这是我上面关于否定的观点。我怀疑任何直接的形式证明都会有很多混乱的细节。我尝试想出一种简单的方法来展示它，但脑海中没有想出来。

为了说明Josh的第一个例子^([^a]|(?=..b))*$，这相当于一个有7个状态的DFSA，所有状态都接受：

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

仅表示状态A的正则表达式如下：

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

换句话说，通过消除环视得到的任何正则表达式通常会更长、更混乱。

回应Josh的评论-是的，我认为证明等价性的最直接方法是通过FSA。这使得事情变得更加混乱的是，构建FSA的通常方式是通过非确定性机器-用epsilon转换将u|v简单地表示为由u和v的机器构造而成的机器。当然，这等价于确定性机器，但存在指数级的状态膨胀风险。相反，否定更容易通过确定性机器完成。

一般的证明将涉及取两个机器的笛卡尔积，并在每个要插入环视的点选择希望保留的那些状态。上面的例子在某种程度上说明了我的意思。

对于没有提供构造的人表示歉意。

进一步编辑：我找到了一篇博客文章，描述了一种从增强了环视的正则表达式生成DFA的算法。它很棒，因为作者以显而易见的方式扩展了NFA-e的“标记epsilon转换”的想法，然后解释了如何将这样的自动机转换为DFA。

我认为类似这样的东西是一种方法来做到这一点，但我很高兴有人写了出来。我无法想出如此简洁的东西。