読みました。
勉強になりました（小並感
正規表現の入門書というより、正規表現エンジンの実装のための入門書。
正規表現エンジンを書きたいと思っているけどどうすればいいのか分からない、っていう人におすすめ。
一部のページは、Software Design 2013年5月号の正規表現特集に掲載された新屋氏自身の記事(sd_engine.pdf)がベースになっているっぽいです。
第2章
歴史が面白い。
Ken Thompson すごい。
Kleene はクリーネと読むのでしょうか。
p64
「合計が閾値θ(ノード内部)を超えると」は「θ以上」と書くべきではないか気になりましたが、ニューロン業界だとそういう表現をするらしい？
p75
『以降、本書では「POSIXの正規表現」と言えば「ERE」を指す』とあるので心して読み進めましたが、p246とp253でしか言われてない上にどちらもどの仕様かは関係ない意味合いで使われてました。
第3章
p99
TRE はこれでしょうか。
TRE — The free and portable approximate regex matching library.
p105
妥協するという選択肢っていいですね。
メールアドレスの正規表現はもう HTML5 方式だけでいいでしょ。
第4章
p127
「ε遷移の除去」という見出しですがε遷移のやり方を説明しつつ、中盤の「しかし、実はどんなε-NFAでもε遷移を取り除くことができます。……」という段落だけは除去の話をしているのでちょっと分かりにくかったです。
p131
しかし、現代の正規表現エンジンで有限オートマトンベースのマッチングをするもので、
NFA だけを用いるエンジンはほとんどありません。
NFA ベースのマッチングを実装しているエンジンは同時に DFA ベースのマッチングにも
対応しているのです。そのため、本書では有限オートマトンベースのマッチングを用いる
正規表現エンジンを DFA 型の正規表現エンジンと呼んでいます。
これはつまり
- DFA に変換せず NFA のまま直接処理するエンジン(ごく少数)
- NFA を DFA に変換して処理するエンジン
- NFA のまま処理するコードと、NFA を DFA に変換して処理するコードを併せ持つエンジン
を DFA 型と呼んでいるということなのでしょうか。
NFA を DFA に変換して処理するという定義に限定すべきでは。
第4章は
- 分岐のない NFA の説明とコード
- ε-NFA の説明とコード
- 部分集合構成法の説明とコード
- DFA の説明とコード
というような順番で説明して欲しかったです。
第5章
p163,173
後方参照に使われるキャプチャにバックトラックが必要なのはなぜ？
いつか鬼雲のソースを読もう。
第6章
p221
固定文字列検索の分野も面白そう。
第7章
p241
(\D+|<\d+>)*[!?] と
(\D++|<\d+>)*[!?] が同じというのが分かりません。
手元で試しても違うように見えます。
p249
固定文字列検索でもオーバーラップしないという仕様はありえるし、正規表現にかぎらず文字列検索一般に該当する問題で、ただ正規表現の場合はオーバーラップしない仕様でも先読みを使えばオーバーラップさせられる、ということでは。
正規表現でもオーバーラップするものとしては、Mery 2.2.2.4953 | Haijin Boys Online とか Perl6 の overlap とか。
p257
可変長後読みはどこからマッチを開始するのかどうやって決めるのか、パターンを逆向きに構築して一文字ずつ後ろ向きにマッチしていく手法はどうか？とか、いろいろと大変だと昔なにかで見た気がします。
p257
空文字列の繰り返しをVM型エンジンでマッチしようとすると、無限ループになりいずれスタック溢れで止まると思うのですが、そういう問題ではないのでしょうか。
他の章で触れられてはいますがそちらでは最適化の一手としての説明ですし。
JavaScript のこの挙動は、
ECMA-262 Edition 5.1 15.10.2.5 Term
NOTE 4 Step 1 of the RepeatMatcher's d closure states that, once the minimum number of repetitions has been satisfied, any more expansions of Atom that match the empty String are not considered for further repetitions. This prevents the regular expression engine from falling into an infinite loop on patterns such as:
によるものだと思いますが、空文字列にマッチするかどうかは実際にマッチを試して成功してからでないと分からないのに「0回のマッチ(1回もマッチしていない)」として扱われるのが謎。
第8章
p264
VerbalExpressions より Regexp::Assemble を紹介した方がよかったかも。
Appendix
この本のメインディッシュ。
第1～8章のいろいろなところで「○○については Appendix で」という案内が書かれていたりします(各節冒頭のあらすじを除いても14か所くらい)。
もちろん第1～8章だけでも役に立ちます。
・組版的なところ
スペースを網掛け＋ルビで表記しているのは分かりやすいです。
第1章以外で正規表現が等幅フォントになっていないのは構わないけど、* が上付きになっているのは注釈記号に見えて紛らわしいので、それだけはなんとかして欲しかった。
図が多くて分かりやすいです。
ただ、この本に限らない一般的な作法ではありますが、図をページの一番下、紙面に余裕がない場合は次ページの一番下に落としてあるのが、本文と図が離れすぎて読みづらいです。正直廃れて欲しい風習……。
スクリーンショットに書き込まれているコメントが、背景色とほとんど同じ色で見づらいです。
ノンブルが文字ごとに上端下端が違うフォントなので、ページをパラパラとめくった時に数字が上下に動いているようで見づらいです。
・以下些細な点。
p43 - 下の方のコードはスクリーンショットなので黒地に白抜きでは。
p64 図2.1 -
(3) 1=x1&x2 は v=(略) では。
(4) v=￢x1 字が小さくて見えづらいけどマイナスじゃなくて否定記号であってる？
p109 図3.4 - このように塗ったほうがよかったのでは。
p113 - 正規表現が 0*(10*10*)*` と書いてあるように見えるけど、自分の本の印刷の汚れ？
p175 リスト5.16 - 2354行のコメントが薄字になっていない。
p194 -・(?(condition)yes|no)、(?(condition)yes)条件式
見出しレベルが違うのと、説明がよく分からない。
p204 図5.21 - a*+a のバイトコード
p217 図6.5 - #1 と #0 を繋ぐ線が矢印になっていない。
p235 - スクリーンショット 6、7行目の正規表現に ^ $ がない。
p242 - 一番上のスクリーンショット 3行目の正規表現に ^ $ がある。
p243 - スクリーンショット 3行目の正規表現に ^ $ がある。1、3行目が [!] になっている。
p265 リスト8.3 - 16行目のコメントが薄字になっていない。
p274 リスト8.6 - 「ですし」がおかしいのと、「数式」が別の意味で二つ使われていて紛らわしい。
p278 - 「これはintegerのdigitが1つ以上存在する」は「integerは数字が1つ以上存在する」あたりの方がよいのでは。
p279 リスト8.8 - integer だけラベルがついていて、上記の表現と相まって余計分かりづらくなっている。
p315 - A A A から C C C までだから 3^3=27 が正しい？
p334 - 索引にハ行がない（ハ行がないとは言ってない）
