正規表現を使用してネストされたパターンを照合できますか?[重複]

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

質問

この質問にはすでに答えがあります:

未知の回数発生するネストされたパターンに一致する正規表現を作成することは可能ですか?たとえば、外側の中括弧内に未知の数の開き中括弧と右中括弧がネストされている場合、正規表現は開き中括弧と閉じ中括弧を一致させることができますか?

例えば：

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

  // More { }
} // End

一致する必要があります:

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

  // More { }
}
役に立ちましたか？

解決

いいえ。それはとても簡単です。有限オートマトン (正規表現の基礎となるデータ構造) は、その状態以外にはメモリを持たず、任意に深いネストを行う場合は、任意に大きなオートマトンが必要になりますが、これは、 有限の オートマトン。

ネストされた/ペアになった要素は固定の深さまで照合できますが、オートマトンは非常に大きくなるため、深さはメモリによってのみ制限されます。ただし、実際には、プッシュダウン オートマトン、つまり、LL (トップダウン) または LR (ボトムアップ) などの文脈自由文法のパーサーを使用する必要があります。実行時の動作の悪化を考慮する必要があります。O(n^3) vs.O(n)、n = 長さ(入力)。

利用可能なパーサー ジェネレーターは数多くあります。たとえば、 アントラー Javaの場合。Java (または C) の既存の文法を見つけることも難しくありません。
詳しい背景については: オートマトン理論 ウィキペディアで

他のヒント

正規表現を使用してネストされたパターンをチェックするのは非常に簡単です。

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

文字列が 1 行にある場合、おそらく Perl ソリューションは機能します。

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

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

HTH

編集： チェック：

そしてもう一つ、 トルステン・マレック (これはもう正規表現ではないということを正しく指摘したのは誰ですか):

はい、.NET RegEx エンジンの場合は可能です。.Net エンジンは、外部スタックで提供される有限ステート マシンをサポートします。見る 詳細

の 通常言語のポンピング補題 それができない理由です。

生成されたオートマトンには有限数の状態 (たとえば k) が含まれるため、k+1 個の左中括弧の文字列は、(オートマトンが文字を処理するときに) どこかで繰り返される状態を持つことになります。同じ状態間の文字列の部分は無限に何度でも複製でき、オートマトンは違いを知りません。

特に、k+1 個の開き中括弧とそれに続く k+1 個の閉じ中括弧を受け入れる場合 (これはそうすべきです)、ポンピングされた数の開き中括弧とそれに続く変更されていない k+1 個の閉じ中括弧も受け入れます (これは受け入れるべきではありません)。

正規言語の領域を離れてコンテキスト自由言語の領域に到達することになるため、適切な正規表現ではこれを行うことはできません。

それにもかかわらず、多くの言語が提供する「正規表現」パッケージは厳密にはより強力です。

例えば、 ルア 正規表現には「%b()" バランスの取れた括弧に一致する認識プログラム。あなたの場合、「」を使用します%b{}"

sed に似たもう 1 つの洗練されたツールは次のとおりです。 ジェマ, 、バランスの取れた中括弧を非常に簡単に一致させることができます。 {#}.

したがって、自由に使えるツールによっては、(広い意味での) 「正規表現」が入れ子の括弧に一致する可能性があります。

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;
}

はい

...ネストの最大数に上限があると想定します。

説明しましょう。

@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} = \{(?:[^{}])*\}

これらの正規表現を再帰的に生成するスクリプトを作成することもできますが、それはこれが必要な範囲を超えています。(これは読者のための演習として残されています。😉）

zsolt が述べたように、一部の正規表現エンジンは再帰をサポートしています。もちろん、これらは通常、バックトラッキング アルゴリズムを使用するものであるため、特に効率的ではありません。例： /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

いいえ、あなたは次の領域に入りつつあります。 文脈自由文法 その時点で。

これはうまくいくようです: /(\{(?:\{.*\}|[^\{])*\})/m

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top