正規表現は便利な技法です。一行ほどの短い文字列で様々な文字列を表現できます。一行で動作させる単純な動作のためか実装されている正規表現の多くは後方参照以外の参照可能な記憶領域を持ちません。入れ子構造を正規表現で表そうとした場合、この記憶領域が無いという仕様が大きくのしかかってきます。
単純に()の入れ子を考えてみます。
(()(()))人間が見やすいようにインデントを付けます。
(
()
(
()
)
)
入れ子が正しく結ばれているか、どの始点がどの終点に対応しているかを考えるためには記憶領域が必要になります。
正しく結ばれているかは、次のルールを守ったまま文字列の終わりまで読み取り切れるか否かで確認できます。
・終点を読み込んだ時、対応する始点が存在する
・読み取り終わった時、今まで読み取った始点、終点の数が等しい
最新以外の始点についての情報が無い場合、対応する始点が存在するか否かがわからず、入れ子の確認ができません。正規表現は後方参照以外に記憶領域を持ちません。このため多くの正規表現は入れ子構造を読み取ることができません。余談ですがデータ構造のひとつであるスタック構造を用いると簡単に入れ子を読み取ることが出来ます。下図はスタック構造のgifです。始点を積み、終点を読んだら始点を一つ取り出す、という動作を繰り返すことで実装できます。
正規表現には方言がある、と言われるほど、実装が多種多様で様々な拡張がなされています。perlやphpの様なプログラミング言語の一部では正規表現の再帰呼び出しが実装されています。再帰は自身の処理中に自身を呼び出すことが可能な動作です。これで始点を積み上げ、終点で始点を打ち消す、というスタック処理をそのままできます。
再帰を用いた正規表現の説明書：PHP: 再帰的パターン – Manual
