[解決済み】正規表現でネストしたパターンにマッチさせることは可能か？重複

質問

未知数の回数発生するネストしたパターンにマッチする正規表現を書くことは可能でしょうか？例えば、外側の中括弧の中に未知の数の開閉中括弧が入れ子になっているとき、正規表現は開閉中括弧にマッチすることができますか？

例えば

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

  // More { }
} // End

マッチするはずです。

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

  // More { }
}

解決方法は？

いいえ、そんな簡単なことです。有限オートマトン（正規表現の基礎となるデータ構造）は、その状態とは別にメモリを持ちません。 有限 オートマトン

入れ子や対になった要素を一定の深さまでマッチングすることができます。オートマトンは非常に大きくなるので、深さはあなたのメモリによってのみ制限されます。しかし、実際には、プッシュダウン・オートマトン、つまり文脈自由文法のパーサー、例えばLL（トップダウン）やLR（ボトムアップ）を使うべきでしょう。その際、実行時の動作が悪くなることを考慮しなければならない。O(n^3) vs O(n), ただしn = length(input)とする。

多くのパーサジェネレータが利用可能で、例えば ANTLR を使用します。また、Java（またはC）用の既存の文法を見つけることも難しくはない。

詳しい背景はこちら。 オートマトン理論 ウィキペディアにて