構文解析の本
アスキードワンゴで出版予定。2023年中になんとか完成にこぎつけたい。
Honkit形式で執筆中。
リポジトリの構成
./
book.json // Honkitの設定ファイル
package.json // npmの各種設定
package-lock.json // package.jsonのロックファイル
README.md // このファイル
honkit / // 原稿が入ったディレクトリ
SUMMARY.md // 章構成
README.md // 原稿のREADME
preface.md // はじめに
chapter1.md // 第一章
chapter2.md // 第二章
chapter3.md // 第三章
chapter4.md // 第四章
chapter5.md // 第五章
chapter6.md // 第六章
chapter7.md // 第七章
appendix.md // 付録
.gitignore // gitの管理対象から除外するパターンの列挙
書籍のビルド方法
npm i
依存ライブラリをインストールする
$ npm i
npm run start
Honkitによって、書籍をビルドし、プレビューができる状態にする
$ npm start // Honkitによるプレビュー
...
Starting server ...
Serving book on http://localhost:4000
趣旨
これまで、プログラミング言語処理系（インタプリタやコンパイラ）を作ることについて は様々な本が出版されてきた。特に有名なのは
- 通称ドラゴンブック（邦題：コンパイラ―原理・技法・ツール）
- 通称タイガーブック（邦題：最新コンパイラ構成技法）
この２冊だと言える。他にも、コンパイラで有名な中田育男先生やアカデミアで有名な専門家が 書いたコンパイラの本は少なくない。
一方で、コンパイラやインタプリタの一部となるパーザ（構文解析器）については、非常に 文献が少ない。上記、ドラゴンブックやタイガーブックにて、そのアルゴリズムについて 一部触れられているものの、それ以外は言語作成の過程として多少の説明をする程度である。 英語の本として、構文解析というテーマについて網羅的に触れられているのは、 Parsing Techniques 2nd Edition がほぼ唯一のものであると思われる。
このことには、構文解析が、1970代〜1980年代にかけて「解決した問題」と思われていた ことが一因ではないかと思われる。しかしBryan Fordが発表したPackrat Parsing(2002) やその理論的基礎をなすParsing Expression Grammar(2004)、再帰下降構文解析の新たな 地平を切り開いたLL()(2010)、Adaptive LL()(2014)、GLL Parsing(2010)など、 新しい構文解析アルゴリズムは近年も登場しており、構文解析は「解決した問題」とは いえない。
今ここで、再び構文解析という世界に光をあて
- （非自然言語の）構文解析とはどのような作業なのか
- 構文解析にはどのようなアルゴリズムがあるのか
- 各構文解析アルゴリズムアルゴリズムの特徴と制限
- 下向き構文解析（LL family）
- 上向き構文解析（主にLR family）
- その他
- 新しい構文解析アルゴリズム（2000年代以降）
- GLL
- LL(*)
- Packrat Parsing(PEG)
といったトピックを扱う本を出版したいと考えている。本書を読むことを通じて、読者は
- 自分が行いたい作業にあった構文解析アルゴリズムを適切に選ぶことができる
- 必要に応じて、構文解析のテクニックを使い分けることができる
- 手書きパーザ
- パーザジェネレータ
- パーザコンビネータ
- より柔軟な文法を組み立てることができる
ようになることが期待される。
作業期間（2022年6月21日修正）
基本的に、
- Parsing Techniques 2nd Edition
- コンパイラー原理・技法・ツール
で解説されている内容に加えて最新の論文でしか触れられていない内容をも平易に解説し、実践 でどのように使えるかという内容も盛り込んでいるのでかなりの難産になっている。
- 内容復習および論文読み込み：計2ヶ月
- 各章（４～７章）：各章につき2ヶ月。計8ヶ月見込み
- レビュー（ラフ原稿段階）：１か月
- レビュー（正式原稿段階）：１か月
計10ヶ月くらいの期間を予定している（暫定）。