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

Can regular expressions be used to match nested patterns? [duplicate]

提问人:Richard Dorman 提问时间:9/25/2008 最后编辑:codeforesterRichard Dorman 更新时间:3/29/2018 访问量:146727

问:

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

例如:

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

  // More { }
} // End

应匹配:

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

  // More { }
}
正则表达式 嵌套 有限自动机

评论

29赞 ridgerunner 3/15/2011
要明确回答这个问题,首先需要定义术语:“正则表达式”。
6赞 Cœur 8/5/2015
从书中可以看出,正则表达式不能做到这一点,但上下文无关的表达式可以。从这些工具中,现代表达式解析器将调用使用外部堆栈的东西,这意味着能够回溯,意味着能够递归:这些都是在实践中,因此您可以使用 simili-PCRE2(PHP、Java、.NET、Perl 等)或符合 ICU 的 (Obj-C/Swift) 工具作为单行工具来完成,通常使用语法或替代语法,例如 或语法。regular expressioncontext-free expressions(?>...)(?R)(?0)

答:

3赞 Craig H 9/25/2008 #1

不,那时您正在进入上下文自由语法的领域。

281赞 Torsten Marek 9/25/2008 #2

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

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

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

评论

65赞 daremon 9/25/2008
就理论而言,托尔斯滕是正确的。在实践中,许多实现都有一些技巧,以便允许您执行递归的“正则表达式”。例如,请参阅 php.net/manual/en/regexp.reference.php 中的“递归模式”一章
2赞 Torsten Marek 9/25/2008
我被我在自然语言处理方面的成长经历和它所包含的自动机理论宠坏了。
7赞 Ben Doom 9/26/2008
一个令人耳目一新的清晰答案。我见过的最好的“为什么不”。
15赞 Novikov 10/5/2010
语言理论中的正则表达式和实践中的正则表达式是不同的野兽......由于正则表达式不能有反向引用、向引用等细节。
1赞 Andy Baker 8/13/2016
@TorstenMarek - 你能确认这仍然是真的吗?其他消息来源指出,如果正则表达式引擎支持反向引用等功能,它就会成为 2 类语法(与上下文无关)而不是 3 类(常规语法)。因此,例如,PCRE 能够处理嵌套结构。这种混淆来自于这样一个事实,即现实世界中的“正则表达式”在技术意义上不再是规则的。如果这是正确的,那么更新这个答案会很棒。
33赞 Zsolt Botykai 9/25/2008 #3

如果字符串在一行上,则可能有效的 Perl 解决方案:

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

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

IT)

编辑:检查:

Torsten Marek 还有一件事(他正确地指出,它不再是正则表达式):

评论

9赞 Michael Carman 9/25/2008
是的。Perl 的“正则表达式”不是(而且已经很久没有了)。应该注意的是,递归正则表达式是 Perl 5.10 中的一个新特性,即使你可以这样做,但在大多数情况下,你可能不应该这样做(例如解析 HTML)。
1赞 Brad Gilbert 10/17/2008
perldoc.perl.org/perlretut.html
20赞 Rafał Dowgird 9/25/2008 #4

常规语言的抽水引理是你不能这样做的原因。

生成的自动机将具有有限数量的状态,例如 k,因此一串 k+1 左大括号必然会在某处重复一个状态(当自动机处理字符时)。同一状态之间的字符串部分可以无限多次复制,自动机不会知道其中的区别。

特别是,如果它接受 k+1 个左大括号,然后是 k+1 个右大括号(它应该接受),它也将接受泵送数量的左大括号,然后是不变的 k+1 右大括号(它不应该)。

14赞 Remo.D 9/25/2008 #5

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

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

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

另一个类似于 sed 的复杂工具是 gema,您可以在其中非常轻松地匹配平衡的大括号。{#}

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

3赞 sirnotappearingonthissite 9/25/2008 #6

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

19赞 Pavlush 12/5/2008 #7

是的,如果它是 .NET 正则表达式引擎。.Net 引擎支持外部堆栈提供的有限状态机。查看详情

评论

12赞 Ben S 3/15/2010
正如其他人所提到的,.NET 并不是唯一能够做到这一点的正则表达式引擎。
0赞 Sean Huber 4/2/2010 #8

这似乎有效:/(\{(?:\{.*\}|[^\{])*\})/m

评论

2赞 Stijn Sanders 1/2/2014
它似乎也匹配它不应该匹配{{}
48赞 Michael 10/4/2010 #9

使用正则表达式检查嵌套模式非常容易。

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

评论

4赞 ridgerunner 3/12/2011
我同意。然而,原子组语法(在 PHP 5.2 下)的一个问题是该部分被解释为:“脚本结束”!我是这样写的:.这对于匹配和非匹配都更有效。就其最小的形式而言,它确实是一件美丽的事情!(?>...)?>/\((?:[^()]++|(?R))*+\)//\(([^()]|(?R))*\)/
1赞 Michael 3/19/2011
双+?我曾经允许评论出现在其他文本中(我把它从我的电子邮件地址正则表达式中撕下来并简化了它)。之所以被使用,是因为我相信它会使它更快地失败(如果需要)。这不对吗?(?1)(?>
17赞 EricP 1/16/2015
你能为正则表达式的每个部分添加一个解释吗?
0赞 Cœur 10/13/2015
对于字符串,使用简单表达式会得到相同的结果。你的长篇大论有什么好处吗?'(a (b c)) (d e)''/\([^()]*\)/'
0赞 Michael 10/13/2015
尝试使用 和 匹配 。前者匹配,但后者不匹配。/^(\((?>[^()]+|(?1))*\))+$//^\([^()]*\)+$/(a (b c))(d e)
5赞 Pete B 9/17/2012 #10

在 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;
}
11赞 awwsmm 3/28/2018 #11

是的

...假设有一些最大数量的嵌套,你会很乐意停下来。

让我解释一下。


@torsten-marek 说得对,正则表达式无法检查这样的嵌套模式,但是可以定义一个嵌套的正则表达式模式,这将允许您捕获这样的嵌套结构,直到某个最大深度。我创建了一个来捕获 EBNF 风格的评论(在这里尝试),例如:

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

正则表达式(用于单深度注释)如下:

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

这可以很容易地适应你的目的,用和替换和,并用简单的替换中间的所有内容:\(+\*+\*+\)+{}[^{}]

p{1} = \{(?:[^{}])*\}

(这是尝试一下的链接。

要嵌套,只需在块本身中允许此模式:

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

要查找三重嵌套块,请使用:

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

一个清晰的模式已经出现。要查找嵌套深度为 的注释,只需使用正则表达式:N

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

可以编写一个脚本来递归生成这些正则表达式,但这超出了我需要它的范围。(这是留给读者的练习。 😉

评论

0赞 7/12/2021
Java 版练习:完美,谢谢。PCRE/2 更优雅:但这在 Java 中是行不通的。String getNestedBraceRegex(int n) {if(n == 1) return "\\{(?:[^{}])*\\}"; else return "\\{(?:(?:" + getNestedBraceRegex(n-1) + ")|(?:[^{}]))*\\}";}(\{((?>[^{}]+|(?1))*)\})