这对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
字符串
……等等
考虑指定正则表达式来匹配多个字符的所有方法可能会变得乏味。有什么想法可以实现这一目标吗?
2条答案
按热度按时间4jb9z9bj1#
不可能编写一个函数
f()
,它接受用户提供的任意JS regular expression,并准确地判断正则表达式是否可以匹配由多个字符组成的字符串。你写的任何函数要么有时会返回一个不正确的结果,要么你需要允许函数返回一个“我不知道”的结果。有一些形式上的证明可以证明这一点,但我不打算在这里展示它们。相反,我将只指向On Lookaheads in Regular Expressions with Backreferences by Nariyoshi Chida and Tachio Terauchi,它显示了存在于JavaScript中的正则表达式类型的emptiness problem(包括backreferences和lookahead和lookbehind assertions)是undecidable。这意味着不可能编写一个函数来始终正确地判断输入JS正则表达式是否有任何匹配。
如果有一个神奇的函数
f()
来回答长度为2或更长的问题,那么你可以用它来构建空问题的答案,通过测试空字符串和每个长度为1的字符串(这很乏味,但理论上是可能的),并将结果与神奇的函数结合起来,得到空问题的完整解决方案。既然空性问题是不可判定的,那么你所描述的问题也是不可判定的。因此,不能对任意JavaScript正则表达式执行此操作。
假设这太抽象了,假设用户提供了一个特定的(可怕的)正则表达式
r
,让我们研究一下我们是否可以编写一个函数f()
,当且仅当r.test(s) === false
对于所有s
,其中s.length > 1
,可以可靠地抛出错误。这就是怪物:字符串
我声明
r
将匹配字符串s
,当且仅当s
满足以下所有条件:"x"
组成。即/^x*$/.test(s) === true
,以及s.length % 2 == 1 && s.length !== 3
,以及p+q+1
,其中p
和q
是素数。也就是说,假设您有一个函数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不是两个素数的和:型
到目前为止,这并没有使
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代码链接
pzfprimi2#
你大概知道正则表达式将测试哪些数据吗?
如果是这样的话,您可以提供一个多字符的测试字符串,如果它允许这样做,那么您知道它不符合您的标准
字符串