regex - 带有反向引用的正则表达式在 chomsky 层次结构中属于哪里（它们是否完全属于那里）？

Question

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

话虽这么说 - 这种“正则表达式”是否属于乔姆斯基层次结构中的任何地方，或者它们是否是某些令人厌恶的科学怪人？

Answer 1

他们真的不适合。

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

这是 CSTheory StackExchange 上的相关帖子，其中包含更多详细信息。

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