regex 有没有一种方法可以验证正则表达式最多只能使用一个字符?

balp4ylt  于 2023-08-08  发布在  其他
关注(0)|答案(2)|浏览(119)

这对Google来说是一件特别困难的事情,因为大多数问题都是关于如何编写正则表达式来匹配单个字符,这不是我的问题。
我的问题是:如果我有一个JavaScript / TypeScript API,它允许用户提供任何给定的正则表达式,但他们的正则表达式只能匹配0-1个字符,如果用户编写的正则表达式可以匹配多个字符,我将如何抛出错误?
举例来说:

/[a-z]/        // valid
/[a-z][A-Z]/   // invalid
/[a-z]{1}/     // valid
/[a-z]{2}/     // invalid
/[a-z]*/       // invalid
/[a-z]+/       // invalid

字符串
……等等
考虑指定正则表达式来匹配多个字符的所有方法可能会变得乏味。有什么想法可以实现这一目标吗?

4jb9z9bj

4jb9z9bj1#

不可能编写一个函数f(),它接受用户提供的任意JS regular expression,并准确地判断正则表达式是否可以匹配由多个字符组成的字符串。你写的任何函数要么有时会返回一个不正确的结果,要么你需要允许函数返回一个“我不知道”的结果。

有一些形式上的证明可以证明这一点,但我不打算在这里展示它们。相反,我将只指向On Lookaheads in Regular Expressions with Backreferences by Nariyoshi Chida and Tachio Terauchi,它显示了存在于JavaScript中的正则表达式类型的emptiness problem(包括backreferenceslookaheadlookbehind assertions)是undecidable。这意味着不可能编写一个函数来始终正确地判断输入JS正则表达式是否有任何匹配。
如果有一个神奇的函数f()来回答长度为2或更长的问题,那么你可以用它来构建空问题的答案,通过测试空字符串和每个长度为1的字符串(这很乏味,但理论上是可能的),并将结果与神奇的函数结合起来,得到空问题的完整解决方案。既然空性问题是不可判定的,那么你所描述的问题也是不可判定的。
因此,不能对任意JavaScript正则表达式执行此操作。
假设这太抽象了,假设用户提供了一个特定的(可怕的)正则表达式r,让我们研究一下我们是否可以编写一个函数f(),当且仅当r.test(s) === false对于所有s,其中s.length > 1,可以可靠地抛出错误。这就是怪物:

const r = /^x(?!x*(?<!^x(?:x?|\1+(xx+)))(?!(?:x?|(xx+?)\2+)$))($|xx(xx)+)$/

字符串
我声明r将匹配字符串s,当且仅当s满足以下所有条件:

  • 它只由字母"x"组成。即/^x*$/.test(s) === true,以及
  • 其长度是不等于3的奇数。即s.length % 2 == 1 && s.length !== 3,以及
  • 它的长度不能写成p+q+1,其中pq是素数。也就是说,假设您有一个函数primes(n),它返回一个由所有小于n的素数组成的数组,则primes(s.length).every(p => primes(s.length-p).every(q => s.length !== p+q+1))

我使用How to determine if a number is a prime with regex?中提到的正则表达式沿着lookaheads和lookbehinds构建了r。粗略地说,它说在字符串中没有一个点,它前面的字符数是一加一个质数(使用向后查找),它后面的字符数是一个质数(使用向前查找)。
我不知道这是否能让你相信我关于r的说法是正确的,但是如果你愿意的话,你可以测试它。让我们暂时假设它是。这意味着它接受输入"x",因为它的长度是1,而1不是两个素数的和:

console.log(r.test("x")); // true


到目前为止,这并没有使r无效,因为如果它接受像"x"这样的单字符串,它是可以的。
但是:是否有一个由两个或更多"x"字符组成的字符串,它 * 会 * 接受?f(r)是否会抛出错误?这就需要我们找到一个大于3的奇数,它不是两个素数之和。这意味着我们需要找到一个大于2的偶数,而不是两个素数的和。
换句话说:f(r)不应该抛出错误,当且仅当 * 每个大于2的偶数都等于两个素数的和 *。但这和Goldbach's conjecture是一样的,Goldbach's conjecture是一个著名的未解数学问题。数百年来,数学家们一直在试图确定这是真是假,而我们到2023年还没有弄清楚。我们认为这是正确的,我们知道如果有一个反例,它是非常大的,但它还没有被证明。

**这意味着函数f()需要能够证明或反驳哥德巴赫猜想才能正常工作。**这本身并不意味着它是不可能的,但它确实意味着 * 目前没有人知道如何做到这一点 *。

即使我关于r的行为的声明是不正确的,或者如果你想从技术上说,哥德巴赫猜想已经被证实了所有可能是JS字符串长度的数字,这仍然应该给予你认真思考,因为它希望证明一个人可以提出JS正则表达式,它根本不清楚它可能接受哪些字符串。
所以,你走吧。对于任意的JS正则表达式输入,这是不可能的,即使有可能,也是非常困难的。
如果你想将可能的输入限制为JS正则表达式的一个子集,比如禁止反向引用和查找,那么答案可能会改变。正则语言的空性问题是可判定的,您可能会使用该结果编写一个算法,用于长度为2或更长的字符串。但这将是一个不同的问题,超出了所提问题的范围。

最后,让我们退一步,看看你在做什么。如果您需要对JS正则表达式进行任何形式的验证,那么允许用户提供任意的JS正则表达式几乎肯定会带来更多的麻烦。
相反,您应该考虑接受一些更简单的数据结构,这些数据结构不会被误用(无论是有意还是无意)。根据您的用例,您可能会切换到只包含您想要接受的所有字符的字符串,或者一组对应于公共字符范围的枚举,等等。
正则表达式是出了名的棘手,正如famous aphorism所证明的那样:

有些人在遇到问题时会想:“我知道,我会用正则表达式。”现在他们有两个问题。

如果不使用正则表达式,问题的数量将减少一半。
Playground代码链接

pzfprimi

pzfprimi2#

你大概知道正则表达式将测试哪些数据吗?
如果是这样的话,您可以提供一个多字符的测试字符串,如果它允许这样做,那么您知道它不符合您的标准

[
  /[a-z]/,
  /[a-z][A-Z]/,
  /[a-z]{1}/,
  /[a-z]{2}/,
  /[a-z]*/,
  /[a-z]+/
]
.forEach(p => {
  const m = 'aa'.match(p);
  console.log(p, m !== null && m[0].length === 1);
});

字符串

相关问题