on
Go言語でつくるインタープリタを読んだ
Tweet
はじめに
Go言語でつくるインタープリタという本を読みましたが、正直めちゃくちゃ良い本でした。 構文解析やASTについてわかりやすく書かれていました。（もちろん、字句解析や評価についても詳しく書いてあるます） Go言語が読めれば、インタープリタについて学べるというのはとても偉大です。 今までのコンパイラ系の本では多くの書籍でC言語で書かれていました。 インタープリタやその仕組みについてGoで学べるということが個人的にはすごくありがたく、筆者や役者には本当に感謝しています。
とにかく良かったです！！
読んだきっかけ
読んだきっかけは２つあります。
- 職場の上司で、Parser(構文解析器)を使ったORMのライブラリを書いていて、自分も読んだり書いたりしたいと思った
- Go言語の静的解析記事を見て自分も作ってみたいと思った
自分は趣味でGo言語をよく扱うのですが、 Go言語には標準ライブラリでParser（go/parserパッケージ）やAST(go/astパッケージ)を扱う枠組みが用意されています。 これらの標準ライブラリを使って静的解析やら、コード生成やらやってみたいと思い、この本を読み始めました。
内容
この本ではMonkey言語というプログラミングのインタープリタを作成していきながら、学んでいきます。 最終的にはプログラムの基本文法だけでなく、配列やハッシュマップや組み込み関数も評価できるインタープリタが完成します。 全体的にテスト駆動開発で進んでいくので、コードも読みやすいです。 本の内容は概ね以下のように別れています。
- 字句解析
- 構文解析
- 評価
字句解析とは
字句解析の入力と出力はそれぞれソースコードとトークン配列です
字句解析ではソースコードを1文字ずつ読んでいって、トークンという意味のある塊で区切っていきます。
例えば演算子や括弧なんかはプログラミング言語に置いて重要な意味を持つのでトークンです。
また、変数宣言の時に使うletや関数定義の時に使うfuncといった予約語や変数名、関数名も当然トークンです。
逆にスペースの文字列は特に意味がないので、字句解析の段階でトリミングします。
今回の字句解析では一行ごとに処理を行っていき、一行ごとにトークン列を配列に追加していきました。
構文解析とは
構文解析の入力と出力はそれぞれトークン配列とASTです。
構文解析ではASTという木を作成するのが、目的です。
ASTではNodeという単位で葉を作成していきます。
例えば、IdentNodeは変数の名前と値（式）をフィールドに保持しています。
Goのインターフェースの機能をうまく使って、Nodeのタイプを分けていたのが印象的でした。
もう１つ構文解析の章で印象的だったのが、
式を再帰的に処理することです。
例えば、1 + 2 + 3みたいな式があったときに、この式は
(1 + 2) + 3という風に木を作っていく部分です。
また、演算子によって優先順位を持たせて木を作って行くところも面白かったです。
評価
個人的には一番好きな章でした。 評価では、構文解析を元に実行結果を返します。 今回の評価器ではGo言語の機能を使って、作成していきます。 最初は数値や真偽値の評価から、式の評価、関数の評価、配列の評価とレベルが上がっていきます。 評価の部分でも再帰的に処理を行います。再帰的に処理を行うというのは １つのAST Nodeに対して処理を定義し、それを使いまわして行くということです。 変数の値や関数の内容をGoのMapで管理するところは面白かったです。 最後のハッシュマップのところも面白かったです。
読んでみて
最初にも書きましたが、めちゃくちゃ良かったです。 Go言語で書かれているので、やっぱり読みやすかったです。 Goの標準ライブラリのASTは、本で使われている、ASTのNode構造体もと非常に似ていてます。 また、本に書かれていた、テスト関数内での、AST Nodeの型アサーションも静的解析で使われているものと非常によく似ています。 なので、静的解析ツールの作成の最初のステップとしてもこの本は良いのではないかと思います。