未知の回数発生するネストされたパターンに一致する正規表現を書くことは可能ですか? たとえば、外側の中かっこ内に入れ子になっている開き/閉じ中かっこの数が不明な場合、正規表現は開き中かっこと閉じ中かっこを一致させることができますか?
例えば：
public MyMethod()
{
if (test)
{
// More { }
}
// More { }
} // End
一致する必要があります:
{
if (test)
{
// More { }
}
// More { }
}
いいえ、簡単です。有限オートマトン (正規表現の基礎となるデータ構造) には、その状態以外のメモリがありません。また、任意の深さのネストがある場合は、有限オートマトンの概念と衝突する任意の大きなオートマトンが必要です。
オートマトンが非常に大きくなるため、ネストされた/ペアになった要素を固定の深さまで一致させることができます。深さはメモリによってのみ制限されます。ただし、実際には、プッシュダウン オートマトン、つまり、LL (トップダウン) や LR (ボトムアップ) などの文脈自由文法のパーサーを使用する必要があります。悪いランタイム動作を考慮に入れる必要があります: O(n^3) 対 O(n)、n = length(input)。
Java用のANTLRなど、利用可能な多くのパーサー ジェネレーターがあります。Java (または C) の既存の文法を見つけることも難しくありません。
詳細な背景:ウィキペディアのオートマトン理論
正規表現を使用してネストされたパターンをチェックするのは非常に簡単です。
'/(\((?>[^()]+|(?1))*\))/'
文字列が1行にある場合、おそらくPerlソリューションが機能しています：
my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;
if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
print "Found: $1\n" ;
}
HTH
編集：チェック：
Torsten Marekによるもう 1 つのこと(正しく指摘していたのは、もはや正規表現ではないということです):
はい、.NET RegEx エンジンの場合。.Net エンジンは、外部スタックで提供される有限状態マシンをサポートします。詳細を見る
正規言語のポンピング補題が、それができない理由です。
生成されたオートマトンは k などの有限数の状態を持つため、k+1 個の左中括弧の文字列は、(オートマトンが文字を処理するときに) どこかで繰り返される状態を持つようにバインドされます。同じ状態の間の文字列の部分は無限に何度も複製でき、オートマトンは違いを知りません。
特に、k+1 個の左中括弧の後に k+1 個の右中括弧を受け入れる場合 (そうすべきです)、ポンプされた数の左中括弧の後に変更されていない k+1 個の右中括弧を受け入れます (これはすべきではありません)。
正規言語の領域を離れて文脈自由言語の領域に到達するため、適切な正規表現ではそれを行うことができません。
それにもかかわらず、多くの言語が提供する「正規表現」パッケージは、厳密に強力です。
たとえば、Luaの正規表現には、%b()バランスの取れた括弧に一致する""レコグナイザーがあります。あなたの場合、あなたは「%b{}」を使うでしょう
sedに似たもう1つの洗練されたツールは、 gemaです。このツールでは、バランスの取れた中括弧をと非常に簡単に一致させることができます{#}。
したがって、使用できるツールによっては、「正規表現」（広義には）がネストされた括弧と一致する場合があります。
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;
}
zsoltが述べたように、一部の正規表現エンジンは再帰をサポートしています。もちろん、これらは通常、バックトラッキングアルゴリズムを使用するものであるため、特に効率的ではありません. 例：/(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm
いいえ、その時点で文脈自由文法の領域に入ります。
これはうまくいくようです：/(\{(?:\{.*\}|[^\{])*\})/m