正则表达式的正则表达式？

Question

可能重复： 是否有一个正则表达式来检测有效的正则表达式？ 寻找正则表达式的正则表达式？

我有一个允许用户输入正则表达式的应用程序。如何检查正则表达式的输入，并确保它们是有效的，因为如果没有正则表达式，就会出现preg_match错误。

我不想在preg_match之前使用“@”，所以如果有方法检查正则表达式的用户输入的有效性，那就太好了。

PHP的正则表达式系统似乎太复杂了，我无法为它们找到一个正则表达式。

Answer 1

如果发生错误，preg_match()返回FALSE。

1. 将表达式发送到服务器
2. 空字符串上的preg_match
3. 查看是否发生错误

您可以使用Ajax实时验证，也可以在表单提交之后进行验证。

您也可以尝试通过将表达式提供给javascript regexp引擎来验证，但是js regexp语法与php语法并不100%兼容。

Answer 2

从数学上讲，用正则表达式验证正则表达式是不可能的。这是因为(正式的)正则表达式只能识别正则语言。语言是任何一组字符串。例如，所有十进制数的集合都是一种语言(顺便说一下，它可以用正则表达式来描述)；所有有效的正则表达式集也是一种语言。常规语言是只需要固定的有限内存(而不是输入大小的函数)才能识别的语言。

包含所有有效正则表达式的语言不是正则语言，因此不可能使用正则表达式识别正则表达式。

要理解这一点，请注意正则表达式中包含必须匹配的括号。因此，如果"(“已发生，")”必须在以后发生。用一台只有固定有限内存的机器来描述这是不可能的。因为，如果有一种方法，并且您的正则表达式有有限的K个不同状态的内存(对于某些整数K)，一个表达式中有K个开括号和K个结束括号，尽管有效的正则表达式将无法被机器识别--这是一个矛盾(请注意，在正式语言中，我们的假设是文本处理一次从左到右发生一个字符，这与应用的正则表达式相同)。我们把描述正则表达式的语言称为上下文无关的语言，而不是正则的语言。

(证明正则表达式不是用抽头引理形成正则语言是很简单的)

因此，使用正则表达式识别正则表达式存在一个基本的计算机科学问题：--从数学上讲是不可能的。

规则语言可以被有限状态自动机识别，即有有限状态但没有记忆的机器。要解决问题，您需要添加一些依赖于输入大小的内存。正则表达式，因为它们是上下文无关的(幸运的是，它们不是某种模糊的、难以识别的语言类型)可以在线性时间使用下推自动机来识别。这是一个"for“循环，它一次遍历表达式一个标记(通常是一个字符)，并跟踪它在堆栈上看到的内容，即它以先到后出的方式”推送“数据。(将数据推入堆栈的示例：“我需要记住稍后找到匹配的`)‘！”；您可以根据需要“按”此选项多次；您可以在以后“弹出”它，当您需要检查之前是否确实需要匹配开括号时)。

当然，为正则表达式编写自己的识别引擎会带来一定的开销--但是如果您想要这样做，您应该知道上面的限制。使用一种已经存在的机制来完成它会更明智--我怀疑您可以将这项工作交给正则表达式库或一种更热衷于处理正则表达式(如Perl)的语言；但是@-方法听起来并不像一个想法的糟糕之处:它可能很慢，但您的用户可能无论如何都会输入非常慢的正则表达式；这可能是一种糟糕的实践，但在您的情况下，它似乎是最好的解决方案。

维基百科的一些相关文章：

• 语言
• 机器
• 理论
• 自动机
• 语言
• 语言
• 维基百科: LIFO

我希望这能帮上忙！

Answer 3

让用户提交正则表达式几乎肯定是个坏主意。

有些表达方式非常昂贵。试试这个：

preg_match('/(.*){1,32000}[bc]/','aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')

这只是30个字符的输入！它们也不是都是这样的:在PCRE中，/^(?:(\d+)|::)*$/也是指数时间。