检查给定的正则表达式是否匹配任何内容 [英] Check if a given regex will match anything

问题描述

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

Is it possible to check if a given regular expression will match any string? Specifically, I'm looking for a function matchesEverything($regex) that returns true iff $regex will match any string.

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

I suppose that this is equivalent to asking, "given a regex r, does there exist a string that doesn't match r?" and I don't think this is solvable without placing bounds on the set of "all strings". I.e., if I assume the strings will never contain "blahblah", then I can simply check if r matches "blahblah". But what if there are no such bounds? I'm wondering if this problem can be solved checking if the regex r is equivalent to .*.

推荐答案

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

This doesn't exactly answer your question, but hopefully explains a little why a simple answer is hard to come by:

首先，术语regex"有点模糊，所以为了澄清，我们有:

First, the term 'regex' is a bit murky, so just to clarify, we have:

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

• "Strict" regular expressions, which are equivalent to deterministic finite automatons (DFAs).
• Perl-compatible regular expressions (PCREs), which add a bunch of bells and whistles such as lookaheads, backreferences, etc. These are implemented in other languages too, such as Python and Java.
• Actual Perl regular expressions, which can get even more crazy, including arbitrary Perl code, via the ?{...} construct.

我认为这个问题对于严格的正则表达式是可以解决的.您只需构建相应的 DFA 并搜索该图以查看是否存在任何通往非接受状态的路径.但这对现实世界"正则表达式(通常是 PCRE)无济于事.

I think this problem is solvable for strict regular expressions. You just construct the corresponding DFA and search that graph to see if there's any path to a non-accept state. But that doesn't help for 'real world' regex, which is usually PCRE.

我不认为 PCRE 是图灵完备的(虽然我不知道 - 也请参阅这个问题:Perl 正则表达式是否图灵完整?).如果是这样，那么我认为正如 Jim Garrison 所说，这基本上就是停机问题.也就是说，将它们转换为 DFA 也不容易，使上述方法无用......

I don't think PCRE is Turing-complete (though I don't know - see this question, too: Are Perl regexes turing complete?). If it were, then I think as Jim Garrison commented, this is basically the halting problem. That said, it's not easy to transform them into a DFA, either, making the above method useless...

我没有关于 PCRE 的答案，但请注意，我想，上述结构(反向引用等)会使它变得非常困难.虽然我犹豫地说不可能".

I don't have an answer for PCREs, but be aware that the aforementioned constructs (backreferences, etc) would make it pretty hard, I imagine. Though I hesitate to say "impossible."

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

A genuine Perl regex with ?{...} in it is definitely Turing-complete, so there be dragons, and I think you're out of luck.

这篇关于检查给定的正则表达式是否匹配任何内容的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！