检查给定的正则表达式是否匹配任何内容

Question

是否可以检查给定的正则表达式是否匹配任何字符串？具体来说,我正在寻找一个matchesEverything($regex)返回true 的函数iff $regex将匹配任何字符串.

我想这相当于问,"给定正则表达式r,是否存在不匹配的字符串r？" 如果不在"所有字符串"的集合上放置边界,我认为这是不可解决的.即,如果我认为字符串永远不会包含"blahblah",那么我可以简单地检查是否r匹配"blahblah".但是,如果没有这样的界限怎么办？我想知道这个问题是否可以解决,检查正则表达式r是否相当于.*.

Answer 1

这并没有完全回答你的问题,但希望能够解释为什么很难得到一个简单的答案:

首先,"正则表达式"一词有点模糊,所以为了澄清,我们有:

• "严格"正则表达式,相当于确定性有限自动机(DFA).
• Perl兼容的正则表达式(PCRE),它添加了一堆钟声和口哨,如前瞻,反向引用等.这些也在其他语言中实现,如Python和Java.
• 实际的Perl正则表达式,可以通过?{...}构造变得更加疯狂,包括任意Perl代码.

我认为这个问题可以解决严格的正则表达式.您只需构造相应的DFA并搜索该图形,以查看是否存在任何非接受状态的路径.但这对"真实世界"正则表达式没有帮助,通常是PCRE.

我不认为PCRE是Turing-complete(虽然我不知道 - 也看到这个问题:Perl regexes图灵完成了吗？).如果是,那么我认为正如吉姆加里森评论的那样,这基本上就是停滞不前的问题.也就是说,将它们转换为DFA也不容易,使上述方法无用......

我没有PCRE的答案,但要注意上述构造(反向引用等)会让我觉得很难.虽然我犹豫说"不可能".

真正的Perl正则表达式?{...}肯定是Turing-complete,所以有龙,我认为你运气不好.