regex - 可以使用正则表达式来匹配嵌套模式吗？

Question

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

例如:

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

  // More { }
} // End

应该匹配:

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

  // More { }
}

Answer 1

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

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

有许多可用的解析器生成器，例如 ANTLR对于Java。查找 Java(或 C)的现有语法也不难。
了解更多背景:Automata Theory在维基百科