アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

108

4

章 能力を高める

balanced =

/

\A #

文字列の先頭にマッチ

(?<brackets> # "brackets"

という部分式の開始

\( #

リテラル開き括弧にマッチ

\g<brackets>

*

#

ゼロ回以上の

"brackets"

部分式にマッチ

\) #

リテラル閉じ括弧にマッチ

) #

部分式の終了

*

#

パターン全体をゼロ回以上繰り返し

\z #

文字列の末尾にマッチ

/x

(?<brackets>...)

という部分式は

1

組の開き括弧と閉じ括弧にマッチしますが、括弧内ではその

任意の数の再帰的な出現にマッチできます。その結果、パターン全体

は任意の深さにネストした括弧

を正しく認識することができます。

>>

['(()', '())', '(())', '(()(()()))', '((((((((((()))))))))))'].grep(balanced)

=> ["(())", "(()(()()))", "((((((((((()))))))))))"]

こ れ が う ま く 動 作 す る の は、

Ruby

の 正 規 表 現 エ ン ジ ン が コ ー ル ス タ ッ ク を 使 っ て

(?<brackets>...)

の再帰的実行を記録しているためです。これは

DFA

や

NFA

にはできないことで

す。次のセクションでは、有限オートマトンにこうした追加の能力を与えるための拡張方法について

見ていきます。

それからもちろん、同じようにネストした

HTML

タグに適切に ...