可以使用正则表达式来匹配嵌套模式吗？ [复制]

是否可以编写一个正则表达式来匹配出现次数未知的嵌套模式？例如，当外大括号内嵌套未知数量的左大括号时，正则表达式是否可以匹配左大括号和右大括号？

例如：

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

  // More { }
} // End

应匹配：

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

  // More { }
}

不，就这么简单。有限自动机（正则表达式底层的数据结构）除了其所处的状态之外没有内存，如果您有任意深度的嵌套，则需要一个任意大的自动机，这与finite自动机。

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

有许多可用的解析器生成器，例如ANTLR http://www.antlr.org/对于Java。找到 Java（或 C）的现有语法也不难。
了解更多背景：自动机理论 http://en.wikipedia.org/wiki/Automata_theory在维基百科