regex - 带有反向引用的正则表达式属于乔姆斯基层次结构的什么地方(它们是否属于那里)？

Question

我在这里有点困惑 - 带有反向引用的 RegEx 显然不是正则表达式，因为它们可以，例如，用于描述复制语言('ww' 代表任何单词 w )，这是上下文相关的。然而与此同时，它们仍然不能用于描述像 HTML 这样的上下文无关语言(或者甚至只是匹配括号)——至少我不知道这样的东西在例如 HTML 中会是什么样子。 POSIX 正则表达式。

话虽这么说 - 这种“正则表达式”属于乔姆斯基层次结构中的任何地方，还是字里行间的某种科学怪人？

Answer 1

他们真的不合适。

带有反向引用的正则表达式可以匹配一些非上下文无关的语言(例如 (.*)\1)，但也不能匹配所有上下文无关的语言(典型的例子是嵌套的括号).

Here is a relevant post on the CSTheory StackExchange ，其中包含更多详细信息。

另请注意，某些实现(例如 .NET 或 Perl)比反向引用更进一步，并且可以匹配嵌套的括号。