厳密でパワフルな技法を体感する――近刊『Pythonで学ぶ解析表現文法と構文解析』はじめに一部公開
2022年2月下旬発行予定の新刊書籍、『Pythonで学ぶ解析表現文法と構文解析』のご紹介です。
同書の「はじめに」の一部を、発行に先駆けて公開します。
＊＊＊
はじめに
構文解析は、プログラミングの経験があれば、一度は書いた人も多い身近なプログラムです。本書は、そのような構文解析技法の一つである解析表現文法をPython3による開発実践とともに解説を試みたものです。
本書のメインテーマである解析表現文法は、2004年にBryan Fordによって提案された形式文法です。文脈自由文法に比べ新しく、実用的なアイディアが詰まっています。しかし、それ以上に面白いのは、解析表現文法は、理論を学ぶことから言語処理系の実装まで、コンピュータ科学の世界への素晴らしい入り口を提供してくれる点にあります。
本書では、読者の次のような疑問に答えるような気持ちで説明しています。
・プログラミングが難しいとき、プログラムはどうやって開発すべきだろう？
・プログラミング言語とはどうやって開発すればよいのだろう？
・形式化とは何か？ どのようにプログラミングに役に立つのだろう？
・最近流行りの関数型プログラミングとはどのようなものか？
・計算量とプログラムの実行性能の本当の関係は？
コンピュータ科学においては、理論をしっかり学ぶことも、それに基づいてきっちり開発することも大切です。本書は、両方ともと考えていたら、欲張りな構成となってしまいました。逆に、理論の解説も実装の解説も物足りなく感じる部分があるでしょうが、そのような部分は著者の力量不足をお許し願いたい。
なお、本書は、Python3の文法を習得し、簡単なプログラミング経験があることを前提に書かれています。構文解析で必要となるオブジェクト指向や関数型プログラミングなどの高度な技法は、本書で学びながら読み進められるようになっています。
本書で紹介したソースコードの一部は、以下のGitHubレポジトリから参照することができます。
（以下略）
＊＊＊
著：倉光君郎（日本女子大学 教授）
「文法として曖昧さがない」「正規表現や文脈自由文法よりも強力」などの理由で注目を浴びる構文解析技術「解析表現文法（parsing expression grammar, PEG）」の初の入門書。
《本書の特長》
●Pythonで動く著者提供のツール「PegTree」でパーザを生成しながら解説。理論の詳細に惑わされず、実装上のポイントが効率よく学べます。
●構文解析の初歩から解説。オブジェクト指向プログラミングや関数型プログラミングなどの高度な技法も随時解説されているので、Pythonでの簡単なプログラミング経験があれば、だれでも読むことができます。
●後半では、小規模なプログラミング言語、パーザジェネレータ、パーザコンビネータなどの開発を解説。一段深い解析表現文法の使い方を学べます。
【目次】
1章 構文解析入門
1.1 構文解析とは
1.2 腕試し：数式パーザを書いてみよう
1.3 再帰からのアプローチ
1.4 体系的なプログラム開発へ
第2章 パターンで考える
2.1 パターンの抽出
2.2 BNF
2.3 BNFと構文解析
2.4 BNFから解析表現文法へ
第3章 解析表現文法の登場
3.1 解析表現文法の概要
3.2 PEG文法
3.3 解析表現
3.4 パターンマッチの手順
第4章 構文木とPegTree
4.1 PegTree
4.2 構文木アノテーション
4.3 繰り返しと再帰
4.4 応用例：情報抽出
第5章 計算機を作る
5.1 構文解析の昔ばなし
5.2 数式の構文定義
5.3 PegTreeによるパーザ生成
5.4 構文木とVisitorパターン
第6章 スモール言語を作る
6.1 Chibi言語とは
6.2 Chibi言語の言語設計と構文定義
6.3 トランスコンパイラ
6.4 インタプリタ
第7章 本格的な文法開発に向けて
7.1 プログラミング言語と文法開発
7.2 文脈依存構文
7.3 解析表現文法とプログラミング言語の将来
第8章 解析表現文法の形式理論
8.1 言語を形式化するとは
8.2 文法と構文論
8.3 意味論
8.4 解析表現文法の操作的意味論
8.5 解析表現文法と形式言語
第9章 PEGパーザを作る
9.1 パーザジェネレータの開発
9.2 解析表現のデータ表現
9.3 パーザインタプリタ
9.4 言語内ドメイン特化言語
第10章 パーザコンビネータ
10.1 関数型プログラミング
10.2 パーザコンビネータ
10.3 パーザコンビネータとPEG文法
第11章 実用的なPEGパーザの開発
11.1 パーザコンテクスト
11.2 構文木の構築
11.3 PEGパーザの実行性能
第12章 Packrat構文解析法
12.1 最悪指数時間問題
12.2 メモ化：指数時間を避ける技法
12.3 PEGパーザとメモ化
12.4 理論と実践のはざまで
付録 構文レシピ
索引