なぜか突然正規表現について復習メモ
正規表現というのは文字列を検索する時に使われるものだ。例えばSq から始まる単語を検索しようと思った場合、"Sq.*" のようにすると Squeak でもSquare でも引っかかる。探したい単語がきっちり決まっていない場合、コンパクトに検索条件を書けてとても便利だ。しかし Squeak には備わっていない。正規表現は UNIX 文化から来た割とマニアックな機構なので、たまたま無いだけなのか、それとも思想的な問題があるのかはしらないけど、正規表現とは何かという事から考える。
正規表現の特徴は二つ挙げられるだろう。一つは見た目の問題。冗長さを廃した、極めて短い文法を使う。例えばドット.は「改行以外すべての文字」とか、コメ*なら「文字列が続く可能性がある」とか。もう一つの特徴は、有限状態遷移機械(長いので FSM)であると言う事。これは、例えば、文字 S を探すとき、エス、エス、と S の事ばかり考えるわけだが、逆にいうと他の事は一切考えないのだ。例えば水溜りを飛び越えるときに「どっこいしょ」なんていうと、それからはエスの事はすっかり忘れてしまう。こういうのを FSM という。正規表現の本質的な「分かりやすさ」は、実はあの奇妙な文法ではなく、FSM であるという特徴から来ると私は思う。
これは、こういった話題に良く出る片方の雄であるパーサと比較すれば分かる。パーサとは、プログラミング言語の解釈に使われるもので、文脈自由文法(BNF)というまた別の理屈を使う。簡単に言うと、FSM が一度に一つの事しか覚えられないのに比べて、BNF ではスタックという領域に今覚えている事を保存する事が出来るので、水溜りを飛び越えた後でもエスに戻ってさっきの仕事の続きをする事が出来る。例えば、プログラミング言語における括弧の対応をチェックするのにこの仕組みは必須だ。
たかがこれだけの違いなのに、人間は馬鹿なので、正規表現に比べてパーサを書くのはひどくしんどい。だからパーサさえあれば正規表現は要らないと考えるのは違う。まあ、あの記号だらけの文法でよいかは別の話だが。なんでこんな事を書き始めたかというと、Squeak で正規表現をやるならストリームを駆使したもっとスマートなやり方があるのではと思ったのだが、思いつかなかったので思ったという事だけ書きました。
ちなみに、拡張正規表現では前方参照という事が出来て、要するに記憶場所が複数あるので純粋な FSM では無い。また、ちなみついでにプログラミング言語自体は文脈依存言語、つまり、変数を使う前に定義しないといけないとか、文脈に依存した決まりがあるので、実は BNF では表現できない。文脈依存の文法を処理する為にはチューリングマシン。すなわちプログラムその物が必要になっしまうので、仕方なしにパーサでは BNF である程度処理するという妥協をしている。しかしこの、文法の種類と計算機理論が交わる所は感動すべき所ですよお兄さん。
日本語の本が無いので間違ってるかも知れません。また、FSM と BNF は対義語では無いですが、BNF を「何たら機械」と呼ぶ言葉を忘れたので仕方なしに書いてます。
