自作言語(コンパイラ作成)の進め方

42tokyo Advent Calendar 2020の20日目の記事です。


私は一ヶ月ほど前まで自作言語の開発をしていました。作ったやつ
自作言語に関する知識がゼロの状態から開発を始めたため、どのように進めていけばいいのかわからず苦労しました。そこで、自作言語に興味があっても進め方がわからない人に向けてオススメの進め方をまとめてみました。ぜひ参考にしてみてください！！


※この進め方はc++の知識を前提としています
#まずコンパイラの理論を学ぶ
ここでソースコードというテキストファイルが、どのように目的コードへ翻訳されていくのか一通りイメージできるようになっておきましょう。基本的に「構文解析→AST生成→目的コードへコンパイル」という流れになっています。実装もこの流れで行うといいでしょう。

ASTとは簡単に言ってしまうと「コードから必要な意味だけ抽出した木構造」です。こいつをもとに最終的なコンパイルを行います。

各処理のアルゴリズムや中間表現についても学んでおきましょう。この後詳しく説明しますが、構文解析にbisonというツールを使い、目的コードをllvmIRにするのがお勧めで、bisonはLALR(1)のアルゴリズムを理解しておく必要があり、llvmIRは三番地コードなどの中間表現を知っておく必要があります。
#構文解析器(パーサー)を作る
コンパイラの理論を学んだら実装に移ります。ここで作るものは、文字列を定義した構文にパターンマッチさせるパーサーと呼ばれるものです。これはflexやbisonなどのツールを使えば、フルスクラッチより簡単に作れるのでオススメです。私はflex、bisonの使い方を以下のサイトで学びました

http://aquamentus.com/flex_bison.html
http://www.asahi-net.or.jp/~wg5k-ickw/html/online/flex2.5.4/flex_toc.html
https://web.sfc.wide.ad.jp/~sagawa/gnujdoc/bison-1.28/


まずflexでトークン(構文解析での最小単位)に分けるプログラムを作成します。これを字句解析器といいます。次に、字句解析器によって分けられたトークンをbisonで作成したパーサーでパターンマッチさせます。このパターンマッチングは非常にバグりやすいので、先ほど言ったLALR(1)のアルゴリズムをしっかりと理解しておく必要があります。また、ここで構文をたくさん定義して言語仕様を大きくしてしまうと、この後の開発が大変なので自作言語初心者は最低限の仕様にしておきましょう。
#AST生成のアルゴリズムを書く
定義した文法にマッチしたら木構造のノードを作成し、それをつなげて最終的にASTが出来上がるようなアルゴリズムを書きます。具体的な実装方法はこのサイトが参考になります。

https://www.kancloud.cn/digest/xf-llvm/162262


このサイトも構文解析にflex、bisonを使っているのでわかりやすいと思います。解説と公開されているコードを読み込み実装方法を学びましょう。ASTは目的コードへのコンパイルがしやすくなるために作るものなので、コンパイル方法がこの時点で決まっていると作りやすいでしょう。
#目的コードへコンパイルする処理を書く
最後にASTをトラバースし、目的コードへコンパイルする処理を書きます。その方法も先ほどのサイトを参考にするといいです。ここで何を目的コードにするかですが、llvmIRをオススメします。llvmIRを作成すると、llvmのツールによってマルチプラットフォームでの実行、最適化などを行ってくれます。llvmIRへAPIを使用してコンパイルしていきます。llvmIRの仕様やAPIの使い方は以下のサイトが参考になります。

https://qiita.com/sakasin/items/097fa676ccfd117acaa2#%E7%B5%84%E3%81%BF%E8%BE%BC%E3%81%BF%E9%96%A2%E6%95%B0
https://itchyny.hatenablog.com/entry/2017/03/06/100000


llvmは仕様が膨大で目的に合うAPIを見つけるのも一苦労ですが（正直この作業が開発全体で一番きつかった）、根気でドキュメントを読み漁りましょう。

すべてのコンパイル処理を書き終わったら「構文解析→AST生成→目的コードへコンパイル」の流れを実装し終わり、自作言語の完成です！！
#最後に
自作言語開発全体を通してとにかく情報収集が大変だったので、参考になったサイトのリンクを貼りつつ、抑えるべきポイントをまとめました。最後まで読んでいただきありがとうございました。


明日は、私と同じ高校で低レイヤー好き同士のyaitoが担当します。ぜひご覧ください！！