Nimで自作インタプリタ③ Evaluatorを実装した

前回のコレコレの続き。

リポジトリ

ここ

evaluatorのコードとしては250行くらい。
README少し整備しないとな。

振り返り、LexerとParser

ここまで作ってきた、LexerとParserについて軽く振り返っておく。

Lexerというのは字句解析器のことで、ソースコードを読み込んで、意味のある最小単位であるTokenに分割する。

前に書いた記事からまるまるパクると、以下のようなコードを字句解析すると、

以下のようなToken列が出力される。

Parserというのは、構文解析器のことでLexerの出力したToken列を入力として、文法エラーなどをチェックしながらASTを作るもののこと。

これも前の記事がパクると、以下のようなコードから、

以下のようなASTを作成する。

Evaluatorとは何か

Evaluatorは日本語では「評価器」のこと。名前の通り、評価をする。

Parserまでは、単純にToken列を見て、「文法的に正しいか」だけを見ており、なんの意味も持っていなかった。

つまり、「1 + True」という文字列は間違ってて、「1+2」という文字列は正しいことは知っているけど、この結果が「3」になるなんて知らなかった。

そこで、Evaluatorを導入することで、この文字列の集合に意味をもたせ、評価できるようにする。また、定義した関数を呼び出せるようにするのもの、これの仕事だ。変数のスコープに気をつけながら関数を扱う。

動いているところ

先日、Twitterに動いているところを投稿した。

具体的にどう実装するか

ここで実装しているevaluatorの評価戦略には、「tree-walking型インタプリタ」のものを採用している。

これはどうやら、インタプリタの原型で最も単純なものっぽい。Parserの出力したASTをそのまま辿り、数値計算や関数を実行したりする。特に最適化もしないので実行速度は遅いが、作りやすく、考えやすく、拡張性や移植性も高いもの(らしい)。

今回は採用していないが、他の評価戦略としては、Ruby v1.9以降で採用されているASTを一度バイトコード(厳密には32bitのワードコード)へ変換し、その後、just in timeで仮想マシン上で動作するものもある。

他にもそもそもASTを作らずに直接バイトコードを出力するものや、逆にASTから直接機械語に変換するものもある。

非常に興味があるので、この辺も今後調べていきたい。

具体的にコードを見てみると、だいぶ簡素にしてるが以下のような感じになっている。このeval()という関数を再帰的に呼び出すことで、評価を行う。

ちなみに実際のコードはここ

eval()の関数の中身はただのcase..of文(他の言語でいうswitch文)で、parserの出力したASTノードによって条件分岐を行っている。

続き

おおまかにはインタプリタ作成自体はほぼほぼ終わった。

あとは、途中端折ったところや、実はやばめのバグが合ったりするので、そこを修正し、さらに足りない機能を拡張したりする。

例えば、型の概念を導入し、演算子に多相性を持たせたり、組み込み関数などを導入したりだ。

さいご

エラーメッセージをかわいくした

Nimには慣れてきた気もするが、まだまだNimれてないなって気もする。