<分区>
Possible Duplicate:
Is there a regular expression to detect a valid regular expression?
Regular expression for finding a regular expression?
我有一个允许用户输入正则表达式的应用程序。我如何检查正则表达式的任何输入并确保它们是有效的，因为如果它们不存在就会出现 preg_match 错误？
我不想在 preg_match 之前使用“@”，所以如果有一种方法可以检查用户输入的正则表达式的有效性，那就太好了。
PHP的正则表达式系统似乎太复杂了，我无法为他们想出一个正则表达式。
最佳答案
从数学上讲，不可能使用正则表达式来验证正则表达式。这是因为(正式的)正则表达式只能识别常规语言。语言是字符串的任意集。例如，所有十进制数字的集合是一种语言(顺便说一句，可以使用正则表达式来描述)；所有有效正则表达式的集合也是一种语言。 常规语言是只需要固定的有限内存(不是输入大小的函数)即可被识别的语言。
包含所有有效正则表达式的语言不是正则语言；因此不可能使用正则表达式来识别正则表达式。
要理解这一点，请注意正则表达式中包含必须匹配的括号。因此，如果出现了“(”，则稍后必须出现“)”。这是不可能用只有固定有限内存的机器来描述的。因为，如果有一种方法可以做到这一点，并且您的正则表达式对K 不同状态(对于某个整数 K)有有限的内存，则表达式有 K 个左括号后跟 K 右括号，尽管有效的正则表达式无法被该机器识别——一个矛盾(注意在形式语言中，我们的假设是文本处理一次一个字符，从左到右，这与应用的正则表达式相同)。我们称描述正则表达式的语言为上下文无关而非常规。
(使用 Pumping Lemma 证明正则表达式不构成正则语言是微不足道的)
因此，在使用正则表达式识别正则表达式时存在一个基本的计算机科学问题:这样做在数学上是不可能的。
有限状态自动机可以识别常规语言，即具有有限状态但没有内存的机器。为了解决您的问题，您需要添加一些取决于输入大小的内存。正则表达式，因为它们是上下文无关的(幸运的是它们不是一些晦涩难懂的语言类型)可以使用下推自动机在线性时间内识别。这是一个“for”循环，一次通过一个标记(通常是一个字符)的表达式，并跟踪它在堆栈上看到的内容，即它“推送”它稍后的数据“pops”以先进后出的方式。 (压入堆栈的数据示例:“我需要记住稍后找到匹配的 `)'!”；您可以根据需要多次“推送”它；您可以稍后“弹出”它，当您需要检查您是否确实需要之前匹配左括号时)。
当然，为正则表达式编写您自己的识别引擎会有点开销——但如果您想这样做，您应该了解上述限制。更明智的做法是采用现有的机制来完成这项工作——我怀疑您可以将这项工作交给正则表达式库或更热衷于处理正则表达式的语言，例如 Perl；但是 @-method 听起来并不是一个太糟糕的想法:它可能很慢，但是您的用户无论如何都可能输入非常慢的正则表达式；这可能是一种不好的做法，但在您的情况下，这似乎是可用的最佳解决方案。
维基百科中的一些相关文章:
希望对您有所帮助!
关于php - 正则表达式的正则表达式？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2789407/