regex - 匹配正则表达式的正则表达式

Question

有没有人尝试过描述匹配正则表达式的正则表达式？

由于关键字重复，这个主题几乎不可能在网络上找到。

它可能在现实世界的应用程序中无法使用，因为支持正则表达式的语言通常具有解析它们的方法，我们可以将其用于验证，以及一种在代码中分隔正则表达式的方法，可用于搜索目的.

但我仍然想知道匹配所有正则表达式的正则表达式会是什么样子。应该可以写一个。

Answer 1

我对此没有正式的证据，但我强烈怀疑正则表达式的语言本身不是正则的，因此不受正则表达式的约束¹。这将使适当的正则表达式无法表示它。

为什么？好吧，可以证明需要平衡括号的语言，例如 Lisp(或，more famously，HTML)is not regular using the pumping lemma :

The proof that the language of balanced (i.e., properly nested) parentheses is not regular follows the same idea. Given p, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will consist entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

正则表达式 permit nested capture groups ，这似乎属于这一类:

Take the example from the previous lesson, if we wanted to capture the image file number along with the filename, I can write the expression ^(IMG(\d+))\.png$.

无论如何，这对于 the Computer Science Stack Exchange site 来说可能是一个更好的问题。 .

编辑:

¹tomp 指出基于 PCRE 的正则表达式引擎(以及其他可能的引擎) are actually able to match all context-free grammars and at least some context-sensitive grammars !这代表了表达能力的巨大差异。假设文章是正确的，很酷!

(当然，这些扩展实现是否仍然是“正则表达式”还有待讨论。由于我们在编程站点上，我将采取它们的立场。在 CS 站点上，我可能会采取相反的立场! )

因此，在技术上可以将正则表达式表示为正则表达式。

即便如此，编写代表所有正则表达式的正则表达式的任务非常复杂。考虑比较验证电子邮件地址的任务。许多资源将其归结为类似于 [^@]+@[^@]+ 的内容。 ，或“只要符号中只有一个并且至少有一个前后一个字符，我们就很好”。

但是看看这个显然 complete regex to validate RFC 822 .这是正确的吗？谁知道。我当然不会检查它。

看到这一点后，我不想尝试编写正则表达式来验证正则表达式。