【書評】正規表現技術入門を読んで（マインドマップ付き）

正規表現技術入門を読んだ。読んでから結構時間が経ってしまった。マインドマップを書いたので、復習がてら、本稿へアップロードしておくことにする。マインドマップ全体をアップロードしようと試みたが、マインドマップが大きくて文字がつぶれてしまうことが分かった。仕方がないので、章ごとに画像で切り取ってアップロードすることにした。以降、簡単な注釈と、章ごとのマインドマップを記載する。

書いてあることをただまとめるのも微妙なので、自分が「こうではないか？」と思ったことも書いている。よって、本を読んでも書いていないようなことを書いてあるかもしれない。また、間違いも書いてあるかもしれない。そのあたりは認識のうえで読んでほしい。なお、間違いなどはコメントをもらえるとうれしい。

まずは第一章について、我々が正規表現として普段使っているものは、本来の意味でいう正規表現という言葉からすればオーバースペックになっているということがわかった。では一体何が、そのオーバースペックさをもたらしているのかというと、再帰や、後方参照である。これは第八章に詳しい。

第六章も切り取った画像に入ってしまったので、ついでにここでかくと、いろいろな文字列探索アルゴリズムについて書いてあった。例えば下記のURLが紹介されている。（様々な文字列探索アルゴリズムが掲載されていて、とてもよい）
ESMAJ

第三章も切り取った画像に入ってしまったので、ついでにここでかくと、正規表現を書くときはfalse positiveとfalse negativeを意識する必要があるということだった。false positiveが例えば、本来マッチしないはずのものにマッチしてしまうということだとすれば、false negativeは、マッチしてほしいものにマッチしないということである。

入力が限られているなら、false positiveを考慮すれば正規表現を簡潔に書ける場合も多い。もちろん脆弱性の話などもあるので、入力が限られていることを別の部分で担保する必要が場合によってはあるだろう。まあ、通常の設計において、脆弱性対策を正規表現の部分でやらないといけないケースというのは、そもそも何かがおかしい。通常のケースでは、false positiveを考慮した正規表現の簡潔化はできるだろう。

第二章では正規表現の歴史などに触れている。とにかく、kleeneがすごいやつだということはわかった。それで、通常正規表現というと、ERE（拡張正規表現）の方だが、BRE（標準正規表現）というのもあるということだ。

ここについでに書いてしまうと、Unixのシェル上などで指定するワイルドカードはGLOB(グロブ)と呼ばれるもので、正規表現とは異なるので、注意が必要だ。
wikipedia:ワイルドカード (情報処理)

第八章で、チョムスキー階層について触れているが、ここで、チョムスキーがすごいやつだということがわかる。チョムスキーといえば生成文法でおなじみだが、生成文法とは比較にならないくらい、この階層をまとめ上げたのはすごいのではないか（主観）。チョムスキー階層というのは、言語やオートマトンを四つの階層（type）に分ける。おおざっぱにいうとtypeが0に近づくほど、自由度が高くなる。type-0にはチューリングマシンが属する。

我々の自然言語は、おそらくtype-1の線形拘束オートマトン（文脈依存言語）におそらく一番近い。（弱文脈依存言語などといわれることもあるようである。つまり自然言語はtype-1.5的な存在として認識されているのだろう。）

type-2は、プッシュダウンオートマトンである。そして、type-3が決定性オートマトンで、正規言語はここに属する。

但し、上で書いたように再帰が使えると、正規言語の枠をもはや飛び出し、type-2のプッシュダウンオートマトンに昇格する。で、便宜的に、このtype-2へ昇格した正規言語（のようなもの）をDyck言語と呼んでいるということだ。

第四章では、ざっくりといえば、正規表現からNFA（非決定性オートマトン）を構成する方法。そして、NFAから、それと等価なDFA（決定性オートマトン）を構成する方法。そして、DFAから、それと等価な最小DFAを構成する方法が、それぞれ掲載されている。つまり、最終的には、正規表現から、それと等価な最小DFAを導くことができるという案内である。

また、Appendixでは、ある言語Lが正規表現であるかどうか判断するのに、ポンピング補題が紹介されている。

読んでいて、おもしろいが、非常に難しかった。ただ、手に負えないという感じではない。

第五章では、正規表現エンジンである鬼雲（鬼車から派生）について、詳細が記載されている。正規表現エンジンの実装には、大別して、DFA型とVM型があるが、鬼雲はVM型であるとのこと。

なお、この本で見て、鬼雲を高速化した人の話があるようだ。本を読んで、高速化可能な部分を指摘できるというのはすごい。
Onigmoを最大49%高速化した話 | κeenのHappy Hacκing Blog

第七章では、量指定子について、書かれていた。控えめな量指定子や、強欲な量指定子について、いろいろ記載されている。先読みも面白い機能だ。

ところで、正規表現のメタ文字はなかなか覚えられないのだが、以下のサイトにまとまっている。
正規表現 メタ文字一覧-正規表現サンプル集

あるいは以下には、説明もあって読みやすい。
手を動かしながら覚える正規表現＜リファレンス＞

先読みなどの機能については、以下のサイトに詳しい。
正規表現の先読み・後読みを極める！ - あらびき日記

先読みは、^や$と同様にアンカーだと考えるのが、理解しやすい。

読んでから随分経ってからこれを書いたので、詳細については結構忘れている部分が多かった。ただ、一度読んだ本であれば、「そういえば、これに関してはあの本に書いてあったかな？」というのができるので、悪くはない。ただ、一度読んだからわかったつもりになっている部分も多い。これについては気を付ける必要がある。