正则表达式可以用来匹配嵌套模式吗?

是否有可能编写一个正则表达式来匹配出现未知次数的嵌套模式?例如，当在外花括号内嵌套了未知数量的开/闭花括号时，正则表达式是否可以匹配开/闭花括号?

例如:

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

应该匹配:

{
  if (test)
  {
    // More { }
  }

  // More { }
}

当前回答

/(\{(?:\{.*\}|[^\{])*\})/m

其他回答

正如zsolt提到的，一些正则表达式引擎支持递归——当然，这些引擎通常使用回溯算法，所以它不是特别有效。例子 : /(?>[^{}]*){(?>[^{}]*)(? R )*(?>[^{}]*)}/ sm

常规语言的泵浦引理是您不能这样做的原因。

生成的自动机将有有限数量的状态，比如k，所以一个由k+1个开括号组成的字符串必然在某个地方有一个重复的状态(当自动机处理字符时)。相同状态之间的字符串部分可以复制无限次，自动机不会知道其中的区别。

特别是，如果它接受k+1个开大括号，后面跟着k+1个闭大括号(它应该)，它也会接受泵送的开大括号数量，后面跟着不变的k+1个闭大括号(它不应该)。

正确的正则表达式将无法做到这一点，因为您将离开常规语言领域，进入上下文自由语言领域。

然而，严格来说，许多语言提供的“正则表达式”包更强大。

例如，Lua正则表达式有“%b()”识别器，它将匹配平衡圆括号。在你的例子中，你可以使用"%b{}"

另一个类似于sed的复杂工具是gema，您可以很容易地用{#}匹配平衡的花括号。

因此，根据您拥有的工具，您的“正则表达式”(在更广泛的意义上)可能能够匹配嵌套括号。

不，你在这一点上进入了上下文自由语法的领域。

不。就是这么简单。一个有限自动机(它是正则表达式下面的数据结构)除了它所处的状态外没有内存，如果你有任意深的嵌套，你需要一个任意大的自动机，这与有限自动机的概念相冲突。

您可以将嵌套/配对的元素匹配到固定的深度，其中深度仅受内存的限制，因为自动机会变得非常大。然而，在实践中，您应该使用下推自动机，即用于上下文无关语法的解析器，例如LL(自上而下)或LR(自下而上)。您必须考虑到较差的运行时行为:O(n^3) vs. O(n)， n = length(输入)。

有许多可用的解析器生成器，例如Java的ANTLR。为Java(或C)找到一个现有的语法也不难。更多背景知识:维基百科的自动机理论

推荐文章