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

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

例如:

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

  // More { }
} // End

应该匹配:

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

  // More { }
}

当前回答

可能是Perl解决方案，如果字符串在一行上:

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

HTH

编辑:检查:

http://dev.perl.org/perl6/rfc/145.html Ruby信息:http://www.ruby-forum.com/topic/112084 更多perl: http://www.perlmonks.org/?node_id=660316 甚至更多perl: https://metacpan.org/pod/Text::Balanced Perl, Perl, Perl: http://perl.plover.com/yak/regex/samples/slide083.html

Torsten Marek(他已经正确地指出，它不再是一个正则表达式)的另一个观点是:

http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

2008-09-25 14:40:25

其他回答

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

2010-04-01 20:39:10

是的，如果它是。net RegEx-engine. net引擎支持有限状态机提供一个外部堆栈。看到细节

2008-12-05 06:35:28

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

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

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

2008-09-25 14:27:12

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

2008-09-25 14:19:02