2023-12-04

自作Cコンパイラ（未完成）

この記事は大阪工業大学 Advent Calendar 2023の4日目の記事です。

はじめに

これは今年ちまちま書いてたCコンパイラ（未完成）のゆるふわ解説です。
実装はリンク先にあります。

コンパイラのアルゴリズムや仕組み、本記事を執筆する参考として低レイヤを知りたい人のためのCコンパイラ作成入門を参考にしています。リンク先の記事は非常に良いテキストなのでちゃんとした仕組みなどが知りたい場合はこの記事ではなく、リンク先の記事を読んでいただければと思います。

また、実装に関してはO'Reilly Japan - Go言語でつくるインタプリタを参考にしています。こちらの書籍はコンパイラではなくインタプリタですが、実装としては共通する部分が多いため非常に参考になりました。

コンパイラとアセンブラ

コンパイラは人間が書いたソースコードを読み込んで、コンピュータが実行できる形式に変換してくれるプログラムです。C言語を書いたことがある人であれば$ cc -o a.out main.c のようなコマンドを実行したことがあると思います。

なぜわざわざコンパイルする必要があるのか？直接コンピュータが実行できる形式でプログラムを書けばいいのでは？と疑問思う人がいるかもしれません。（昔の人は直接書いてたみたいです。）

コンパイルを実行するのがメンドクサイと思うかもしれませんが、最近のコンピュータが直接実行できる命令は '0'，'1' の羅列からなる数列で表現されるており、機械語と呼ばれています。そのため、機械語を直接書くためには '0', '1' からなる数列を打ち込む必要があり非常に厳しいです。

そこで開発されたのが機械語に人間が読める形式で文字を当てはめたアセンブリです。アセンブリは機械語と一対一対応していますが、そのままでは実行できないためアセンブリを機械語に変換する処理が必要です。

この処理はアセンブルと呼ばれます。上記のccコマンドの例でもそうですが、最近のコンパイラはこのアセンブルの処理も同時に行っています。今回作成しているコンパイラではこのアセンブルは行わず、C言語のソースコードからアセンブリを出力するような構成になっています。

機械語とアセンブリの例として次のadd関数を逆アセンブルした結果を載せておきます。

int add(int a, int b){
        return a + b;
}

話が少しずれましたが、アセンブラの登場により命令を人間が直接読める形式で記述できるようになりました。しかし、人間が直接読めるようになったとは言えアセンブリの表現力は低く、大きなプログラムを作成するのは非常に大変です。先ほどの例で挙げたadd関数を逆アセンブルした結果を見てもらえばわかるかと思います。

そのため、より高級で表現力の高い言語としてC言語などのプログラミング言語を人間が書いて、コンピュータが実行できる形式に変換するためにコンパイルを行う必要があるのです。

前置きが長くなりましたが、単純なコンパイラの処理を大きく分けると、
字句解析・構文解析・意味解析・コード生成・最適化に分けられると思います。

今回作成しているコンパイラでは最適化の処理をまだ作成しておらず、意味解析に関しては構文解析のおまけ程度で行っているので、それ以外の３つの処理について実装を交え簡単に解説していこうと思います。

字句解析（Lexer）

github.com

まず初めの字句解析では、単語をトークンと呼ばれる単位に分けます。トークンの種類としては数値や演算子、記号、予約語などです。これらのトークンは次の構文解析で利用します。

int a = 123 * b;

例えば上記のようなコードがあった場合、トークン列は次のようになります。

[ TYPE, IDENT, INT, ASTERISK, IDENT, SEMICOLON ]

字句解析を行う関数の実装としては、次のようにトークンとリテラルの値を持つ構造体を配列として作成して返却するような実装になっています。

type Token struct {
    Type    TokenType   // string
    Literal string
}

字句解析は特に複雑なアルゴリズムなども必要ないのであまり説明することもありませんが、文字列をどこまで読み込んだかなどの境界でバグらせやすいのでテストをちゃんと書くことが大切だと思います。（n敗）

構文解析（Parser）

github.com

抽象構文木

構文解析では字句解析で作成したトークン列を元に抽象構文木を作成します。
抽象構文木は括弧などの意味に関係のない情報を取り除き、演算子をノード、値を葉とするような木構造になります。

例として int a = 1 + 2 * 3; のような簡単な式を抽象構文木にしてみます。

この例では =, *, + が演算子です。ポイントとしては演算子のノードは葉だけでなく同じ、もしくは異なる演算子のノードを再帰的に持つことが出来ることです。もちろん、どんなノードでも持てるわけではなく言語仕様によって異なります。

また、この抽象構文木は演算子の優先度をそのまま表しています。ある演算子のノードを評価するためには、そのノードが持つ子のノードを評価します。そのため、今回の例だとまず 2 * 3 を評価し得られた 6 を 1 + 6 のように評価したのち a に代入します。

実装に関した話をすると、参考にしているGo言語でつくるインタプリタの実装がかしこいなと思って真似しています。C言語のノードを表現する型を考えるときにノードの種類を大きく分けると式と文に分けられます。（宣言などもあります）

式は 1 + 2 * 3 のように評価されると値を生成するもので、文は return 123; のように評価しても値を生成しないものです。この式と文を表現するインターフェースを次のようにそれぞれ用意しておき、式と文を表すノードに実装させています。そうすることで、実際に構文木を作成する際に返り値の型を絞ったり、型アサーションを可能にしています。

type Node interface {
    node()
    String() string
}

type Statement interface {
    Node
    statementNode()
}

type Expression interface {
    Node
    expressionNode()
}

このような演算子の優先度を考慮したような抽象構文木を作成するために、再帰下降構文解析と呼ばれる方法で抽象構文木を構築します。

再帰下降構文解析

プログラミング言語の構文を記述する方法としてBNFと呼ばれるものがあります。詳しくは調べて欲しいのですが、BNFを用いることで文法を再帰的に定義することが出来ます。

C言語の文法をBNFで記述するとリンク先のようになります。

cs.wmich.edu

再帰下降構文解析の面白いところは、BNFにより文法がしっかりと記述されているならば、BNFに対応するように関数を実装するだけで構文解析が行えることです。また、ボトムアップ式に構文解析を実装する場合も、後回しにしたい機能は構文規則に対応する空の関数を作っておけばいいので実装面でも書きやすいと思います。

このように文法規則に従って関数を実装するだけで演算子の順序を考慮したような抽象構文木が作れるの面白くないですか？面白いんですよね。

コード生成（Generator）

github.com

コード生成では構文解析で作成した抽象構文木を元にアセンブリのコードを生成しています。演算などは仮想的なスタックマシンとして実現しています。コード生成に関しては参考にしている低レイヤを知りたい人のためのCコンパイラ作成入門とほとんど変わらないと思うのでそちらを読んでいただければと思います。~~（力尽きました）~~

おわりに

今回作成しているコンパイラは完成までまだまだ道のりが長いですが、それなりにちゃんとしたコンパイラを作成するとそのコンパイラで自分自身をコンパイルしたり、また別のコンパイラをコンパイルしたりできるようになります。

今使われているコンパイラも他のコンパイラによってコンパイルされてるんだなぁーと思うと、生物の自己複製や進化の過程っぽくて感慨深くなっちゃいますね。少しややこしくなりましたが、言いたかった事としてはコンパイラが再帰的にコンパイラを作るのって滅茶苦茶面白いと思うんですよね。

非常に個人的な意見ですがコンパイラなどの言語処理系を書く営みがプログラミングの中で一番面白いと思っています。構文解析で出てきた再帰下降構文解析もそうですし、コンパイラがコンパイラをコンパイルする流れなど再帰的な構造が好きなのかもしれないですね。

おまけ

今回のコンパイラはGolangで実装しているのでWASMにコンパイルできます。なので、ブラウザでデモを試せるようにGithub Actionを利用してmasterが更新されるとWASMにコンパイルし自動でデプロイするようにしています。
まだ実装していない構文やバグってる構文が割とありますが、テストに書いてある構文はコンパイルできるはずなので、興味があれば触ってみてください。

aoken7.github.io