The Super Tiny Compiler ではじめるコンパイラ入門
The Super Tiny Compiler とは？
The Super Tiny Compiler は、わずか 200 行の JavaScript で書かれたコンパイラです。
Super Tiny の言葉どおり機能はとても限定されていて、LISP ぽい関数呼び出しを C 言語のような関数呼び出しに変換するだけです。
;コンパイル前
(add 2 (subtract 4 2))
//コンパイル後
add(2, subtract(2, 4));
ただ、内部実装的には 変換元コード ➜ Tokenize(字句解析) ➜ Parse(構文解析) ➜ Transform（変換） ➜ Generate（コード生成） ➜ 変換後コード と一般的なコンパイラの処理の流れを踏襲しています。
すべてのコードに心底丁寧にコメントが記載されているので、これを写経するだけで、コンパイラの雰囲気が理解できると思います。
機能ごとの振り返り
今回 The Super Tiny Compiler ただ写経するだけでなく、 開発体験の良い TypeScript with Deno で再実装してみました。そのコードとともに各機能実装の振り返りを記載します。
以降で紹介する実装コードはこちらです。
元リポジトリでは、すべて 1 ファイルにまとめられていますが、上記リポジトリでは機能ごとにファイル分割して、それぞれに Unit Test を追加しています。
1. Tokenize（字句解析）
Tokenize では、コードの文字列を、Token という種別ごとにラベル付けされたオブジェクトの配列に変換します。ここで解析に不要な空白などは削除されます。
const token = [
{ type: "paren", value: "(" },
{ type: "name", value: "add" },
{ type: "number", value: "2" },
{ type: "number", value: "4" },
{ type: "paren", value: ")" },
];
仕組み的には、while ループでコードの文字列を一文字ずつ解析して、種別ごとにラベルと値を持つオブジェクトに変換していく形です。
2. Parse（構文解析）
Parse では、Token を AST（抽象構文木）に変換します。
AST は、コードの構文構造（意味を理解するために必要な構造）を木構造で表したものです。
ここで、さきほどのparen（()）などプログラムの実行に不要な情報は取り除かれて、関数、引数、文などのまとまりごとに構造化されます。
const ast = {
type: "Program",
body: [
{
type: "CallExpression",
name: "add",
params: [
{
type: "NumberLiteral",
value: "2",
},
{
type: "NumberLiteral",
value: "4",
},
],
},
],
};
3. Transform (変換)
Transform では元コードの AST を出力したい構文構造を表現する新しい AST に変換します。
ここでは、Traverser という AST を巡回する関数と、 Transformer という Traverser を使って実際に AST を変換する関数を作成します。
Traverser
Traverser は AST を深さ優先で探索する関数です。
ast と visitor（ast の各ノードのタイプによって実行する処理を設定したオブジェクト）を受け取り、内部で定義した traverseArray と traverseNode という 2 つの関数を再帰的に呼び出すことで、visitor に設定された node の種別に応じた処理を実行します。
Traverser には、ノードへたどり着いた時に実行されるenterと、ノードの子要素を探索して戻ってきた時に実行されるleaveの 2 つの処理実行タイミングがあります。
Transformer
Transformer は AST を受け取り、別の構文構造を持つ新しい AST に変換する関数です。内部では、さきほど定義した Traverser を使っています。
個人的にここの実装が 1 番のハマりポイントでした。
最初、なぜこのコードで新しい AST が出力できるのか全然わからず、print デバックを繰り返しました。。
理解のポイントはCallExpression ノードの処理にて、ひとつのexpression オブジェクトの参照を expression.arguments と、expression 自身で使い分けて、node と parent それぞれの __contextに登録している点です。
元コードにもコメントされていますが、これはなかなか Hacky なので、コードレビュー依頼でこの実装を使った PR が来たら相当困ると思います 😅
4. Code Generate
最後に、Transformer によって変換された AST から、文字列を出力します。
ここはとてもシンプルで、Node のタイプごとに再帰的に文字列化をおこない、要所で()や;などコードの構造を表現する記号、空白や改行などの読みやすさを担う文字列を追加します。
これでコンパイラの実装はすべて完了です。
いままで作った関数を組み合わせると、コンパイラの一連の処理を表現できます 🎉
export const compiler = (code: string) => {
const tokens = tokenizer(code);
const ast = parser(tokens);
const newAst = transformer(ast);
const output = codeGenerator(newAst);
return output;
};
おわりに
The Super Tiny Compiler はコンパイラの処理を完結に理解するためのとても優れた教材だと思いました。
是非試してみてください。
また、The Super Tiny Compiler の次のステップとしては、Go 言語で作るインタプリタ や、Let's build a browser engine! もオススメです。
2022/10/03 13:03 追記
@ababupdownba さんに以下を教えてもらいました！こちらもオススメです。
Discussion