regex 防止正则表达式中任何回溯超过特定模式

fquxozlt  于 2023-04-13  发布在  其他
关注(0)|答案(3)|浏览(95)

是否可以使用regex(在任何高级实现中,即:PERL、Ruby、python正则表达式模块)来禁止任何回溯特定的匹配模式?
这里有一个简单的例子:假设我想做一个正则表达式,它必须验证一个简单的语言。这个语言由以下部分组成:

  • 仅数字(09
  • @后接ab

请注意,空字符串是有效的。
所以这些是有效的:"""123""@a""1@b""@a123"无效:"X""@""@@""@1""a""@aa"
我想构建一个正则表达式,匹配有效的情况下,不匹配无效的情况下(失败)。与捕获:

  • 我使用的匹配函数从字符串的开头开始搜索,但不强制完全匹配......我希望有一个解决方案,可以避免这些和所以请不要使用$来匹配字符串的结尾。我们知道**字符串不匹配,而不必检查字符串的结尾。我必须补充一点,我不能使用这个,因为我的玩具语言可以在更广泛的语言中使用,并且给定的字符串不会在那里结束......这不会破坏我们在检查字符串结尾的位置或剩余字符串的内容之前就知道字符串不会匹配我们的语法的事实。
  • 请注意,如果我们匹配@,而它匹配ab失败,则不需要进行任何回溯,因为整个字符串将无法匹配给定的语法。
  • 我需要正则表达式失败不匹配字符串的一部分。

我想写的正则表达式是这样的:

(@![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

然后,这里是test命令,后面是等待的输出:你可以填写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])*$是一个简单的答案,将产生正确的输出,但它使用了一个最终的$,这是明确禁止在这里。

**所以你能消除检查完全匹配的需要吗?**如果你不能,你能详细说明为什么你认为这是不可能的吗?

lnvxswe2

lnvxswe21#

使用regex模块限制回溯:

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

请注意,您需要**才能使用锚点。
如果允许多个带@的部分:

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

1cosmwyk2#

在Perl 6中可以使用:修饰符,但在本例中,使用grammars可能更好

pcww981p

pcww981p3#

我最近在浏览PCRE 2文档中关于“回溯动词”的部分找到了答案。
有一个回溯动词(*COMMIT),意思是“强制后续的RegExp部分匹配或无法匹配任何进一步的东西”。对于“后续的RegExp部分”,我指的是紧接着(*COMMIT)之后的部分。后续的RegExp部分可以由原子组或Assert(如lookahead或lookbehind)内的闭括号)分隔。
让我们把它应用到你的想法:

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

它不会找到空的匹配项。因为OP请求,它不需要匹配到主题字符串的末尾。
每当它读取@时,它会前进到(*COMMIT)回溯动词的左侧。然后它会通过它到右侧。然后,如果没有[ab]匹配,它会尝试回溯,但当回溯流到达(*COMMIT)的右侧时,尝试转到它的左侧,整个匹配尝试将失败。当它与(*COMMIT)失败时,根据这里的文档,它甚至不会尝试新的匹配尝试,参见“回溯后的动词”一节
即使模式是非锚定的,也不会进一步尝试通过前进起始点来查找匹配。如果(*COMMIT)是遇到的唯一回溯 predicate ,则一旦传递了它,pcre2_match()就会被提交以在当前起始点查找匹配,或者根本不查找匹配。
这并不意味着它不能找到多个匹配项,但当(*COMMIT)第一次失败时,它将停止搜索新的匹配项。这意味着,它不会丢弃先前成功尝试中已经找到的匹配项。
还有另一个回溯动词(*PRUNE),当回溯控制流从右向左通过它时,它也会失败整个匹配尝试。但与(*COMMIT)不同的是,它允许进一步的匹配尝试。我不理解文档中与(*COMMIT)的比较,但我用regex101测试了(*PRUNE),它也给出了很好的解释。
如果你需要更多的控制,关于新的匹配尝试不可以开始的主题字符,你可以使用(*SKIP)(*SKIP:)(*SKIP)类似于(*PRUNE),但额外要求每个新的匹配尝试从它的右边开始,也就是说,在(*SKIP)到达之前最后匹配的字符之后。可选名称可以引用另一个地方-由(*MARK:x 1 m20n1x注解-用于跳过新的匹配尝试。它将通过在字符串中后退(不再输入Assert或原子组)来搜索MARK,当没有找到合适的标记时,将根据文档忽略(*SKIP)
(*SKIP)就像修改最新的回溯点,使其指向一个新的位置。然而,在许多情况下,这不是一个功能性的增加,只是服务优化,这使得它在可读性方面值得怀疑。我想一个智能引擎,以推断这种“跳过”自动性能优化。

(*SKIP)的实用示例:
  • 主题字符串的语言:(abab|abac)*
  • 主题字符串内的所需匹配项:abab(但不与abac重叠)
  • PCRE 2溶液:aba(*SKIP)b

相关问题