8

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

我想这相当于问，“给定一个正则表达式r，是否存在一个不匹配的字符串r？” 如果不对“所有字符串”设置界限，我认为这是无法解决的。即，如果我假设字符串永远不会包含“blahblah”，那么我可以简单地检查是否r匹配“blahblah”。但是如果没有这样的界限呢？我想知道这个问题是否可以通过检查正则表达式r是否等同于.*.

4

1 回答 1

13

这并不能完全回答你的问题，但希望能解释为什么一个简单的答案很难得到：

首先，“正则表达式”这个词有点模糊，所以为了澄清，我们有：

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

我认为这个问题对于严格的正则表达式是可以解决的。您只需构建相应的 DFA 并搜索该图以查看是否有任何路径可以到达不接受状态。但这对通常是 PCRE 的“现实世界”正则表达式没有帮助。

我不认为 PCRE 是图灵完备的（虽然我不知道 - 也请参阅这个问题：Perl regexes turing complete?）。如果是这样，那么我认为正如 Jim Garrison 评论的那样，这基本上是停止问题。也就是说，将它们转换为DFA也并不容易，使上述方法无用......

我对 PCRE 没有答案，但请注意，我想，上述构造（反向引用等）会使它变得非常困难。虽然我犹豫说“不可能”。

一个真正的 Perl 正则表达式?{...}绝对是图灵完备的，所以有龙，我认为你不走运。

于 2013-07-30T18:47:07.810 回答