正则表达式可以用于匹配嵌套模式吗？

是否可以编写与未出现次数的嵌套模式匹配的正则表达式？例如,当外括号内嵌有未知数量的打开/关闭括号时,正则表达式是否可以匹配开括号和右括号？

例如:

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

  // More { }
} // End

应该匹配:

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

  // More { }
}

Torsten Mare.. 257

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

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

有许多可用的解析器生成器,例如用于Java的ANTLR.查找Java(或C)的现有语法也并不困难.
更多背景:维基百科的自动机理论

1> Torsten Mare..：

---

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

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

有许多可用的解析器生成器,例如用于Java的ANTLR.查找Java(或C)的现有语法也并不困难.
更多背景:维基百科的自动机理论

---

就理论而言,托斯滕是正确的.在实践中,许多实现都有一些技巧,以允许您执行递归"正则表达式".例如,请参阅http://php.net/manual/en/regexp.reference.php中的"递归模式"一章.

---

语言理论中的正则表达式和实践中的正则表达式是不同的动物...因为_regular_表达式不能具有诸如反向引用,前向引用等的细节.

---

一个令人耳目一新的答案.最好的"为什么不"我见过.

---

我在自然语言处理方面的成长以及它所包含的自动机理论被宠坏了.

2> MichaelRusht..：

---

使用正则表达式检查嵌套模式非常简单.

'/(\((?>[^()]+|(?1))*\))/'

---

你能为正则表达式的每个部分添加一个解释吗？

---

我同意.但是,`(？> ...)`原子组语法(在PHP 5.2下)的一个问题是`？>`部分被解释为:"end-of-script"!我将如何编写它:`/ \((？:[^()] ++ |(？R))*+ \)/`.这对于匹配和非匹配都更有效.在它的最小形式,`/ \(([^()] |(？R))*\)/`,它真的是一个美丽的东西!

3> Zsolt Botyka..：

---

可能正在使用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

红宝石信息:http://www.ruby-forum.com/topic/112084

更多perl:http://www.perlmonks.org/？node_id = 660316

甚至更多perl:https://metacpan.org/pod/Text ::平衡

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

---

对.Perl的"正则表达式"不是(并且已经很长时间没有了).应该注意的是,递归正则表达式是Perl 5.10中的一个新特性,即使你可以做到这一点,你也许不应该在大多数常见的情况下(例如解析HTML).

4> 小智..：

---

是的,如果它是.NET RegEx引擎..Net引擎支持随外部堆栈提供的有限状态机.看细节

---

正如其他人所提到的,.NET不是唯一能够做到这一点的正则表达式引擎.

5> Rafał Dowgir..：

---

常规语言的Pumping引理是你不能这样做的原因.

生成的自动机将具有有限数量的状态,比如k,因此一串k + 1个开口括号必然会在某处重复一个状态(因为自动机处理字符).同一状态之间的字符串部分可以无限次复制,自动机不会知道差异.

特别是,如果它接受k + 1个开口支撑,接着是k + 1个闭合支撑(它应该),它还将接受泵送的开口支撑数量,接着是未改变的k + 1个闭合支撑(它不应该).

6> Remo.D..：

---

正确的正则表达式将无法执行此操作,因为您将使常规语言领域在Context Free Languages区域中着陆.

然而,许多语言提供的"正则表达式"包非常强大.

例如,Lua正则表达式具有%b()匹配平衡括号的" "识别器.在你的情况下你会使用" %b{}"

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

因此,根据您可以使用的工具,您的"正则表达式"(在更广泛的意义上)可能能够匹配嵌套的括号.

7> Pete B..：

---

在PHP正则表达式引擎中使用递归匹配比括号的程序匹配快得多.特别是长弦.

http://php.net/manual/en/regexp.reference.recursive.php

例如

$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';

preg_match_all( $patt, $str, $m );

与

matchBrackets( $str );

function matchBrackets ( $str, $offset = 0 ) {

    $matches = array();

    list( $opener, $closer ) = array( '(', ')' );

    // Return early if there's no match
    if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
        return $matches;
    }

    // Step through the string one character at a time storing offsets
    $paren_score = -1;
    $inside_paren = false;
    $match_start = 0;
    $offsets = array();

    for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
        $char = $str[ $index ];

        if ( $opener === $char ) {
            if ( ! $inside_paren ) {
                $paren_score = 1;
                $match_start = $index;
            }
            else {
                $paren_score++;
            }
            $inside_paren = true;
        }
        elseif ( $closer === $char ) {
            $paren_score--;
        }

        if ( 0 === $paren_score ) {
            $inside_paren = false;
            $paren_score = -1;
            $offsets[] = array( $match_start, $index + 1 );
        }
    }

    while ( $offset = array_shift( $offsets ) ) {

        list( $start, $finish ) = $offset;

        $match = substr( $str, $start, $finish - $start );
        $matches[] = $match;
    }

    return $matches;
}