防止正则表达式在特定模式之前回溯

Question

在正则表达式中（在任何高级实现中，例如：PERL、Ruby、Python正则表达式模块），是否有可能禁止通过特定匹配模式之前的所有回溯？以下是一个简单的例子：假设我想要创建一个正则表达式来验证一个简单语言。该语言由以下组成：

- 仅由数字（0到9）组成 - @后跟a或b。

请注意，空字符串是有效的。因此，这些是有效的：" "，"123"，"@a"，"1@b"，"@a123"，而这些是无效的："X"，"@"，"@@"，"@1"，"a"，"@aa"。

我想构建一个正则表达式，以匹配有效情况并且不匹配无效情况（失败）。但需要注意以下几点：

- 我正在使用从字符串开头开始搜索的匹配函数，但不强制进行完全匹配... 我希望避免这种情况，并且请不要使用$来匹配字符串的结尾。这最多只是一个解决方法，我们知道在检查字符串的结尾位置或剩余字符串的内容之前，该字符串不会匹配。我必须补充说，我不能使用这个方法，因为我的玩具语言可以用于更广泛的语言，给定的字符串不会在那里结束...这不会破坏我们在检查字符串的结尾位置或剩余字符串的内容之前就知道该字符串不会匹配我们的语法的事实。 - 如果我们匹配@并且在它之后匹配a或b失败，那么没有必要进行任何回溯，因为整个字符串将无法匹配给定的语法。 - 我需要正则表达式失败而不是只匹配部分字符串。

我想编写的正则表达式如下：

 (@![ab]|[0-9]|!(?!))*

以我的想象为基础，加入了!字符，如果遇到该字符，则不允许回溯。如果剩余的字符串与剩余的模式不匹配，则整个模式将无法匹配整个字符串。注意，如果最后一个备选项是!(?!)，则遇到该字符时整个模式将失败。

我研究了原子组和贪婪量词，但我无法看出如何使用它们来模拟所需的结果。

以下是设置测试环境的简单方法：

pip install regex &&
cat <<EOF > ./test_regex.py
#!/usr/bin/env python

import sys, regex

def check_regex(rx, *strings):
    for string in strings:
        m = regex.match(rx, string)
        print("match %-4s for %r" %
              ("Fail" if m is None else m.end(), string))

check_regex(*sys.argv[1:])
EOF
chmod +x test_regex.py

接下来是测试命令及其期望输出，请填写MYSTERY_REGEX：

./test_regex.py MYSTERY_REGEX "" "123" "@a" "1@b" "@a123" "X" "@" "@@" "@1" "a" "@aa"
match 0    for ''
match 3    for '123'
match 2    for '@a'
match 3    for '1@b'
match 5    for '@a123'
match Fail for 'X'
match Fail for '@'
match Fail for '@@'
match Fail for '@1'
match Fail for 'a'
match Fail for '@aa'

请注意，(@[ab]|[0-9])*$是一个简单的答案，可以产生正确的输出，但它使用了一个明确被禁止在此处使用的最后一个$。

那么，您能否消除对完全匹配的需求？如果不能，能否详细说明为什么不可能？

- vaab

---

请注意，我想要的与PROLOG的“！”非常相似（更多信息：http://en.wikipedia.org/wiki/Cut_%28logic_programming%29） - vaab

我知道，这个问题非常老，但我认为答案是负预查。顺便说一句，如果这应该匹配更大的语言，则“！（？！）”部分没有意义。我将其删除： （@[ab] | [0-9]）* +（？！[@0-9]） 如果您想匹配字符串的结尾，则可以再次添加它：（@[ab] | [0-9]）* +（？！。） - ChrisoLosoph

Answer 1

我最近在浏览PCRE2文档中发现了答案，它在“回溯动词”部分。

有一个回溯动词(*COMMIT)，意思是“强制后续的RegExp部分匹配或不匹配任何进一步的内容”。这里的“后续RegExp部分”指的是(*COMMIT)右边的部分。后续的RegExp部分可以由原子组或断言（如前瞻或后顾）内的闭合括号)进行分隔。

让我们将其应用于你的想法：

(@(*COMMIT)[ab]|[0-9])+

它不会找到空匹配。正如OP请求的那样，它不必匹配到主题字符串的结尾。

每当它读取@时，它就会进展到(*COMMIT)回溯动词的立即左侧。然后，它通过右侧。然后，如果没有匹配[ab]，它会尝试回溯，但是当回溯流到达(*COMMIT)的右侧时，尝试向其左侧移动时，整个匹配尝试将失败。根据文档here，参见“在回溯之后起作用的动词”部分，当它使用(*COMMIT)失败时，甚至不会尝试新的匹配尝试

即使模式未锚定，也不会通过推进起始点来进行进一步的查找匹配尝试。如果(*COMMIT)是遇到的唯一回溯动词，一旦它被传递给pcre2_match()，就会致力于在当前起始点找到匹配，否则不会找到。

这并不意味着它不能找到多个匹配，但当 (*COMMIT) 第一次失败时，它会停止搜索新的匹配。这意味着，它不会丢弃早期成功尝试中已经找到的匹配项。

还有另一个回溯动词(*PRUNE)，当回溯控制流从右向左通过它时，也会导致整个匹配尝试失败。但与(*COMMIT)不同，它允许进行进一步的匹配尝试。我不理解文档中对 (*COMMIT) 的比较，但我使用 regex101 测试了 (*PRUNE)，它也提供了很好的解释。

如果你需要更多控制，以便确定新匹配尝试不可能从哪个主题字符开始，你可以使用(*SKIP)或(*SKIP:<name>)。 (*SKIP)类似于(*PRUNE)，但还要求每次新的匹配尝试都在其右侧开始，即在达到(*SKIP)之前最后匹配的字符之后。 可选名称可指向另一个位置-由(*MARK:<name>)注释-用于跳过新的匹配尝试。 它将通过字符串向后撤退（不再进入断言或原子组）搜寻标记，当未找到适当的标记时，(*SKIP)将根据文档而被忽略。

(*SKIP)就像修改最新回溯点，使其指向新位置。然而，在许多情况下，这并不是一个功能性的添加，仅仅为优化服务，这使得它对可读性产生怀疑。我希望有一个智能引擎可以自动推断出这种“跳过”以进行性能优化。

(*SKIP)有用的示例：

• 主题字符串的语言：(abab|abac)*
• 主题字符串中所需匹配项：abab（但不与abac重叠）
• PCRE2解决方案：aba(*SKIP)b

- ChrisoLosoph

Answer 2

为了使用正则表达式模块限制回溯：

^[0-9]*+(?>@[ab])?[0-9]*+$

请注意，您需要使用锚点。

如果允许带有@的多个部分：

^[0-9]*+(?>@[ab][0-9]++)*(?>@[ab])?[0-9]*+$    

- Casimir et Hippolyte

---

嗯，如果使用锚点“(@[ab]|[0-9])*$”就足够了... 这意味着我们不会强制失败。我想避免使用'$'，因为我的小玩具语言可能被包含在更大的语言中，因此字符串可能不会在那里结束，但是，正则表达式匹配应该失败，并且并不是事实上我们到达了字符串的结尾才使字符串不匹配。但还是谢谢你的努力 ;) - vaab

@vaab：在这种情况下，使用原子组和占有量词是不够的，你必须用允许匹配前后的查找来替换两个锚点。例如：在@a之后，[ab]是不允许的。 - Casimir et Hippolyte

Answer 3

在Perl 6中，使用:修饰符是可能的，但在这种情况下，最好使用语法结构

- jjmerelo

---

无论出于何种原因，Perl 6 必须远离正则表达式惯例，这使我花了一段时间才理解。这个答案与问题无关，实际上是关于 Perl 6 中占有量词的奇怪替换符号的说明。Perl 6 将 ?+、*+ 和 ++ 转化为 ?:、*: 和 +:。占有量词不会抛弃每一个现有的回溯点，只会抛弃特定量词所创建的那些回溯点。文档中所宣传的使用情形也有点奇怪，用于解析没有显式分隔符的标记。我本以为只有我这样想出古怪的东西。 - ChrisoLosoph

@ChrisoLosoph，原始问题只是简单地标记为“regex”：选择您喜欢的任何正则表达式引擎！OP明确提到了Perl、Ruby和Python，所以我猜想Raku（又名Perl6）也是可以的。祝好！ - jubilatious1

很抱歉，我的评论可能过于间接了。我并没有批评在这个答案中使用Riku的语法（尽管它非常不直观）。我想指出这个答案存在的问题。首先，缺乏适当的解释（参考文档本身就像Riku的正则表达式语法一样不清晰）。其次，仅仅将Riku相同概念的语法变化视为问题的解决方案。看起来作者误解了语法变化是语义变化。而且语法显然偏离了问题，因此并不是一个好的答案。 - ChrisoLosoph