自作コンパイラを実装してみた

はじめに

こんにちは、高二の中野です。今回の部誌では、コンパイラについて紹介してみたいと思います！自分自身昔からコンパイラに対して「難しそう」みたいな偏見を抱えていて全く触れてこなかったのですが、ふとしたきっかけで自作Cコンパイラについて体系的にまとめているサイト(参考文献に載せておきます)を見かけて覗いたところ、「意外といけそう」と思ったので軽く始めてみたらハマってしまったという次第です。ところどころ至らない点があると思うので、もし不明な点や疑問があればこのメールアドレス( s2017197@asano.ed.jp )に連絡してください。

対象読者

C++, Pythonなどのメジャー言語で基礎的なコードが書ける人。ある程度人のコードが読める人。今回の部誌は扱う内容がかなり学問的というか高度なので、細かいプログラミング言語の文法などは説明しないのでご了承ください。同様に小学生がこれを読むのもあまりおすすめしません。受験勉強してください。逆にこの条件から外れた方々にとっては割と楽しめる内容かと思います。わからない用語・関数などが出てきたら適宜自分で調べてみてください。コーディングにおいて自分のほしい情報を限られた時間でインターネット等で見つけるのは大事な能力です。ちなみに私はC++のリファレンスを参照する際には cpprefjp(https://cpprefjp.github.io)を主に使っています。

コンパイラとはなんぞや

ではここから実際にコンパイラとは何かを説明しましょう。 Wikipediaにはこのように書いてあります。

コンパイラ（英: compiler）は、コンピュータ・プログラミング言語の処理系（言語処理系）の一種で、高水準言語によるソースコードから、機械語あるいは元のプログラムよりも低い水準のコードに変換（コンパイル）するプログラムである。

有名な話かもしれませんが、コンピュータは0と1の羅列(2進数)をデータとして扱い、それをもとに計算などを実行しています。要は、コンピュータは0010100110011001010101000などのような我々人間にとって一見摩訶不思議に見える数字の羅列を用いています。一方、我々は普段日本語や英語などの自然言語を用いています。この人間とコンピュータの通訳係となってくれるのがコンパイラです。大半のプログラミング言語は人間にとってある程度の可読性が担保されています。もちろん、我々はコンピュータを利用するためにさっきの0と1の羅列を自分でキーボードで打つわけにはいけませんよね？その、割と人間寄りいわば自然言語寄りのプログラミング言語をコンピュータが理解できるように0と1の羅列に変換するのがまさにコンパイラの仕事なのです。 コンパイラの仕組みを理解することできっとあなたはコンピュータと、より親しくなれるでしょう！

コンパイルの手順

前章ではコンパイラの概要について説明しました。ここから詳しい話に移りたいと思います。まず簡潔に言うと、コンパイラは以下の4つのフェーズを踏んで実行されます。

1.字句解析
　　　↓
2.構文解析
　　　↓
3.アセンブリコードの生成
　　　↓
4.生成したアセンブリコードをバイナリに変換する

これだけだと分かりづらいと思うので具体例を出して説明します。今 int main(){return 0;} というC言語のソースコードをコンパイルしたいとします。当然コンパイラへの入力形式は 文字列 です(C++で扱うとしたら const char*やstd::stringのような型を用いるでしょう)。しかしコンパイラからしてみると、文字列の状態だと大変扱いづらいのです。プログラムによってはint main () { return 0; /*hogehoge*/} のような本来コンパイルする際には不要な空白やコメントがついている場合もあります。それを除去してよりソースコードの本質を抽出するような処理が1番目の字句解析です。このプログラムの場合、ソースファイルは [int,main, (, ), {, return, 0, ;, }] という一つずつが意味を持った 字句(トークン) の配列に変換され、コメントや空白なども全て無視されます。こうすることで、2番目以降の処理が格段にやりやすくなるのです。次にこのトークン配列を 構文解析木(AST) という 木構造 に変換します(なぜこのようにする必要があるのかは後ほど説明します)。この工程を文字通り　構文解析と呼びます。そして、その構文解析木を元にアセンブリコードを生成して、そのコードを機械語(バイナリ)に変換(アセンブルといいます)すればコンパイラの仕事は終わりです。字句解析の過程は比較的に簡単なので、ページ数的に ここでは省略したいと思います。では次章からさっそく構文解析から実装していきましょう！ちなみに今回はすべてC++で実装しています。

開発環境

今回私はVisual Studioでコーディング&ビルドし、生成したアセンブリコードは WSL(Windows Subsystem Linux) というWindowsマシン上でLinux(Ubuntu)が動く的な仮想環境上で実行ファイルにアセンブルしました。ちなみにビルドする際は x86 ではなく x64 でビルドしてください。 x86 だとなぜか WSL の呼び出しに失敗します。

構文解析

gcc などの我々が普段書くようなコードをコンパイルしてくれるコンパイラの全てをここで実装するのは到底不可能なので、 まず最初に、四則演算をしてくれるコンパイラを作成したいと思います。例を上げると、 1 + 2 * (3 + 4) という文字列を入力すると 15 を返してくれるアセンブリコードを出力するプログラムを作ります。そして、今章では前章で扱ったフローのうち、構文解析について説明します。ちなみにmain関数にコンパイラのすべての要素を実装するのは可読性的にあまりよろしくないので、構文解析は Parse という専用の関数に実装し、それをmain関数で呼ぶ形式を取りたいと思います。また構文解析の段階では字句解析は終了している(Tokenize関数で実装している)ので、以下に示す Token クラスのベクターである std::vector<Token> tokens; が既に存在しているという前提で話を進めます。ちなみにこれからはソースコードは全体ではなく変更部分だけを載せたいと思います。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

//予め必要なファイルはここでインクルードする
#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <functional>
#include <fstream>
#include <algorithm>
#include <cassert>

//トークンの種類を表す列挙型
enum class TOKENTYPE {
    NUMBER, //数字リテラルトークンを表す
    CHARACTER, //文字リテラルトークンを表す
    STRING, //文字列リテラルトークンを表す
    SYMBOL, //(, ), {, }などの記号トークンを表す
    KEYWORD, //intやreturnなどの予約語トークンを表す
    IDENTIFIER, //変数名などの識別子トークンを表す
    NONE //トークンが初期化されてない状態を表す
};

//トークンクラス
class Token {
public:
    TOKENTYPE type;
    std::string string;
};

std::vector<Token> tokens;

int Tokenize(){ ... } //ここで字句解析を行う。字句解析の結果はtokensに保存される。本誌では扱わない。

int Parse(){ ... } //ここで構文解析を行う。本章はこの関数に焦点を当てる。

int GenerateAssembly(){ ... }//ここでアセンブリコードを生成する。8章ではこの関数に焦点を当てる

int main(){
    Tokenize();
    Parse();
    GenerateAssembly();
}

さて、本格的にコーディングを始める準備が整いました。ここで先程提示した 1 + 2 * (3 + 4) という数式に考えてみましょう。もし、この世の数式が数字と + と - のみで表されていたらその値を計算するのはとても簡単です。前から数字を読んでいって + で繋がれていたら前の結果にその値を足す、 - であればその値を引く、というふうにすることで楽に実装できます。問題を複雑にしているのは + や - ではなく * や / であるということになります。そして、ここで大事なのは数式には文法があるということです(コンパイル実装においてさらに広義的に考えると、プログラムのソースコードにも文法があるということになります)。ルールがなかったら数式をどの人が見ても普遍的に認識することができません。ロシア語圏では数式はこのように理解されて、フランス語圏ではまた別にこのように理解されて～～ということはありえないのです(自然言語にはそういうのは多々ありますが)。また、もちろんルールが存在するということはそのルールを記述する専用のフォーマットが存在するということです。有名どころでいうとBNF記法(バッカス・ナウア記法)などがあります。Wikipediaの記事(https://ja.wikipedia.org/wiki/バッカス・ナウア記法)を見ると、アメリカでの住所表記のルールがBNF記法で記述されていて面白かったです。このように、BNF記法は広範に及んで適用可能な記法なので昔からずっと使われているのだと思われます。そして、数式というのもまたBNF記法の適用範囲内なのです。今回はBNF記法を拡張したEBNF記法で数式の文法のルールを書いてみます。それが ソース2 です。

1
2
3
4

Expr = Mul ("+" Mul | "-" Mul)*
Mul = Primary ("*" Primary | "/" Primary)*
Primary = Num | "(" Expr ")"
Num = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

このEBNF記法ではnumが数字リテラル(0~9)を表しており、どの数式もこのような入れ子構造(木構造)で表現することができ、我々が小学校で習った四則演算の順序としっかり一致しています。以下に示す木構造は、式1 + 4(2 + 3) - 5 を ソース2 のEBNF記法に基づいて分解したものになります。BNFなどの生成規則に基づいて生成された木構造を 構文解析木 といいます。

一見なんだか難しそうな気がしますが、この木構造もちゃんと上の規則に従っています。そして、プログラミング言語もこれらの規則が複雑になっているだけでちゃんとコーディング時の文法ルールもBNFで記述することができ、ソースコード自体も構文解析木に落とし込むことができます。4章で私はトークン列は構文解析木に変換する必要があると言いました。木構造の特徴として再帰的処理(深さ優先探索など)が行いやすいというのがあります。このことこそがトークン列を構文解析木に変換する意義の一つです。何千行もある膨大なソースファイルを正確にアセンブリに変換するには再帰的処理を行うことで明快に実装することができるのです。 ただしExpr, Mulなどのノードは実際のコンパイラ実装には不必要なのでそれらのノードを削った木構造のことを 抽象構文木 といいます。以下に示す木構造は上の構文解析木を抽象構文木に加工したものです。

では、これからいよいよ実際に抽象構文木を実装していきます。木構造のノードを表すのには基本ポインタ型を用いますが、実装言語がC++なのでその特徴を生かしてメモリ解放などをいちいち気にしなくて済むスマートポインタである std::shared_ptr を使いたいと思います。いちいちこの長い型名をタイプするのは面倒なので、グローバル空間で最初にエイリアス宣言をします。

1
2

template<class T>
using Ptr = std::shared_ptr<T>;

すると、それぞれのノードの型は次のように表すことができます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

//ノードの種類を表す列挙型
enum class NODETYPE{
    ADD, // +ノードを表す
    SUB, // -ノードを表す
    MUL, // *ノードを表す
    DIV, // /ノードを表す
    NUMBER,// 数字リテラルの末端ノードを表す
    NONE //無効なトークンを表す
};

class Node{
public:
    Ptr<Node> lhs, rhs;
    NODETYPE type;
    int num; //数字ノードの時に使う
    Node(){
        type = NODETYPE::NONE;
        num = -1;
    }
};

四則演算の場合抽象構文木は完全二分木なので、lhs と rhs で自分のノードの子ノードを表します。次にノードの追加などのユーティリティ関数を実装しようと思います。また、グローバル空間が汚染されないために構文解析で用いる関数群は全てラムダ式として Parse 関数のスコープ内で宣言します。またラムダ式の場合、宣言と初期化を分けられないので前方宣言の必要がある場合は std::function を使います。細かい仕様は各自リファレンスで調べてください。ユーティリティ関数を実装したのが ソース4 です。一応述べておくと、以下のコードは全て Parse 関数のスコープ内に記述されます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

size_t token_pos = 0; //今見ているトークンの番号

//もし今見ているトークンが引数の文字列と一致するならtoken_posをインクリメントしてtrueを返す
auto ConsumeByString = [&](std::string str)->bool {
    if (token_pos >= tokens.size())return false;
    if (tokens[token_pos].string == str) {
        ++token_pos;
        return true;
    }
    return false;
};

//lhsとrhsを子ノードに持つノードを返す
auto MakeBinaryNode = [](NODETYPE type, Ptr<Node> lhs, Ptr<Node> rhs)->Ptr<Node> {
    Ptr<Node> node = std::make_shared<Node>();
    node->type = type;
    node->lhs = lhs;
    node->rhs = rhs;
    return node;
};

//末端ノード(数字リテラルのノード)を返す関数
auto MakeNum = [](int num)->Ptr<Node> {
    Ptr<Node> node = std::make_shared<Node>();
    node->num = num;
    node->type = NODETYPE::NUMBER;
    return node;
};

ソース4 はやることをただ実装しているだけなのでコードを読み解くのはそこまで難しくないと思います。では、いよいよ構文木の真髄を実装します。まず、与えられたトークン列全体は ソース2 におけるExpr に分類可能です。逆に与えられたトークン列が式(Expr)として解釈できなかったらおかしいですよね？だって、今は式がコンパイラの入力として与えられているのですから。また、Expr は式全体を評価する以外にも Primary = Num | "(" Expr ")" という生成規則がある以上、別のところで例えば、より木が深くなった部分でも評価する必要があります。最も有名かつ手軽な手法が Expr, Mul, Primary, Num などのそれぞれのEBNFの要素を関数として実装する手法です。こうすることで再帰的な処理ができ、比較的楽に実装することができます。こうすることでそれぞれの生成規則の要素の相互関係を関数呼び出しで対応することができます。この手法を 再帰下降構文解析 といいます。式全体を Expr と決めつけてそのあとによりミクロな視座で部分を評価して木を伸ばすという性質を考えればこの名前の由来も合点がいきます。次の ソース4 がそれぞれのEBNFの要素を関数として実装したコードになります。ひと目見ただけじゃ本当にそれが機能するかどうかわからないと思いますが、この後に実際の例を用いて説明するので安心してください。また、これらの関数の実装の本質は ソース2 の生成規則なので適宜 ソース2 を参照してください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

std::function<Ptr<Node>(void)> Expr, Mul, Primary; //これらはお互いに他の関数を呼び出し合うこともあるので前方宣言をしておきます

Expr = [&]()->Ptr<Node>{
    //Exprは1個以上のMulが+もしくは-で結合されている

    Ptr<Node> node = Mul(); //この段階で1つのMulを読み込んだので後は+もしくは-が存在すればそのトークンを消費してMulを読み込む(5-1)
    for(;;){
        if(ConsumeByString("+"))node = MakeBinaryNode(NODETYPE::ADD, node, Mul());//(5-3)
        else if(ConsumeByString("-"))node = MakeBinaryNode(NODETYPE::SUB, node, Mul());
        else break;
    }
    return node;
};

Mul = [&]()->Ptr<Node>{
    //Mulは1個以上のPrimaryが*もしくは/で結合されている
    Ptr<Node> node = Primary();//(5-2)
    for(;;){
        if(ConsumeByString("*"))node = MakeBinaryNode(NODETYPE::MUL, node, Primary());
        else if(ConsumeByString("/"))node = MakeBinaryNode(NODETYPE::DIV, node, Primary());
        else break;
    }
    return node;
};

Primary = [&]()->Ptr<Node>{
    //Primaryは()でくくられたExprか、数字リテラルである
    Ptr<Node> node;
    if(ConsumeByString("(")){
        //もし(があったらそれはExprであるということ
        node = Expr();
        ConsumeByString(")");
    }else{
        //もし違ったら数字リテラルである
        assert(tokens[token_pos].type == TOKENTYPE::NUMBER); //(注)このようなアサーションを入れといたほうがデバッグなどがしやすいです
        node = MakeNum(std::stoi(tokens[token_pos].string));
        ++token_pos;
    }
    return node;
};

これらがそれぞれのEBNFの要素を関数として実装した結果です。また式全体すなわち与えられたトークン列は Expr としてみなすことができるので、最初に Expr 関数を呼び出します。それが ソース6 です。

1

Ptr<Node> program = Expr(); //全体の抽象構文木はprogramに格納される

{width=130 .img-right}

これを提示されただけではよくわからないと思うので具体例を出して一緒に考えてみましょう。今回は 4 * 2 + 3 * 7 という式について考えてみます。 まず ソース6 より Expr() が呼び出されます。そして今度は Expr() 内で Mul() が呼ばれます(ソース5の5-1のところ)。次に Mul() 内で Primary() が呼ばれます(ソース5の5-2のところ)。これらの呼び出し関係を図で表すと ソース7 のようになります。

画像内の矢印は戻り値を表しています。それぞれの関数は戻り値が Ptr<Node> のポインタ型なので木もしくはノード単体を表していることになります。(1)では Primary の実装を見ると数字リテラルのノードが帰ることになります。それをビジュアル化すると ソース8 になります。

また式を見ると 4 と 2 が * で結合されているので(2)では以下のような木構造が返されることになります。

この段階でようやく最初に呼ばれていた Expr 関数に戻りました。この時点で式全体 4 * 2 + 3 * 7 のうちの 4 * 2 までが処理されたことになります。またその後には + が続いているので、ソース5の5-3よりもう一度 Mul() が呼ばれることになります。またそこで以下のような木構造が返されます。

そして、Expr 関数内の node = MakeBinary(NODETYPE::ADD, node, Mul()); という処理によりこれらの２つの木が + 演算子のノードで結合されることになります。その結果が以下になります。

{width=500}

これで式全体 4 * 2 + 3 * 7 の読み込みが完了しました。これ以降はもう + も - も存在しないのでここで Expr の処理は打ち切られ上の木構造がそのまま program 変数に格納されることになります。これによってちゃんと式全体がEBNFの文法規則に従って抽象構文木に変換されたことになります。これが構文解析の全てです。後はEBNFの文法規則が複雑になるだけで、「それぞれの要素を関数として実装して再帰的な処理をする」という今までやってきた大まかな流れは変わりません。現に私が今実装しているコンパイラもこの流れを変えていません。みなさん、ここまでお疲れ様でした。次章ではこの章で作られた抽象構文木をもとに実際にアセンブリコードを出力してみましょう！

アセンブリで四則演算

本章では前章で構築した構文解析木をもとにアセンブリコードの出力を目標に実装していきます。 まずはスタックという概念について説明します。おそらくプログラマーの大半はスタックやキューといった言葉は一度くらい聞いたことがあると思います。Wikipediaにはスタックについてこのように書かれています。

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。

スタックとは誤解を恐れずに言うと、値を追加(Push)したり、コンテナ上の要素を削除(Pop)することができるデータ構造です。ここで重要なのは、要素が削除される場所が一意に定まるということです。以下のような{2, 3, 5, 7}と表されるスタックを考えてみてください。(ソース12)

スタックでは、値を追加するときは図の(1)方向でしか追加することができず、値を削除するときも基本的に(1)側にある要素しか削除しかできません。またキューの場合には値を削除するときは(2)側の要素しか削除できません。そしてコンテナの途中に値を割り込んで追加することもできません。これを不便に思うかもしれませんが、このことこそがスタックそしてキューの最大の特徴なのです。 次になぜコンパイラ作成の過程でスタックの概念が登場するのかを説明します。まず、前提としてどんなに複雑な式でも2項の計算の組み合わせとして計算することができます。前章で扱った 4 * 2 + 3 * 7 という式で考えてみましょう。 まず最初に 4 * 2 を計算して 8 という結果を得ます。次に 3 * 7 を計算して 21 という結果を得ます。そして最後に計算結果である 8 + 21 を計算して 29 という式全体の値を計算することができました。これが私が先程言った「どんなに複雑な式でも2項の計算の組み合わせとして計算」の意味です。 今、前章で扱った抽象構文木を思い出してみてください。あれらも、もし自分のノードが演算子のノードだったら必ず2つのノードを子として保持していますよね？必ずしもその子ノードが数字リテラルであるとは限りませんが。このような背景から式全体を計算するには、「数字リテラルすなわち末端ノードが現れるまで走査し、２つの子ノードを親ノードの演算子ノードに従って計算しそれを上に伝播すればよい」という方針が立ちます。ここでこの伝播を表現するのにスタックを用いるのです。では先程と同様に 4 * 2 + 3 * 7 の例で考えてみましょう。まず、構文木の頂点を起点として深さ優先探索(Depth-First Search)をします(深さ優先探索を知らない人は適当に各自で調べてください)。そして、子ノードがもし数字リテラルであればスタックにプッシュします。そうすることで * ノードを探索した後、スタックは次のようになります。

{width=100 .img-left}

そしてこの時、自分自身のノードは * であるので、スタックから2つの値をポップしてそれらに * 演算を施した結果を再度スタックにプッシュします。そして次はソース14で赤で囲った部分木にも同様の処理を施してあげるとスタックは ソース15 のようになります。

{width=100%}

そして、赤で囲った部分木の親は * なのでスタックから2つの値を同様にポップして計算した結果をスタックにプッシュするとスタックは以下になります。

最後に、抽象木全体の頂点は + ノードなのでスタックに残っている 8 と 21 に + 演算を施した結果をスタックにプッシュして次のような結果を得られます。

これが式全体の演算結果を抽象構文木に基づいて計算するアルゴリズムです。そしてこのアルゴリズムをアセンブリで表現する必要、すなわちその演算をするアセンブリコードを生成する必要があるのですが、それを実装するには多少のアセンブリの知識が必要なのでそれについてまず説明します。

そもそもx86-64のCPUにはスタック上で直接値の計算ができません。基本x86-64のCPUはレジスタと呼ばれるメモリよりも高速にアクセスが可能である記憶領域においての演算しか行いません。このコンピュータのことを レジスタマシン　と言います。 なので、私達は先程紹介したスタックの概念とレジスタの演算を結びつける必要があります。また、レジスタにはそれぞれ名前がついており、それぞれの役割が暗黙的に割り当てられています。以下に示す表が今回使うレジスタたちです。

汎用レジスタとは、用途が特に定まっておらずユーザーが様々な演算する際に値を記憶しておけるレジスタのことです。

では次にレジスタに対して演算を施すCPUの命令を紹介します。アセンブリのコードはこれらの命令の連続であると考えることができます。

割り算の命令だけは書かなかったのですが、これはなぜかというと除算命令は他の四則演算と仕様が違うので同列に書けなかったからです。除算命令を実装したいときは代わりに以下のコードを使ってください。

1
2

cqo
idiv rdi

これの詳細を知りたい人はググってください。

これで準備が整いました。実際に 4 * 2 + 3 * 7 を計算するアセンブリコードを書いてみましょう。以下に示すのはあくまでアセンブリのコードであり、今まで紹介してきたC++のコードとは全く別物なので勘違いしないでください。

ソース18

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

.intel_syntax noprefix
.global main
main:
    #アセンブリの場合エントリポイントはmainなのでその中で処理を書く
    push 4
    push 2

    pop rdi
    pop rax
    #この段階でrdiには2, raxには4が格納されている

    imul rax, rdi #ここで4 * 2の演算を実行して8がraxに新たに保存される
    push rax #そして8をスタックにプッシュ

    push 3
    push 7
    #この段階でスタックは{ 8, 3, 7 }という並びになっている

    pop rdi
    pop rax
    #この段階でrdiには7, raxには3が格納されています

    imul rax, rdi #ここで3 * 7の演算を実行して21がraxに新たに保存される
    push rax #21をスタックにプッシュ
    #この時点でスタックは{8, 21}という並びになっている

    pop rdi
    pop rax
    add rax, rdi #ここで8 + 21 = 29が計算され、結果がraxに保存される
    ret

はい、ここまでで計算結果がraxレジスタに保存されるという状態を実現できました。そしてこのコードでは ret 命令を追加してmain関数の戻り値として計算結果を返すようにしました。では実際にWSLのターミナルで本当に計算結果が帰ってくるのか確認してみましょう。 では、上記のコードを test.s として保存してください。そしてこのアセンブリコードを cc -o test test.s というコマンドでアセンブルして、 test という実行ファイルを生成します。その後、 ./test でアセンブルした実行ファイルを実行します。 最後に echo \(? を実行します。このコマンドは直前に実行したプログラムの戻り値を表示するコマンドです。 これらをWSL上で実行すると、なんと、実際に29が表示されました！ 自分のプログラムしたものがこうやって形として現れると嬉しいですよね。

{width=100%}

アセンブリコードの自動生成

いよいよ、この章では6章と7章で学んだことを総動員してコンパイラ最後の砦、アセンブリコードの生成を実装していきます。これを実装すれば4章で説明したコンパイルのフローがすべて実装されたことになりました。後は構文などのプログラミング言語の要素を追加していくたびにこれらのフローのそれぞれの要素に追加で実装すればいいので、今章で大まかな全体としてのプログラムは完成することになります。まあこの後も様々困難が待ち構えているのですが。。。 ここではC++で前章で取り扱ったようなアセンブリコードを自動生成できるように実装をするのですが、大まかな方針は既に前章で紹介しています。「数字リテラルすなわち末端ノードが現れるまで走査し、２つの子ノードを親ノードの演算子ノードに従って計算しそれを上に伝播すればよい」ということです。これだけ言われてもやはりピンとこないと思うので丁寧に説明していきます。まず抽象構文木の特徴でもあるのですが、末端ノード以外、すなわち数字リテラル以外のノードは以下の構造をとっています。

この場合、「自分」は子ノードを2つ持っているので必ず演算子ノードです。また「子1」、「子2」は数字ノードであるとは限りません。しかし、抽象構文木の頂点から深さ優先探索をして末端に行けば必ず「子1」と「子2」が数字ノードである部分木が1つ以上は存在します。なぜならどんなに複雑な式であっても必ず△ + △ のような2項からなる式の組み合わせにすぎないからです。これらのことから、もし子ノードが数字だったらその値をプッシュ、でなければ走査を続けるといったようなコードを実装すれば良いことになります。C++でこれを実装すると以下のようになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

int GenerateAssembly(){

    //生成するアセンブリコードはここに格納する
    std::string res = ".intel_syntax noprefix\n.global main\nmain:\n";

    //構文木を再帰的に走査する関数。再帰呼び出しをするのでこの命名をしたけどあんまり気に入ってない
    std::function<void(Ptr<Node>)> Recursive;

    Recursive = [&](Ptr<Node> node){

        //もし今走査しているノードが数字ノードだったらその値をプッシュ
        if(node->type == NODETYPE::NUMBER){
            res += ("\tpush " + std::to_string(node->num) + "\n");
            return;
        }

        //子ノードについても同様の走査をする
        Recursive(node->data[0]);
        Recursive(node->data[1]);

        //この段階で2つの値がスタックトップに存在しているはず。
        res += "\tpop rdi\n";
        res += "\tpop rax\n";

        switch(node->type){
        case NODETYPE::ADD:
            res += "\tadd rax, rdi\n";
            break;
        case NODETYPE::SUB:
            res += "\tsub rax, rdi\n";
            break;
        case NODETYPE::MUL:
            res += "\timul rax, rdi\n";
            break;
        case NODETYPE::DIV:
            res += "\tcqo\n";
            res += "\tidiv rdi\n";
            break;
        }

        //最後に計算結果をプッシュ
        res += "push rax\n";

    };

    //構文木の頂点から走査を始める
    Recursive(program);

    //計算結果をraxにポップする
    res += "\tpop rax\n";

    //最後に計算結果をプログラムの戻り値として返す
    res += "\tret\n";

    return 0;

}

これで実際にプログラムに 4 * 2 + 1 という式を入力として与えて std::cout << res; で生成されたアセンブリコードを実際に出力させると以下が得られます。

{width=200}

これでようやくコンパイラの体裁をなして来ました。後は得られたアセンブリコードをコンパイラ内部でアセンブルして実行ファイルを生成するところまでやっていきましょう。以下のような関数を実装してください。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int Assemble() {
    //出力されたアセンブリコードをresult.sに保存する
    std::ofstream assembly_file{ "result.s" };
    assembly_file << assembly_code;
    assembly_file.close();

    //result.sをバイナリファイルに変換する
    int res = system("wsl cc -o result result.s");

    //もしccコマンドが正常終了しなかったらエラーログを出す
    if (res != 0)std::cout << "Assembling didn't go well.\n";

    return 0;
}

int Run() {
    //resに式の演算結果が保存されるのでそれを出力
    int res = system("wsl ./result");
    std::cout << res << "\n";
    return 0;
}

このコードはコンパイラ実装の本流とは関係ないので説明は省略します。 よって、 main 関数内の関数呼び出しの順番は

1
2
3
4
5
6
7
8
9

Tokenize
↓
Parse
↓
GenerateAssembly
↓
Assemble
↓
Run

となります。 ここまで、コンパイラ作成のおおまかな流れを解説しましたが、いかがでしたでしょうか？C++を使った実際の実装はここまでとしたいと思います。これから変数などのいわゆる「プログラミング言語」らしい機能を紹介したいと思いますが、これらの実装を詳しく説明するのは流石に骨が折れるので、概要だけお話したいと思います。

比較演算子

ここでは比較演算子を説明して　12 > 2 などの真の条件式が与えられたら1を、1 == 2などの偽の条件式が与えられたら0を返せるようにします。構文解析木の実装方法は前章で丁寧に扱ったのでそこの部分はEBNFの変更点だけを説明します。まず、最上の階層で expr を使いたいので既存のEBNFを以下のように書き換えます。

1
2
3

add = mul ( "+" mul | "-" mul )*
mul = primary ( "*" primary | "/" primary )*
primary

また、 == よりも > などの不等号のほうが先に結合します(例: 1 == 4 > 1 の場合、4 > 1 が先に1と評価され、その次に 1 == 1 が評価されます)。MSVCなどのコンパイラで実際に ソース25 のようなコードをコンパイルすると false が帰るのでやはり == より > が先に結合されることがわかります(もし2 == 2 が先に評価されるのであれば、 true が帰るはずです)。

ソース25

このことを考慮すると以下のようなEBNFを新たに追加すればいいとわかります。

1
2
3

expr = equality
equality = relational ( "==" relational | "!=" relational )*
relational = add ( "<" add | "<=" add | ">" add | ">=" add )*

このようなEBNFを設計することで 12 などの数字単体からなる式や、 1 + 1 > 0 などの不等式や、 2(3 + 4) > 10 == 1 などのような不等号と等号を混ぜた式まで構文解析できるようになります。ここまでの段階で比較演算子に対応した Parse() を実装することができます。 次に比較演算子に対応した GenerateAssembly() すなわちアセンブリコードの生成の実装を説明します。 基本は四則演算のアセンブリ生成と同じ流れです。木全体を走査して、 + ノードであれば add 命令を生成するのと同様に > や == ノードであればそれに対応したアセンブリの命令を生成すればよいです。以下にその命令を示します。

ただしここで一つ注意があります。上の表で al というレジスタを用いましたが、実はこれは頻繁に使う整数レジスタ rax の下位8bitに割り当てられた別名レジスタに過ぎないのです。従って比較結果をraxに格納したい場合は残りの56bitを0で埋める必要があります。それを行ってくれるのが movzb 命令です。なお、ここでは > と >= に対応する命令を紹介していませんが、単に構文解析時に右辺と左辺を入れ替えれば > や >= は < や <= に置換可能です。A > B はB < A と同値であるからです。

以上を踏まえて実装すると以下のようになります(掲載しているのは GenerateAssembly 関数のswitch 文の新規ラベルです)。ちなみに構文解析木では、==, !=, <, <= がそれぞれ NODETYPE::EQUAL, NODETYPE::NOT_EQUAL, NODETYPE::LESS, NODETYPE::LESS_OR_EQUAL に対応しています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

case NODETYPE::EQUAL:
    //ここが処理されている段階で `A == B` のAがraxレジスタに、Bがrdiレジスタに格納されている
    res += "\tcmp rax, rdi\n";
    res += "\tsete al\n";
    res += "\tmovzb rax, al\n";
    break;
case NODETYPE::NOT_EQUAL:
    //以下同様に実装していく
    res += "\tcmp rax, rdi\n";
    res += "\tsetne al\n";
    res += "\tmovzb rax, al\n";
    break;
case NODETYPE::LESS:
    res += "\tcmp rax, rdi\n";
    res += "\tsetl al\n";
    res += "\tmovzb rax, al\n";
    break;
case NODETYPE::LESS_OR_EQUAL:
    res += "\tcmp rax, rdi\n";
    res += "\tsetle al\n";
    res += "\tmovzb rax, al\n";
    break;

今まで長々と説明してきましたがいざ実装すると意外とあっけなかったですね。ここまで以下のようなコードがコンパイルできるようになります。

1

1 == 1 <= 0

おわりに

さあ、ここまで比較演算子の実装まで終わりました。私はC言語の主要な機能(ローカル変数、関数、ポインタなど)を実装したのですが、私が今これを執筆しているのが2021年9月25日で、時間がキツキツになっているのでここで終わりとしたいと思います。今回の部誌でコンパイラについて興味を持ってくれる人がいたら幸いです。もし、私のコードの全体が見たい人がいたら1章に載せたメールアドレスに連絡してください。読んでいただきありがとうございました！！