正規表現技術入門を読んだ

この本がTwitter上でたまに言及されているのを見て読んでみたいなと思っていたらちょうどタイミング良く例のDMMブックス70%オフクーポンが配布されたので購入して、すきま時間に読んでいたのがようやく読み終わった。

正規表現を支える理論と数理についての内容がメインの本で、自分の興味の方向性と良く合っていたので基本的に全編楽しみながら読めた。この本のおかげで正規言語、DFA、バックトラック、ポンピング補題、Myhill-Nerodeの定理、syntactic monoidに入門することができた。

数理的な内容とは別に実務的な面でも個人的にはそれまで使い方があまりよく理解できていなかった先読み/後読みに対する直観が得られたり、強欲な量指定子（possessive quantifier）を使うことでバックトラックを抑制できること（そして可能な場合は正規表現エンジンの最適化により自動強欲化が行われるのでプログラマ側が積極的に強欲な量指定子を使うよりは正規表現エンジンの最適化に任せたほうが良いこと）を知れたりと得るものが大きかった。

入門書なのである程度以上高度な証明は割愛されてしまっているのだけどそれでもAppendix 1のような簡単な証明を追うのは楽しい。計算機の理論の世界はやっぱり深淵で面白いな。