ANTLR 作者による本で、中身は後半から ANTLR を使った実装でした。ただ、ANTLR を使用する・しないに限らず、解説を読むだけでもインタプリタ制作に詳しくなることができる一冊かなと思います。要するに、何か特定のツールや言語に限らない広く使える知識を習得できるということです。
また、中身は Java で実装されていますので、他のコンパイラ本のようにがんばって C 言語を読む必要もありません。ただ、実装がちょっと古いように感じたので、適宜最近の Java の実装に置き換えて考えてみるといいかなと思います。
言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで
- 作者: Terence Parr,中田育男,伊藤真浩
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/12/24
- メディア: 大型本
- 購入: 5人 クリック: 333回
- この商品を含むブログ (13件) を見る
読んだ動機
- 以前、スクリプト言語や Lisp のインタプリタなどを作ったことがあったが、理論的な背景についてより深く体系的に勉強したいと思ったから。
- ただ、コンパイラの教科書はまだちょっと難しかった…と思っていた矢先に、 Java による実装例が豊富な本書が目に止まったから。
読後の感想
- インタプリタの実装について一通り、しかも手軽に学ぶことができる: ただのスクリプト言語用インタプリタではなくて、一応バイトコード出力くらいまで取り扱ってくれます。ただ、AST を作って、それがどの木かを判別するくらいまでしかしていなくて、いわゆる eval (評価フェーズ) は取り扱っていません。
- ANTLR について知りたい際にはもってこい: ANTLR のサンプルコードがたくさん載っているので、ANTLR 入門にもとてもよいと思います。
- コードがちょっと微妙…: 私があまり、フィールドを使った再代入などが好きではないという好みの問題かもしれませんが、もう少し Effective Java に載っているようなアンチパターン的な実装を減らしてほしかったかなと思いました。もっとも、作者もアンチパターンをしていることはわかっているようです。あえてそうしている的な説明がきちんと本の中でなされているので、そこは好感のもてるところではあるのですが。ちなみに LL(1) パーサに関しては Scala でちょっと書き直してみました (動作未確認) 。ただ、あまりに辛くて途中で挫折しましたorz
ちなみに、言語実装に関する基本的な話のみを知りたいとしたら、本書は1章を読んで閉じるのもありです。長いので、サラっと読んだだけの章は1行くらいでメモを残しておきます。
読書メモ
1章
言語実装に関する基本的な知識が詰め込まれています。1章を読んで本を閉じてもかまわないくらいよくまとまっていると思いました。
- 言語は reader, generator, translator, interpreter によってできています。reader はテキスト読み取り、generator は内部データ構造を走査して出力を書き出し、translator はテキストを読んで同じ言語・別言語の形式に沿って出力を書き出す、最後にインタプリタは命令を読み込んで解読し、それを実行するものです。
- reader→構文解析、generator→木構築、translator→スコープ作成、interpreter→バイトコード出力といったくくり？
- Java コンパイラが生成する .class ファイルの中には、記号表と抽象構文木が直列化された状態で格納されています。
- FindBugs は BCEL を使うことにより、 .class ファイルを読み取る方式を取っています。
2章
よく聞く LL(1) ならびに LL(k) 構文解析に関する話です。本当にコンパイラを作る上でよく見る手法が掲載されています。
- LL : 1個目の L は「左から右に入力を読み取る」ことを指していて、2個めの L は「左から右の子ノードの順で構文木の階層を下る」ことを指します。後述するように、プログラムの1つ1つの句は、最終的には一度木構造に直して、それから解釈を開始するので、子ノードという表現になります。
- 句の構造を理解して、木を作成するまでが構文解析の仕事: たとえば、次のようなコードがあった場合、下記のように木を作ります。これさえ覚えておけば、あとは Token を生成するだけで一通りインタプリタの基礎は出来上がります。
if (x < 0) x = 0; ^^^^^^^ ^^ 式(expr) 式(expr) ^^^^ 代入(assign) ^^^^^^^^^^^^^^^ if 文 (ifstat) ^^^^^^^^^^^^^^^^ 文 (stat): セミコロンまで
- 先読み集合: 特定の構文候補の先頭になることができる字句の集合のことをいいます。計算方法は2種類あり、FIRST と FOLLOW と呼ばれているようです。しかし、実際は「この構文候補ではじまるすべての句に対して、どの字句ならその句を開始できるか？」を考えるとより簡単に先読み集合を計算できます。
3章
LL ではシンプルすぎて、たとえば C++ といった高度で複雑な文法をもつ言語の構文解析には対応できないので、それに対応するための手法がいくつか紹介されています。後戻り構文解析器、メモ化構文解析器、述語制御構文解析器の3つが紹介されていました（正直消化不良）。
4章
いわゆる AST (抽象構文木) を作るフェーズです。昔作って遊んだ経験もあいまって、この辺の理解は少し深まった気がします。
- 改めて、なぜ木を使って文を認識するのかの話。多くの言語には、部分句と入れ子構造が存在しており、それを表現するのに木の方が、他のアルゴリズムに比べて都合がいいからとのことです。
- AST は次のようにノードを作っていくことで、最終的に木として扱えるようにします。Scala だと、case class を始めとする代数データ型 + パターンマッチングをすることで本当にスッキリ書けそうだなと思いました（下記の実装は Scala によるものです）。Rust だったら enum かな。
sealed trait AST sealed trait ExprNode extends AST case class AddNode(evalType: DataType) extends ExprNode case class MultNode(evalType: DataType) extends ExprNode case class IntNode(evalType: DataType) extends ExprNode
- その他、さまざまな構文木の構築手法について解説がされています。
5章
木の走査について。Visitor パターンを使って、再帰的に処理していくのが一般的みたいですね。なお、このあたりまでは、基本的にパーサーコンビネータのライブラリを使うことで、そちらに処理を任せてしまうので、普段意識をすることはあまりないかなと思いました。もちろん、中身をブラックボックス化せず、内部的な処理を理解しながら利用することは、デバッグ精度の向上にもつながりますしとても重要なことです。
6章
ここからが結構おもしろかったです。まずは、スコープの作り方。
- まず、Symbol と Type という概念を導入します。Type は後続の章で出てくるので後述しますが、型を表します。Symbol は、それがメソッドであることを示したり、変数であることを示したり、クラスであることなどを示します。
- さらに、各 Symbol は Scope の中にまとめられます。実装としては下記のようになるはず。
trait Scope { /** * 名前を取得します */ def name(): String /** * 他のスコープの中で入れ子状態かどうか * @return [[Scope]] */ def enclosingScope(): Scope /** * シンボルをスコープの中で定義します。 * @param symbol [[Symbol]] */ def define(symbol: Symbol): Unit /** * スコープの中で、引数として与えられたスコープ名を検索します。 * @param name スコープ名 * @return 検索結果の [[Symbol]] */ def resolve(name: String): Symbol }
- スコープは、スコープスタックにまとめられて順繰りに取り出されるようにして判定が行われていきます。コード上のスコープは、このようなシンプルな仕組みで表現されているのですね。
- プログラムでは結構入れ子スコープになるのですが、入れ子も木で表現されます（スコープ木）。たとえば
MethodSymbolは、さらに内部に自身のLocalScopeを保持しており、そのLocalScopeはさらに、自分自身の中にどのようなシンボルを持っているかを保持しています。
trait Symbol case class MethodSymbol(name: String, orderedArgs: List[String], scope: LocalScope) extends Symbol // エトセトラ。変数のシンボルなども続きます。 trait Scope case class GlobalScope(symbols: List[Symbol]) extends Scope case class LocalScope(symbols: List[Symbol]) extends Scope
7章
クラスや構造体のスコープ木の構築に関してでした。基本線は6章とそこまで変わりません。クラスの場合は、継承も表現する必要があるのですが、継承もきちんと表現できていました。すごいですね。
8章
ついに型をつけます。型計算と呼ばれる物を使って、型安全性やポリモフィズムを実現します。また、暗黙の型変換（int → double とか）に関する解説もあります。このあたりから、結構ハードに ANTLR が登場してきます。
9章
これまでの章で解説された実装をすべてつなげて、インタプリタの実装を行います。総集編ですね。
10章
9章の実装で一通りインタプリタは作成できるのですが、それだけだと速度が遅く、とくにプログラミング言語を作る際にはとても使い物にならないそうです。そこで、バイトコードを直接解釈できるバイトコードインタプリタの作成に取り掛かります。
11章, 12章
Wiki から HTML に変換したり、あるいは Java のクラスを、テーブルを作成してくれる SQL に変換したりするサンプルが掲載されています。
今後
有限状態オートマトンの理解を進めたいのと、それを使った関数型による Lexer の実装をしてみたいですね。そこさえクリアできれば、この本に載っている話のほとんどを関数型プログラミングで実装できるかなと思いました。実際、再帰を非常によく使う話ですし、代数データ型とパターンマッチングでかなりスッキリさせられるはずなので…。
