概要

正規表現エンジンの理論的背景と実装原理を一冊で体得する

想定読者

正規表現の動作原理を理解したいエンジニア。特にVM型・DFA型エンジンを自作・改造したい中〜上級の実装者

こんな人には向いていない

• grep・sed・Pythonのreモジュールなど特定ツールの文法を手早く参照したいだけの実用リファレンス用途には射程が合わない
• 集合・写像などの離散数学的概念に一切触れたことがない完全初学者には理論パートで早期に詰まりやすい
• 正規表現エンジンを本番環境で実装・改修した経験があるコンパイラエンジニアには基礎説明の比重が大きく感じられる可能性がある

この本で身につくこと

• NFA・DFAの構成とサブセット構成法による相互変換を実装レベルで説明できる
• VM型正規表現エンジンの命令セット設計とバックトラック制御の仕組みを理解できる
• DFA型とVM型のメモリ・時間計算量の特性の違いを根拠をもって使い分けられる
• ReDoSを引き起こすパターン構造とその回避手法を具体的に習得できる
• 基本三演算(和・積・スター閉包)の数学的定義と実装コードの対応関係を理解できる

ハイライト(外部からの言及)

パターンマッチの基本から、基本三演算および理論/数学的背景、VM型/DFA型という二大最新エンジン実装まで徹底解説。また、処理系を踏まえた効率的な書き方や落とし穴を避ける技法もしっかり押さえます。 — 出典

理論・実装・実用技法の三層をすべてカバーする本書の射程を最も端的に示した記述

最近「正規表現技術入門」という本を読み、正規表現の実装について触れる機会があったので、試しに最小の正規表現エンジンを作ってみることにした。 — 出典

本書を読んだ直後に最小のVM型エンジンをスクラッチ実装するに至った読者体験。「読んだ→作った」という行動変化が最も率直に表れており、理論解説の実装誘発力を示す

思いの外、参考にした正規表現技術入門が詳細にかかれており、VM形式で正規表現をマッチするときの、命令列とその解釈の概要も勉強になったのでそこも含めて記事にまとめてみます。 — 出典

別ライブラリの学習目的で本書を参照した読者が「想定を超える記述の詳細さ」を率直に評価したコメント。VM型命令列の解説密度という具体的な観点で既存のhighlightと角度が異なる

章立て

第1章 [入門]正規表現

メタ文字・構文・エンジンの導入。後続章を通じて参照される基礎ピース

第2章 正規表現の歴史

Kleene の正規言語理論から PCRE までの 70 年の系譜。実装と理論を往復する本書の起点

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

純粋な正規表現 vs 最新エンジン実装の差異。POSIX 拡張・後方参照などの実用対応

第4章 DFA型エンジン

決定性有限オートマトン。理論的に最速の探索を可能にする方式の解説

第5章 VM型エンジン

バックトラックを使う Perl 系エンジンの実装。本書の核心の 1 つ

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

JIT / 固定文字列探索 / ビットパラレル。最新エンジン(RE2 / Hyperscan)の理解

第7章 正規表現の落とし穴

ReDoS(壊滅的バックトラック)を実装レベルで解説。セキュリティ視点でも重要

第8章 正規表現を超えて

本書最終章。書かない / 読み解く / 不向きな問題を知るという編集観点での到達点

関連記事 / 参考情報

• インフラエンジニアの自分が買ってよかったと思う書籍10選 — インフラエンジニア視点で本書を含む10冊を推薦。実装・理論以外の職種からの評価として参考になる
• 正規表現からLLVMへのコンパイラを実装する — 本書のVM型エンジン解説を踏まえ、正規表現パターンからLLVM IRを生成するコンパイラを実装した詳細解説
• 正規表現のJITコンパイラを実装する — VM型正規表現エンジンにJITコンパイル最適化を組み込む実装と解説。本書の発展的な応用例
• VM型の正規表現エンジンを実装する — 本書を参照しながらVM型正規表現エンジンをスクラッチ実装した詳細な解説記事
• [ruby] Parsletで正規表現をパースしてvm型のエンジンを実装してみる[その1] パース〜ASTまで — RubyのParsletライブラリで正規表現のASTを生成するフェーズを実装した実践記録
• [ruby] Parsletで正規表現をパースしてvm型のエンジンを実装してみる[その2] AST〜VMまで — 前編に続きASTからVM実行エンジン部分をRubyで完成させた記録
• 【社内勉強会】正規表現 入門(2017/04/05) — 本書を参考にした社内勉強会向けの正規表現入門資料

学習のヒント

• 理論パート(オートマトン・基本三演算)で詰まったら後半のVM型実装章を先読みすると「この理論は何のためか」が具体化し、逆引きで戻りやすくなる
• VM型エンジン章はコードを実際に動かしながら読むのが最も効果的。本書と並行して関連Qiita記事の自作実装を参照すると、別言語による別実装との比較で理解が深まる
• DFA型とVM型それぞれの章を読んだ直後に「どちらが有利なケース・不利なケース」を自分の言葉でメモにまとめると、後半の性能考察が一気に腑に落ちる
• ReDoSの章は、既存コードに正規表現を多用しているエンジニアが最初の入口として読んでも機能する。具体的な脆弱パターンのカタログから逆算して読むと動機付けになる

前提知識

• grep・sed・任意の言語での正規表現の実用経験(文法レベルで書いたことがある程度)
• 集合・写像・直積など大学初年度レベルの離散数学の基礎概念(厳密さより概念の存在を知っている程度で可)
• 任意の言語での基本的なプログラミング経験(実装章を写経・改造する場合)

次に読む本

コンパイラ ――原理・技法・ツール(通称: ドラゴンブック)

本書は正規表現エンジンの字句解析相当の理論と実装に絞っているが、ドラゴンブックは構文解析・意味解析・コード生成・最適化まで含むコンパイラ全体を扱う。本書で習得したオートマトン理論と VM 型バイトコード設計の知識が前提として活きる順序感がある。

計算理論の基礎 第2版(Sipser著)

本書は正規表現エンジンの実装寄りで、形式言語理論の数学的証明は最小限にとどめている。Sipser は正規言語・文脈自由言語・チューリング機械の受容性を ε-NFA の形式的定義から証明するため、本書で直感的に理解した内容を厳密に再構成したい読者に適する。

Writing An Interpreter In Go(Thorsten Ball著)

『正規表現技術入門』がエンジン実装の単一コンポーネントに特化するのに対し、本書は字句解析から構文解析・評価器まで一連のインタープリタとして通し実装する構成をとる。Go で書かれた実装コードは明快で、本書で習得したバイトコード設計の延長として字句解析フェーズを補完できる。