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

2015-05-10

書評

κeenです。正規表現技術入門という本の書評が望まれているようなので今日買ってきて読みました。

私のバックグラウンドと目的

バックグラウンドは

RubyとUnixの正規表現はそこそこ使ってる
ドラゴンブックは読んだことある
RE2の概略も知ってる
VMベースの言語処理系のコミッタなのでVMへの理解もある
Standard MLの正規表現エンジンを開発中。機能はほぼ揃ってる

な感じです。で、実装中の正規表現エンジンがこの本で紹介されてるVM型でもDFA型でもなくVM型の素朴な形、ASTのインタプリタで実装されてるので

インタプリタのまま追加出来る機能はないか
高速化を目指すならVM化とDFA化どちらがいいか
(既存のSMLの正規表現エンジンではVMバックエンドやDFAバックエンドでグルーピングが使えないので)高速な手法でのグルーピングの実装方法が知りたい
後方参照の実装方法が知りたい

などの目的で読みました。割とガチめですね。そういうことを念頭に置いてこの書評を読んで下さい。

書評

1章正規表現

正規表現とはなんぞや？から入り使われる記号などを解説してます。「日本酒うめえwww」など出てきてしかも「草を生やす」の意味の解説がありました。フランクですね。はいはい、と読み進めていったら先読み、後読みなどのあまり理解してない機能の解説やさらに上手い使い方も紹介されておお！となりました。例えばhoge、fuga、piyoの3つが含まれる文字列は

(?=.*hoge.*)(?=.*fuga.*)(?=.*piyo.*).*

と書けるそうです。飽くまで先読みは文字列ではなく位置にマッチするため、正規表現の重ね合わせが出来るんですね。本来ならhoge、fuga、piyoが3!通りの並び方をするので6つの分岐をしないといけない。

あと、貪欲、非貪欲の他に強欲マッチなるものを知りました。確かに実装側としては貪欲マッチでバックトラックしてるところが無駄に複雑になるので強欲マッチがあるとありがたいですね。

正規表現の再帰の話もありました。(?0)で全体、(?n)(n >= 1)でグループを再帰します。予想の通りこれは正規言語ではなくなるのですが、

(\d+|\((?0)\))([-+*/](?1))*

で括弧と四則演算の式をパース出来てしまうそうです。もはやパーサジェネレータ並だなと。と思ったら後で出てくる通り対応する括弧にマッチ出来てしまうので文脈自由文法を受理するそうです。すごい。

導入なので読み飛ばそうと思ったのですがちゃんと飽きさせない内容で良かったですね。

あとこの章でさらっと(否定)?[先後]読みが正規言語の範疇で出来るという（私にとって）大変重要な事実が書かれてました。実装しますかな。

2章正規表現の歴史

一口に正規表現といっても色々あるんだよーな感じな内容。恐らく後の章で比較する時のために役者を揃える目的。

「Unixの正規表現といえばEREのこととする」と書いてあったのでこの章は許さない。あとegrepを使ってる。奴は互換性のためだけに残された非推奨コマンドで、実体は grep -Eだ。古のシェルスクリプトでもない限りgrep -Eを使え。絶対許さない。

3章プログラマのための一歩進んだ正規表現

正規表現の形式的な話のあとはエンジン毎のサポートする機能の違いだとかベンチマークだとかの話。VM型とDFA型の性能特徴が出てて面白かった。

そして正規表現の限界(メールアドレスの精密なバリデーションには正規表現は使えないから妥協しろ、など)にも言及。恐らく使う側からしたらこの辺の話を聞きたかったんだろうが私はそんなに興味ない。

4章 DFA型エンジン

オートマトンの話から入る。んでNFAからDFAを構築する話。ドラゴンブックに載ってたトンプソンのアルゴリズムや部分集合構成法が紹介されてた。しかもPythonによる実装も載っててすごいありがたい。理論系の資料だと自然言語によるアルゴリズムだけで分かりづらいんですよねー。解説も平易。

次にDFAのOn the Fly構成の話。ちゃんと載ってるのはありがたい。しかしほぼ必須の機能といいつつ参考資料が載ってないのが気になった。資料が必要ないくらい簡単なのかな。

最後にDFAの良いところが載ってる。VMと比較したい人には嬉しい点ですね。

5章 VM型エンジン

トイレに行きたくてうずうずしながら読んだので少し軽めにしか読んでない（ごめんなさい）。最初はVMとはなんぞや？という話から正規表現VMの挙動について、CレベルでのAPIについて、実装についてなど。著者が開発している鬼雲で採用されてる方式なだけあってかなり詳しくて丁寧。VMの仮想アセンブラ例とスタックの遷移なども細かく書いてある。

最初に必要最小限な機能をナイーブに実装したVMのコードを紹介して読者に雰囲気を掴ませたあと徐々に最適化していき、最後は鬼雲のコードを見せます。

鬼雲の拡張機能のための命令や高速化のための工夫なども載ってて実装の際にはかなり役立つ筈。ここで目的の1つであったVM方式での後方参照の実装の仕方を知ります。

Unicodeつらいよねーって話とか。Unicode対応しようかと思いましたがこれ読んで諦めました。

AST/バイトコードレベルでの最適化の話もありました。私がプリントしたASTが簡単になるように変換していたものや、インタプリタの機能を出来る限り小さくするためにASTレベルで実現していた機能が実は最適化だったことを知りました。

正規表現エンジンの三大技術動向

JIT、固定文字列探索、ビットパラレルについて。やはりドラゴンブックのように古い本だとこの辺はカバーし切れない。

JITの話

まあ、知ってるよって思ったのですがVM命令を実際にアセンブラに変換した例が載っていて後の参考になりそうだった。あとなぜバイトコードよりJITした方が速いのかの図解がめちゃくちゃ分かりやすかった。あの図、Direct Threaded VMの説明にも使えるのでいつか説明する機会があったら参考にさせてもらいます。ところで本に載ってた鬼雲のコードはDTにしてなかったけど簡単のためなのかな？あるいは厳格にC89に準拠するため？picrinみたくプリプロセッサで分岐すれば使えるのに。

流石にOn the Flyコンパイルの話はなかった。まあ、あんまりメリットないしやんないか。

固定文字列探索の話

grepよりgrep -Fの方が速いよねーって話かと思ったらそれだけではなかった。http://([^/?#]*)?([?#]*)(\?([^#]*))?(#(.*))?みたいな正規表現にマッチさせる時に、まず http:// を固定文字列探索で高速に見付けてからそこを起点にマッチを始める高速化手法があるそうです。固定文字列探索が高速なのはQuick Search（多分尺取り法と同じ）などのアルゴリズムがあるからですねー。あとSIMDやAVXも使える。さらに今回のhttp://みたいな"キーワード"を抽出する技術の話も。

ビットパラレルの話

先の固定文字列探索の話に関連して。固定文字列ではなく文字クラスまで含めても高速に扱える方法。なるほど〜といったところ。SIMDやAVXが使えない/使いづらい言語でも実践出来そうでいいですね。

正規表現の落とし穴

RE2のモチベーションでもある、バックトラックによってマッチングが指数時間になってしまう問題から。「RE2使え」ってくるかと思ったらユーザーレベルでどうにかする話や正規表現の最適化の部分でどうにかする話もあった。

落とし穴とその対策の話があるのですが、一番気になったのがエンジンによる挙動の違い。私の正規表現エンジンはEREを実装することを目標として、grep -Eで挙動を確かめながら実装してたのですがちょっと怪しくなってきた。

マッチ戦略が最左最長か自身がないのもあるけどグルーピングの話。pythonではグループは上書きされて、

>>> r = re.compile('(\w+,?)*')
>>> re.match('apple,banana,kiwi').groups()
('kiwi',)

となるそうです。最初、私の正規表現エンジンもこの挙動をしていたのですが、grep -Eは例えばecho 'apple,banana,kiwi' | grep -o -E '([a-z],?)*'がapple,banana,kiwiを返すのでわざわざ

| Star => (case acc of
                           [] => raise Parse
                         | Group(i, x) :: xs  => parse(ts, Group(i, Kleene x) :: xs, e, gi)
                         | x :: xs => parse(ts, Kleene x :: xs, e, gi))

のように括弧の後にスターが来たら括弧の中のクリーネ閉包をとってました。まあ、実装はそれぞれらしいのでこれが間違ってる訳ではないのですがパーサを不必要に複雑にしてしまったことを反省。

残りはアトミックグループの話だとか。

正規表現を越えて

正規表現周りのツールの紹介の後はBNF、PEGの話。恥ずかしながら、BNFの表現範囲である文脈自由言語が正規表現言語+括弧の対応だということを初め知りました。いや、もしかしたらドラゴンブックに書いてたのかもしれませんが見落してました。

PEGについては、BNFあるしいいやって思ってたのですがマッチが線形時間だったりBNFで表現出来ない範囲まで表現出来たりと中々楽しそうでした。

あとまさかの「草生やす」の説明をした伏線を回収。

付録A.1 正規と非正規の壁

正規言語の話とその辺の証明。否定は正規だけど後方参照は非正規だとか。この本で一番理論寄りな話でありながら同値関係とは〜とかから解説していてすごい丁寧（簡単に理解出来るとは言っていない）。いや、でも本当に正規言語関連の証明が欲しかったらまずはここ参照するかってくらい丁寧ですよ。

付録A.2 正規性の魅力

だんだん感想が雑になってるのからも分かる通り、この辺で力尽きたのでこの章は流しました。後日読みます。

全体を通して

論文やWeb上の資料への参照をばら撒いていますが本書自体は理論寄りになりがちな正規表現の解説を平易に書いていて、かなり敷居を下げてくれたなという印象。正規表現やエンジンの歴史、それによる実装の違いなども説明しているのでこの本を持っていれば正規表現でハマるということもなくなりそう。まえがきにもある通り、Web上では断片的にしか入らない知識が1冊にまとまっている。個人的にはDFAの話をもうちょっと詳しく知りたかった。DFAを実装する時の最適化の話とか。

私のように正規表現を実装したい人だけでなく「正規表現の最適化ってどこまで賢いの？」だとか「このパターンは正規表現で表現出来るの？」だとか「書いた正規表現が魔境で理解出来ないから綺麗に書きたい」だとか思ってる人にも良い本だと思います。

因みにこの本、33,00円ですが私は4,800円でも買った。