☰

正規表現を使用してネストされたパターンを一致させることはできますか? [重複] 質問する

tag-icon • tag-icon regex nested finite-automata
正規表現を使用してネストされたパターンを一致させることはできますか? [重複] 質問する

出現回数が不明なネストされたパターンに一致する正規表現を記述することは可能ですか? たとえば、外側の中括弧内にネストされた開き/閉じ括弧の数が不明な場合、正規表現は開き括弧と閉じ括弧に一致できますか?

例えば：

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

  // More { }
} // End

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

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

  // More { }
}

ベストアンサー1

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

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

Java用のANTLRなど、利用可能なパーサージェネレータは多数あります。Java（またはC）用の既存の文法を見つけることも難しくありません。
詳細については、Wikipediaのオートマトン理論を参照してください。

おすすめ記事