はじめに

このオンラインブックは執筆中です。完成版ではありません。

この本には一冊の本に盛り込むにはやや欲張りな内容を詰め込みました。本書では、C言語で書かれたソースコードをアセンブリにコンパイルするコンパイラ、つまりCコンパイラを作成します。コンパイラそのものもCを使って開発します。当面の目標はセルフホスト ―― すなわち自作コンパイラでそれ自身のソースコードをコンパイルできるようにすることです。

この本では、コンパイラの理論の学習曲線が急峻になりすぎないように、様々なトピックを本書全体を通じて次第に掘り下げていくという形で説明することにしました。その理由は次のとおりです。

コンパイラは、構文解析、意味解析、コード生成といった複数のステージに概念的に分割することができます。よくある教科書的アプローチでは、それぞれのトピックについて章を立てて解説を行うことになります。そのようなアプローチの本は、話が途中で高度になりすぎて読み通すのが辛いことがあります。その結果として、本の最初に書いてあった構文解析の、最初のほうに書いてあったテクニックだけはわかるけど……といった状態になることがよくあります。

また、こういった開発手法では、全てのステージが完成するまでコンパイラを動かしてみることができないので、全体が動き始めるまでどこかが決定的に間違っていても気づくことができません。そもそも次のステージの入力としてなにが期待されているのか、自分で作ってみるまでよくわからないので、あるステージで何を出力すればよいのかもよくわからないのです。また、完成するまで何のコードもまったくコンパイルできないのでモチベーションを保つのが困難という問題もあります。

本書ではその罠を避けるために別のアプローチをとることにしました。この本の最初のほうで、読者はごく簡単な言語仕様の「独自言語」を実装することになります。その言語はあまりにも簡単なので、それを実装する時点では、それほどコンパイラの作り方について詳しく知っている必要はありません。その後、読者は本書を通じて「独自言語」に機能を追加していって、最終的にそれをC言語と一致するものに育て上げることになります。

そのようなインクリメンタルな開発手法では、細かいコミットを刻みつつ、ステップ・バイ・ステップでコンパイラを作っていくことになります。この開発手法では、どのコミットにおいてもコンパイラはある意味常に「完成形」です。ある段階ではただの電卓レベルのことしかできないかもしれないし、ある段階では相当簡略化されたCのサブセットのような言語が扱えるコンパイラかもしれないし、ある段階ではほとんどCといってよいけど欠けている機能があるかもしれない、というようになります。ポイントは、どの段階でも、その時点の完成度に合わせたレベルできちんとある意味使い物になるということです。別の言い方をすれば、ものすごく簡単な自作言語のコンパイラを作り、それに次第にCぽい方向に向かって機能追加を繰り返していくことで、最終的に自作言語をCと同じものにする、ということを行います。一部の機能だけを突出してC言語ぽくすることはせず、どのステップにおいても、それなりにリーズナブルな、無理のない仕様の言語として、ある意味きちんと使い物になるようなものを作成します。

インクリメンタルな開発では、本書を読んでいるどの時点においても、読者はそこまでのレベルにおいてのリーズナブルな言語の作り方の知識をまんべんなく持っている、ということが達成されることになります。これはコンパイラ作成の一部のトピックだけ極端に偏って詳しい状態よりずっとよい状態です。そして、本書を読み終わることには、すべてのトピックについてまんべなく知識が得られていることでしょう。

また、この本は、大きなプログラムを1から書くにはどうすればよいのかということを説明している本でもあります。大きなプログラムを作るスキルというのは、データ構造やアルゴリズムを学ぶのとはまた違った一種独特のスキルなのですが、そういったものを解説している本はあまりないように思います。また、仮に解説してもらっても、実際に体験してみなければピンとこないでしょう。本書は、自作言語をC言語に育てていくプロセスがその実体験になりうるようにデザインされています。

筆者の目論見が成功していれば、この本を読むことで、読者はコンパイラ作成のテクニックやCPU命令セットの知識だけではなく、大きなプログラムを小さなステップにわけて少しづつ作っていく方法や、ソフトウェアテストの手法、バージョン管理の手法、そしてコンパイラ作成のような野心的なプロジェクトに取り組むときの心がけすら学ぶことができるはずです。

この本の想定読者は普通のCプログラマです。Cの言語仕様を熟知しているスーパーCプログラマである必要はありません。ポインタや配列が理解できており、他人の書いた小規模なCプログラムを、少なくとも時間をかければ読める、というレベルであれば十分です。

それに加えて、言語仕様やCPUの仕様については、単に仕様を説明するだけではなく、なぜそのようなデザインが選ばれたのかについての解説をできる限り行うようにしました。また、読者の興味を引くようなコンパイラやCPU、コンピュータ業界や歴史についてのコラムを散りばめて、楽しく読み進められるように心がけました。

コンパイラ作成は大変楽しい作業です。最初のころはバカバカしいくらい単純なことしかできなかった「自作言語」のためのコンパイラが、開発を続けていくとたちまちのうちに自分でも驚くくらいC言語っぽく成長していって、まるで魔法のようにうまく動くようになります。実際に開発をしてみると、現時点でうまくコンパイルできるとは思えない大きめのテストコードがエラーなしにコンパイルできて、完全に正しく動くことに驚くことがよくあります。そういうコードはコンパイル結果のアセンブリを見ても自分ではまったく理解できません。時折、自作のコンパイラが作者である自分を超える知性を持っているように感じることすらあります。コンパイラは仕組みがわかっていても、どことなく、なぜここまでうまく動くのか不思議な感じがするプログラムです。きっとあなたもその魅力に夢中になることでしょう。

さて、前置きはこれくらいにして、さっそく筆者と一緒にコンパイラ開発の世界に飛び込んでみましょう！

本書の想定する開発環境

本書では開発環境として、IntelやAMDなどのいわゆる普通のPCで動く64ビットのLinux環境を想定します。読者がお使いのディストリビューションに合わせてgccやmakeといった開発ツールをあらかじめインストールしておいてください。

Intel CPU上のmacOSはアセンブリのソースレベルでLinuxとほぼ互換性があり、この本の内容をほぼそのまま適用することができます。macOSがLinuxと異なる箇所については適時説明を行います。macOSを利用する場合は、標準開発環境のXcodeを事前にインストールしておいてください。

WindowsはLinuxとはアセンブリのソースレベルで互換性がありません。ただし、Windows 10ではLinuxを1つのアプリケーションのようにWindows上で動作させることが可能で、それを使うことでWindows上で開発を進めていくことができます。Windows Sysbsystem for Linux（WSL）というアプリケーションがそのLinux互換環境の名前です。本書の内容をWindowsで実践するときは、WSLをインストールして、その中で開発を進めるようにしてください。

本書の表記法

関数や式、コマンドなどは本文中でmainやfoo=3、makeのように等幅フォントで表示します。

複数行に渡るコードは、次のように等幅フォントを使って枠の中の中に表示します。

int main() {
  printf("Hello world!\n");
  return 0;
}

ユーザがそのまま入力することを想定しているシェルコマンドの場合、$から始まる行はプロンプトを意味しています。その行の$以降をシェルに入力してください（$そのものは入力しないようにしてください）。$以外の行は、入力したコマンドからの出力を表しています。例えば下のブロックは、ユーザがmakeという文字列を入力してエンターを押した場合の実行例です。makeコマンドからの出力はmake: Nothing to be done for `all'.です。

$ make
make: Nothing to be done for `all'.

機械語とアセンブラ

この章では、コンピュータを構成するコンポーネントと、我々が作成するCコンパイラからどのようなコードを出力すればよいのかということについて、大雑把なイメージをつかむことを目標とします。具体的なCPUの命令などについてはまだ深入りはしません。まずは概念を把握することが重要です。

CPUとメモリ

コンピュータを構成するコンポーネントは、大まかにいうとCPUとメモリにわけることができます。メモリはデータを保持できるデバイスで、CPUは、そのメモリを読み書きしながら何らかの処理を行なっていくデバイスです。概念的に、CPUにとってはメモリはランダムアクセス可能な巨大なバイト（Cでいうところのchar型）の配列のように見えます。CPUがメモリにアクセスするときは、メモリの何バイト目にアクセスしたいのかという情報を数値で指定するわけですが、その数値のことを「アドレス」といいます。例えば「アドレス16から8バイトのデータを読む」というのは、バイトの配列のように見えているメモリの16バイト目から8バイト分のデータを読む、という意味です。同じことを「16番地から8倍とのデータを読む」ということもあります。

CPUが実行するプログラムと、そのプログラムが読み書きするデータは、どちらもメモリに入っています。CPUは「現在実行中の命令のアドレス」をCPU内部に保持していて、そのアドレスから命令を読み出して、そこに書かれていることを行い、そして次の命令を読み出して実行する、ということを行なっています。その現在実行中の命令のアドレスのことを「プログラムカウンタ」（PC）や「インストラクションカウンタ」（IP）といいます。CPUが実行するプログラムの形式そのもののことを「機械語」といいます。

プログラムカウンタは必ずしも直線的に次の命令だけに進んでいくわけではありません。CPUの「分岐命令」と呼ばれる命令を使うと、プログラムカウンタを、次の命令以外の任意のアドレスに設定することができます。この機能によってif文などが実現されています。プログラムカウンタを次の命令以外の場所に設定することを「ジャンプする」あるいは「分岐する」と表現することがあります。

CPUはプログラムカウンタのほかにも、少数のデータ保存領域を持っています。例えばIntelやAMDのプロセッサには、64ビット整数が保持できる領域が16個あります。この領域のことを「レジスタ」と呼びます。メモリはCPUからみて外部の装置で、それを読み書きするには多少の時間がかかりますが、レジスタはCPU内部に存在していて、ディレイなしにアクセスすることができます。

多くのCPU命令は、2つのレジスタの値を使って何らかの演算を行なって、その結果をレジスタに書き戻すというフォーマットになっています。したがってプログラムの実行というものは、CPUがメモリからレジスタにデータを読み込んできて、レジスタとレジスタの間でなんらかの演算を行い、その結果をメモリに書き戻す、ということで実行が進んでいくことになります。

特定の機械語の命令を総称として「命令セット」とといいます。命令セットは一種類というわけではなく、CPUごとに好きにデザインしてかまいません。とはいえ、機械語レベルの互換性がないと同じプログラムを動かせないので、命令セットのバリエーションはそれほど多くありません。PCではIntelやその互換チップメーカーであるAMDの、x86-64と呼ばれる命令セットが使われています。x86-64は主要な命令セットの1つですが、x86-64だけが市場を独占しているというわけではありません。例えばiPhoneやAndroidではARMという命令セットが使われてます。

アセンブラとは

機械語はCPUが直接読んでいくものですから、CPUの都合だけが考慮されていて、人間にとっての扱いやすさというものは考慮されていません。こういった機械語をバイナリエディタで書いていくのは、不可能というわけではないものの、とても辛い作業です。そこで発明されたのがアセンブラです。アセンブリは機械語にほぼそのまま1対1で対応するような言語なのですが、機械語よりもはるかに人間にとって読みやすいものになっています。

アセンブリのコードを機械語に変換するのは「コンパイルする」ということもありますが、入力がアセンブリであることを強調して特別に「アセンブルする」ということもあります。

仮想マシンやインタープリタではなくネイティブなバイナリを出力するコンパイラの場合、アセンブリを出力することが目標になります。本書で作るCコンパイラもアセンブリを出力します。

読者はアセンブリをいままでにどこかで見たことがあるかもしれません。もしアセンブリを見たことがなければ、今が見てみるよい機会です。objdumpコマンドを使って、適当な実行ファイルを逆アセンブルして、そのファイルの中に入っている機械語をアセンブリとして表示してみましょう。以下はlsコマンドを逆アセンブルしてみた結果です。

$ objdump -d -M intel /bin/ls
/bin/ls:     file format elf64-x86-64

Disassembly of section .init:

0000000000003d58 <_init@@Base>:
  3d58:  48 83 ec 08           sub    rsp,0x8
  3d5c:  48 8b 05 7d b9 21 00  mov    rax,QWORD PTR [rip+0x21b97d]
  3d63:  48 85 c0              test   rax,rax
  3d66:  74 02                 je     366a <_init@@Base+0x12>
  3d68:  ff d0                 call   rax
  3d6a:  48 83 c4 08           add    rsp,0x8
  3d6e:  c3                    ret
...

筆者の環境ではlsコマンドには2万個ほどの機械語命令が含まれているので、逆アセンブルした結果も2万行近い長大なものになります。ここでは最初のごく一部だけを掲載しました。

アセンブリでは、基本的に機械語1個につき1行という構成になっています。例として次の行に着目してみましょう。

  3d58:  48 83 ec 08           sub    rsp,0x8

この行の意味は何でしょうか？ 3d58というのは、機械語が入っているメモリのアドレスです。つまり、lsコマンドが実行されるとき、この行の命令はメモリの0x3d58番地に置かれるようになっていて、プログラムカウンタが3d58のときにこの命令が実行されることになります。その次に続いている4つの16進数の数値は実際の機械語です。CPUはこのデータを読んで、それを命令として実行します。sub rsp,0x8というのは、その機械語命令に対応するアセンブリです。CPUの命令セットについては章を分けて説明しますが、この命令は、RSPというレジスタから8を引く（subtract = 引く）という命令です。

Cとそれに対応するアセンブラ

簡単な例

Cコンパイラがどのような出力を生成しているのかというイメージを掴むために、Cコンパイラが出力するアセンブリコードを少し見てみましょう。最も簡単な例として次のプログラムを考えてみます。

int main() {
  return 42;
}

このプログラムが書かれているファイルをtest1.cとすると、次のようにしてコンパイルして、mainが実際に42を返していることを確認することができます。

$ gcc -o test test1.c
$ ./test1
$ echo $?
42

Cではmain関数が返した値はプログラム全体としての終了コードになります。プログラムの終了コードは画面に表示されることはありませんが、暗黙のうちにシェルの$?という変数にセットされているので、コマンド終了直後に$?をechoで表示することで、そのコマンドの終了コードを見ることができます。ここでは正しく42が返されていることがわかります。

さて、このCプログラムに対応するアセンブリプログラムは次の通りです。

.global main
main:
        mov rax, 42
        ret

このアセンブリでは、グローバルなラベルmainが定義されていて、ラベルのあとにmain関数のコードが続いています。ここでは42という値を、RAXというレジスタにセットし、mainからリターンしています。整数を入れられるレジスタはRAXを含めて合計で16個あるのですが、関数からリターンしたときにRAXに入っている値が関数の返り値という約束になっているので、ここではRAXに値をセットしています。

このアセンブリプログラムを実際にアセンブルして動かしてみましょう。アセンブリファイルの拡張子は.sなので、上のアセンブリコードをtest2.sに記述して、次のコマンドを実行してみてください。

$ gcc -o test2 test2.s
$ ./test2
$ echo $?
42

Cのときと同じように42が終了コードになりました。

大雑把にいうと、Cコンパイラは、test1.cのようなCコードを読み込んで、test2.sのようなアセンブリを出力するプログラムということになります。

関数呼び出しを含む例

もう少し複雑な例として、関数呼び出しのあるコードがどのようなアセンブリに変換されるのかを見てみましょう。

関数呼び出しは単なるジャンプとは異なり、呼び出した関数が終了した後に、元々実行していた場所に戻ってこなければいけません。元々実行していたアドレスのことを「リターンアドレス」といいます。仮に関数呼び出しが1段しかなければ、リターンアドレスはCPUの適当なレジスタに保存しておけばよいのですが、実際には関数呼び出しはいくらでも深くできるので、リターンアドレスはメモリに保存しないわけにはいきません。

リターンアドレスはスタックになっています。スタックというのはデータ構造の名前で、テーブルに積まれた本のように、一番上にさらにデータを積んだり、あるいは一番上からデータを取り出したりできるようになっています。スタックにデータを積むことを「プッシュ」、その逆に一番上にあるデータを取り除くことを「ポップ」といいます。

スタックはアドレスを保持する1つの変数のみを使って実装することができます。そのアドレスを常にスタックの一番上のデータを指しているようにします。プッシュするためには、プッシュするデータの大きさだけアドレスを減らして、そのアドレスにデータをコピーします。ポップするときは、現在のアドレスからデータを読み込んで、そのデータの大きさだけアドレスを増やします。一番上のデータのアドレスを保持している記憶領域のことを「スタックポインタ」といいます。x86-64には、関数を使ったプログラミングをサポートするために、スタックポインタ専用のレジスタと、そのレジスタを利用する命令をサポートしています。

さて、関数呼び出しの実例を見てみましょう。次のCコードを考えてみてください。

int plus(int x, int y) {
  return x + y;
}

int main() {
  return plus(3, 4);
}

このCコードに対応するアセンブリは次のようになります。

.global plus, main

plus:
        add rsi, rdi
        mov rax, rsi
        ret

main:
        mov rdi, 3
        mov rsi, 4
        call plus
        ret

1行目の.globalから始まる行は、plusとmainという2つの関数がファイルスコープではなくプログラム全体から見える関数であるという意味です（関数定義にstaticをつけるとグローバルではなくなります）。これはさしあたり無視してかまいません。

まずmainに着目してみてください。Cではmainからplusを引数つきで呼び出しています。アセンブラにおいては、第一引数はRDIレジスタ、第二引数はRSIレジスタに入れるという約束になっているので、mainの最初の2行でそのとおりに値をセットしています。

callというのは関数を呼び出す命令です。具体的にcallが行うのは次のことです。

• callの次の命令のアドレスをスタックにプッシュ
• callの引数として与えられたアドレスにジャンプ

したがってcall命令が実行されると、CPUはplus関数を実行し始めることになります。plus関数に着目してください。plus関数には3つの命令があります。

addは足し算を行う命令です。この場合には、RDIレジスタとRSIレジスタを足した結果がRSIレジスタに書き込まれます。x86-64の整数演算命令は、通常2つのレジスタしか受け取らないので、どちらかのレジスタの値を上書きする形で結果が書き込まれることになります。

関数からの返り値はRAXに入れるということになってました。したがって足し算の結果はRAXに入れておきたいので、RSIからRAXに値をコピーする必要があります。ここではmov命令を使ってそれを行なっています。movはmoveの省略形ですが、実際にはデータを移動するのではなくコピーする命令です。

plus関数の最後では、retを呼んで関数からリターンしています。具体的にretが行うのは次のことです。

• スタックからアドレスを1つポップ
• そのアドレスにジャンプ

つまりretは、callが行なったことを元に戻して、呼び出し元の関数の実行を再開する命令です。このようにcallとretは対になる命令として定義されています。

plusからリターンしたところにあるのはmainのret命令です。元のCコードではplusの返り値をそのままmainから返すということになっていました。ここではplusの返り値がRAXに入った状態になっているので、そのままmainからリターンすることで、それをそのままmainからの返り値にすることができます。

本章のまとめ

本章ではコンピュータが内部でどのように動いているのかということと、Cコンパイラが何をすればよいのかということについて、概要を説明しました。機械語やアセンブリを見ると、Cとはかけ離れた、ごちゃっとしたデータの塊のように見えますが、意外とある意味でCの構造を素直に反映していると思った読者も多いのではないでしょうか。

まだ本書では具体的なCPU命令についてほとんど説明していないので、objdumpで表示されたアセンブリコードについて1つ1つの命令はわからないと思いますが、なんとなくなにをやっていそうなのかということについは、勘が効くようになったのではないでしょうか。本章の段階ではそういう勘が効くようになれば十分です。

本章のポイントを箇条書きで下にまとめます。

• CPUはメモリを読み書きすることでプログラムの実行を進めていく
• CPUが実行するプログラムと、そのプログラムが扱うデータはどちらもメモリに入っていて、CPUはメモリから順に機械語命令を読み、その命令を実行する
• CPUにはレジスタという小さな記憶領域があり、多くのCPU命令はレジスタ間での操作として定義されている
• アセンブリは機械語を人間にとって読みやすくした言語で、Cコンパイラはアセンブリを出力する
• 関数呼び出しはスタックを使って実装されている

ステップ1：整数1個をコンパイルする言語の作成

最もシンプルなC言語のサブセットを考えてみてください。読者の皆さんはどういう言語を想像するでしょうか？ main関数しかない言語でしょうか。あるいは式1つだけからなる言語でしょうか。突き詰めて考えると、整数1つだけからなる言語というものが、考えうる限り最も簡単なサブセットだといってよいと思います。したがってこのステップではまずその言語を実装します。

このステップで作成するプログラムは、1個の数を入力から読んで、その数をプログラムを終了コードとして終了するアセンブリを出力するコンパイラです。つまり入力は単に42のような文字列で、それを読むと次のようなアセンブリを出力するコンパイラです。

.intel_syntax noprefix
.global main

main:
        mov rax, 42
        ret

.intel_syntax noprefixというのは、複数あるアセンブリの書き方のなかで、本書で使っているIntel記法という記法を選ぶためのアセンブラコマンドです。今回作成するコンパイラでは必ず冒頭にこの行をお約束として入れるようにしてください。それ以外の行は、[第1章]で説明した通りです。

読者はここで、「こんなプログラムはコンパイラとは言えない」と思うかもしれません。筆者も正直そう思います。しかし、このプログラムは、数値1つからなる言語を入力として受け付けて、出力としてその数値に対応したコードを出力するというもので、それはコンパイラの定義から言うと立派なコンパイラです。このような簡単なプログラムも、改造していくとすぐにかなり難しいことができるようになるので、まずはこのステップを完了してみましょう。

実はこのステップは、開発全体の手順からみてみるととても重要です。このステップで作るものをスケルトンとして使って今後開発を進めていくからです。このステップでは、コンパイラ本体の作成に加えて、ビルドファイル（Makefile）、ユニットテストの作成、gitリポジトリのセットアップも行います。それらの作業について1つ1つ見ていきましょう。

なお、本書で作るCコンパイラは9ccと名前です。ccというのはC compilerの略称です。9という数字に特に意味はないのですが、筆者の以前につくったCコンパイラが8ccという名前なので、それの次の作品ということで9ccという名前にしました。もちろんみなさんは好きな名前をつけてもらってかいません。ただし、事前に名前を考えすぎてコンパイラ作成が始められないということはないようにしましょう。Githubのリポジトリも含め、名前は後から変えられるので、適当な名前で初めて問題ありません。

mov rbp, rsp   // Intel
mov %rsp, %rbp // AT&T

mov [rbp + rcx * 4 - 8], rax // Intel
mov -8(rbp, rcx, 4), %rax    // AT&T

コンパイラ本体の作成

コンパイラには通常はファイルとして入力を与えますが、ここではファイルIOをするのが面倒なので、コマンドの第1引数に直接コードを与えることにします。第1引数を数値として読み込んで、定型文のアセンブリの中に埋め込むCプログラムは、次のように簡単に書くことができます。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
  printf("  mov rax, %d\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

9ccという空のディレクトリを作って、その中に9cc.cというファイルを上記の内容で作成します。そのあと下のように9ccを実行して動作を確認してみましょう。

$ gcc -o 9cc 9cc.c
$ ./9cc 123 > tmp.s

1行目で9cc.cをコンパイルして9ccという実行ファイルを作成しています。2行目では123という入力を9ccに渡してアセンブリを生成し、それをtmp.sというファイルに書き込んでいます。tmp.sの内容を確認してみましょう。

.intel_syntax noprefix
.global main
main:
  mov rax, 123
  ret

見ての通りうまく生成されていますね。こうしてできたアセンブリファイルをアセンブラに渡すと実行ファイルを作成することができます。

Unixにおいてはcc（あるいはgcc）は、CやC++だけではなく多くの言語のフロントエンドということになっていて、与えられたファイルの拡張子で言語を判定してコンパイラやアセンブラを起動するということになっています。したがってここでは9ccをコンパイルしたときと同じように、.sという拡張子のアセンブラファイルをgccに渡すと、アセンブルをすることができます。以下はアセンブルを行い、生成された実行ファイルを実行してみた例です。

$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
123

シェルでは直前のコードの終了コードが$?という変数でアクセスできるのでした。上の例では、9ccに与えた引数と同じ123という数字が表示されています。つまりうまく動いているということです。0〜255の範囲の123以外の数を与えてみて（Unixの終了コードは0〜255ということになっています）、実際に9ccがうまく動くことを確認してみてください。

ユニットテストの作成

趣味のプログラミングでテストを書いたことがない読者も多いと思いますが、本書ではコンパイラを拡張するたびに、新しいコードをテストするコードを書くことにします。テストを書くのは最初は面倒に感じるかもしれませんが、すぐにテストのありがたみがわかるようになるはずです。テストコードを書かなかった場合、結局は同じテストを手で毎回走らせて動作確認をするしかないわけですが、そちらのほうが圧倒的に面倒なのです。

テストが面倒だという印象の多くの部分は、テストフレームワークが大げさであったり、テストの思想が時に教条的であるところからきていると思います。例えばJUnitやxUnitのようなテストのフレームワークはいろいろな便利な機能を持っていますが、導入するのも使い方を覚えるの面倒です。したがってこの章ではそういったテストフレームワークを導入することはしません。インクリメンタルに、手書きのとても簡単な「テストフレームワーク」をシェルスクリプトで書いて、それを使ってテストを書くことにします。

以下にテスト用のシェルスクリプトtest.shを示します。シェル関数tryは、引数を入力の値と、期待される出力の値という2つの引数を受け取って、実際に9ccの結果をアセンブルし、実際の結果を期待されている値と比較するということを行います。シェルスクリプトでは、try関数を定義した後に、それを使って0と42がどちらも正しくコンパイルできることを確認しています。

#!/bin/bash
try() {
  expected="$1"
  input="$2"

  ./9cc "$input" > tmp.s
  gcc -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" != "$expected" ]; then
    echo "$input expected, but got $actual"
    exit 1
  fi
}

try 0 0
try 42 42

echo OK

実際にtest.shを走らせてみましょう。何もエラーが起きなければ、以下のようにtest.shはOKとのみ表示して終了します。

$ ./test.sh
OK

もしエラーが起きれば、test.shは、期待される値と実際の終了コードを以下のように表示します。

$ ./test.sh
42 expected, but got 123

テストスクリプトをデバグしたいときは、bashに-xというオプションを与えてスクリプトを実行してください。-xオプションをつけると、bashは以下のように実行のトレースを表示します。

$ bash -x test.sh
+ try 0 0
+ expected=0
+ input=0
+ gcc -o 9cc 9cc.c
+ ./9cc 0
+ gcc -o tmp tmp.s
+ ./tmp
+ actual=0
+ '[' 0 '!=' 0 ']'
+ try 42 42
+ expected=42
+ input=42
+ gcc -o 9cc 9cc.c
+ ./9cc 42
+ gcc -o tmp tmp.s
+ ./tmp
+ actual=42
+ '[' 42 '!=' 42 ']'
+ echo OK
OK

我々が本書を通して使う「テストフレームワーク」は、単なる上記のようなシェルスクリプトです。このスクリプトはJUnitなどの本格的なテストフレームワークとくらべて簡単すぎるように見えるかもしれませんが、このシェルスクリプトの簡単さは、9cc自身の簡単さとバランスが取れているので、これくらい簡単なほうが望ましいのです。ユニットテストというものは、要は自分の書いたコードを一発で動かして結果を機械的に比較できればよいだけなので、難しく考えすぎず、まずはテストを行うことが大切なのです。

makeによるビルド

本書を通して読者のみなさんは9ccと何百回、あるいは何千回もビルドすることになるでしょう。9ccの実行ファイルを作成して、その後にテストスクリプトを走らせる作業は毎回同じなので、ツールに任せると便利です。こうした用途で標準的に使われているのがmakeコマンドです。

makeは、実行されるとカレントディレクトリのMakefileという名前のファイルを読み込んで、そこに書かれているコマンドを実行します。Makefileは、コロンで終わるルールと、そのルールのためのコマンドの列という構成になっています。次のMakefileはこのステップで実行したいコマンドを自動化するためのものです。

9cc: 9cc.c

test: 9cc
        ./test.sh

clean:
        rm -f 9cc *.o *~ tmp*

上記のファイルを、9cc.cがあるのと同じディレクトリにMakefileというファイル名で作成してください。そうすると、makeを実行するだけで9ccが作成され、make testを実行するとテストを実行する、ということができるようになります。makeはファイルの依存関係を理解できるので、9cc.cを変更した後、make testを実行する前に、makeを実行する必要はありません。9ccという実行ファイルが9cc.cより古い場合に限り、makeは、テストを実行するより前に9ccをビルドしてくれます。

make cleanというのはテンポラリなファイルを消すルールです。テンポラリファイルは手でrmしてもよいのですが、消したくないファイルを誤ってファイルを消してしまうと面倒なので、こういったユーティリティ的なものもMakefileに書くことにしています。

なお、Makefileを記述する際の注意点ですが、Makefileのインデントはタブ文字でなければいけません。スペース4個や8個ではエラーになります。これは単に使い勝手の悪い文法なだけなのですが、makeは1970年代に開発された古いツールで、伝統的にこうなってしまっています。

gitによるバージョン管理

本書ではバージョン管理システムとしてgitを使います。本書を通してコンパイラをステップ・バイ・ステップで作っていくわけですが、そのステップごとに、gitのコミットを作って、コミットメッセージを書くようにしてください。コミットメッセージは日本語で構わないので、実際に何を変更したのかを1行サマリーとしてまとめるようにしてください。1行以上の詳細な説明を書きたいときは、最初の行の次に1行空行を開けて、そのあとに説明を書くようにします。

gitでバージョン管理を行うのはみなさんが手で生成したファイルだけです。9ccを動かした結果として生成されるファイルなどは、同じコマンドを実行すればもう一度生成できるので、バージョン管理対象には入れる必要はありません。むしろ、こういったファイルを入れてしまうとコミットごとの変更点が不必要に長くなるので、バージョン管理から外して、リポジトリに入れないようにする必要があります。

gitでは.gitignoreというファイルに、バージョン管理から外すファイルのパターンを書くことができます。9cc.cがあるのと同じディレクトリに、以下の内容で.gitignoreを作成して、テンポラリファイルやエディタのバックアップファイルなどをgitが無視するように設定しておきましょう。

*~
*.o
tmp*
9cc

gitを使うのが初めてという人は、gitに名前とメールアドレスを教えておきましょう。ここでgitに教えた名前とメールアドレスがコミットログに記録されます。下は筆者の名前とメールアドレスを設定する例です。読者の皆さんは自分の名前とメールアドレスを設定してください。

$ git config --global user.name "Rui Ueyama"
$ git config --global user.email "rui314@gmail.com"

gitでコミットを作るためには、まず変更があったファイルをgit addで追加する必要があります。今回は初回のコミットなので、まずgit initでgitリポジトリを作成し、その後に、ここまでで作成したすべてのファイルをgit addで追加します。

$ git init
Initialized empty Git repository in /home/ruiu/9cc
$ git add 9cc.c test.sh Makefile .gitignore

そのあとgit commitでコミットします。

$ git commit

git commitを実行するとエディタが立ち上がるので、「整数1つをコンパイルするコンパイラを作成」と1行で書いて、エディタを終了してください。コミットがうまくいったことは以下のようにgit log -pを実行すると確認することができます。

$ git log -p
commit 0942e68a98a048503eadfee46add3b8b9c7ae8b1 (HEAD -> master)
Author: Rui Ueyama <rui314@gmail.com>
Date:   Sat Aug 4 23:12:31 2018 +0000

    整数1つをコンパイルするコンパイラを作成

diff --git a/9cc.c b/9cc.c
new file mode 100644
index 0000000..e6e4599
--- /dev/null
+++ b/9cc.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char **argv) {
+  if (argc != 2) {
...

最後に、ここまでで作成したgitリポジトリをGithubにアップロードしておきましょう。特にGithubにアップロードする積極的な理由はないのですが、アップロードしない理由もないですし、Githubはコードのバックアップとしても役に立ちます。Githubにアップロードするためには、新規のリポジトリを作って（この例ではrui314というユーザを使って9ccというリポジトリを作成しました）、そのリポジトリに対してローカルのリポジトリを以下のようにプッシュします。

$ git remote add origin git@github.com:rui314/9cc.git
$ git push

上記のコマンドを実行したあとGithubをブラウザで開いて、自分のソースコードがアップロードされていることを確認してみてください。

これで第1ステップのコンパイラの作成は完了です。このステップのコンパイラは、コンパイラと呼ぶには簡単すぎるようなプログラムですが、コンパイラに必要な要素をすべて含んだ立派なプログラムです。これから我々はこのコンパイラをひたすら機能拡張していって、まだ信じられないかもしれませんが、立派なCコンパイラに育て上げることになります。まずは最初のステップが完成したことを味わってください。

ステップ2：加減算のできるコンパイラの作成

このステップでは、前のステップで作成したコンパイラを拡張して、42といった値だけではなく、2+11や5+20-4やのような加減算を含む式を受け取れるようにします。

5+20-4のような式は、コンパイルする前に計算して、その結果の21をアセンブリに埋め込むこともできますが、それだとコンパイラではなくインタープリタになってしまうので、加減算を実行時に行うアセンブリを出力する必要があります。加算と減算を行うアセンブリ命令はaddとsubです。addは、2つのレジスタを受け取って、その内容を加算し、結果を第1引数のレジスタに書き込みます。subはaddと基本的に同じですが、減算を行います。これの命令を使うと、5+20-4は次のようにコンパイルすることができます。

.intel_syntax noprefix
.global main

main:
        mov rax, 5
        add rax, 20
        sub rax, 4
        ret

上記のアセンブリでは、movでRAXに5をセットし、そのあとRAXに20を足して、そして4を引いています。retが実行される時点でのRAXの値は 5+20-4すなわち21になるはずです。実行して確認してみましょう。上記のファイルをtmp.sに保存してアセンブルし、実行してみます。

$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
21

上記のように正しく21が表示されました。

さて、このアセンブリファイルはどのように作成すればいいのでしょうか？ この加減算のあるものを「言語」として考えてみると、この言語は次のように定義することができます。

• 最初に数字が1つある
• そのあとに0個以上の <項> が続いている
• <項>というのは、"+"の後に数字が来ているものか、"-"の後に数字が来ているものである

この定義を素直にCのコードに落としてみると、次のようなプログラムになります。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  char *p = argv[1];

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
  printf("  mov rax, %ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
      printf("  add rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
      printf("  sub rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    fprintf(stderr, "予期せぬ文字です: '%c'\n", *p);
    return 1;
  }

  printf("  ret\n");
  return 0;
}

ちょっと長いプログラムになっていますが、前半部分とretの行は以前と同じです。中間に<項>を読み込むためのコードが足されています。今回は数字1つを読むだけのプログラムではないので、数字を読み込んだあとに、どこまで読み込んだのかがわからないといけません。atoiでは読み込んだ文字の文字数は返してくれないので、atoiでは<項>をどこから読めばよいのかわからなくなってしまいます。したがってここでは、C標準ライブラリのstrtol関数を使いました。

strtolは数値を読み込んだ後、第2引数のポインタをアップデートして、読み込んだ最後の文字の次の文字を指すように値を更新します。したがって、数値を1つ読み込んだ後、もしその次の文字が+や-ならば、pはその文字を指しているはずです。上のプログラムではその事実を利用して、whileループの中で次々と<項>を読んで、1つ<項>を読むたびにアセンブリを1行出力するということを行なっています。

さて、さっそくこの改造版コンパイラを実行してみましょう。9cc.cファイルを更新したら、makeを実行するだけで新しい9ccファイルを作ることができるのでした。実行例を以下に示します。

$ make
$ ./9cc '5+20-4'
.intel_syntax noprefix
.global main
main:
  mov rax, 5
  add rax, 20
  sub rax, 4
  ret

どうやらうまくアセンブリが出力されているようですね。この新しい機能をテストするために、test.shに次のようにテストを1行追加しておきましょう。

try 21 '5+20-4'

ここまでできたら、ここまでの変更点をgitにコミットしておきましょう。そのためには以下のコマンドを実行します。

$ git add test.sh 9cc.c
$ git commit

git commitを実行するとエディタが起動するので「足し算と引き算を追加」と書いて保存し、エディタを終了します。git log -pコマンドを使ってコミットが期待した通りに行われていることを確認してみてください。最後にgit pushを実行してGithubにコミットをプッシュしたら、このステップは完了です！

ステップ3：トークナイザを導入

前のステップで作成したコンパイラには1つ欠点があります。もし入力に空白文字が含まれていたら、その時点でエラーになってしまうのです。例えば以下のように5 - 3という空白の入った文字列を与えると、+あるいは-を読もうとしているところで空白文字を見つけることになり、コンパイルに失敗してしまいます。

$ ./9cc '5 - 3' > tmp.s
予期せぬ文字です: ' '

この問題を解決する方法はいくつかあります。1つの自明な方法は、+や-を読もうとする前に空白文字を読み飛ばすことでしょう。このやり方には特に問題があるというわけはないのですが、このステップでは別の方法で問題を解決することにします。その方法というのは、式を読む前に入力を単語に分割してしまうという方法です。

日本語や英語と同じように、算数の式やプログラミング言語も、単語の列から成り立っていると考えることができます。例えば5+20-4は5, +, 20, -, 4という5つの単語でできていると考えることができます。この「単語」のことを「トークン」といいます。トークンの間にある空白文字というのは、トークンを区切るために存在しているだけで、単語を構成する一部分ではありません。したがって、文字列をトークン列に分割すると空白文字は取り除かれることになります。文字列をトークン列に分割することを「トークナイズする」といいます。

文字列をトークン列に分けることには他のメリットもあります。式をトークンに分けるときにそのトークンを分類して型をつけることができるのです。例えば+や-は、見ての通りの+や-といった記号ですし、一方で123という文字列は123という数値を意味しています。トークナイズするときに、入力を単なる文字列に分割するだけではなく、その1つ1つのトークンを解釈することで、トークン列を消費するときに考えなければならないことが減るのです。

現在の加減算ができる式の文法の場合、トークンの型は、+、-、数値の3つです。さらにコンパイラの実装の都合上、トークン列の終わりを表す特殊な型を1つ定義しておくとプログラムが簡潔になります（文字列が'\0'で終わっているのと同じですね）。

コードを読みやすくするために、1文字のトークンについては、そのトークンのASCIIコードをそのトークンの型とすることにします。したがって、+を表すトークンの型は'+'、-を表すトークンの型は'-'です。2文字以上のトークンについてはこのような方法は使えないですし、数値といったトークンもこれで表すことはできないですのですが、そういったトークンはASCIIコードの範囲より大きな数値（256以上）でその型を表すことにします。

やや長くなりますが、トークナイザを導入して改良したバージョンのコンパイラを下に掲載します。

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// トークンの型を表す値
enum {
  TK_NUM = 256, // 整数トークン
  TK_EOF,       // 入力の終わりを表すトークン
};

// トークンの型
typedef struct {
  int ty;      // トークンの型
  int val;     // tyがTK_NUMの場合、その数値
  char *input; // トークン文字列（エラーメッセージ用）
} Token;

// トークナイズした結果のトークン列はこの配列に保存する
// 100個以上のトークンは来ないものとする
Token tokens[100];

// pが指している文字列をトークンに分割してtokensに保存する
void tokenize(char *p) {
  int i = 0;
  while (*p) {
    // 空白文字をスキップ
    if (isspace(*p)) {
      p++;
      continue;
    }

    if (*p == '+' || *p == '-') {
      tokens[i].ty = *p;
      tokens[i].input = p;
      i++;
      p++;
      continue;
    }

    if (isdigit(*p)) {
      tokens[i].ty = TK_NUM;
      tokens[i].input = p;
      tokens[i].val = strtol(p, &p, 10);
      i++;
      continue;
    }

    fprintf(stderr, "トークナイズできません: %s\n", p);
    exit(1);
  }

  tokens[i].ty = TK_EOF;
  tokens[i].input = p;
}

// エラーを報告するための関数
void error(int i) {
  fprintf(stderr, "予期せぬトークンです: %s\n",
          tokens[i].input);
  exit(1);
}

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  // トークナイズする
  tokenize(argv[1]);

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // 式の最初は数でなければならないので、それをチェックして
  // 最初のmov命令を出力
  if (tokens[0].ty != TK_NUM)
    error(0);
  printf("  mov rax, %d\n", tokens[0].val);

  // `+ <数>`あるいは`- <数>`というトークンの並びを消費しつつ
  // アセンブリを出力
  int i = 1;
  while (tokens[i].ty != TK_EOF) {
    if (tokens[i].ty == '+') {
      i++;
      if (tokens[i].ty != TK_NUM)
        error(i);
      printf("  add rax, %d\n", tokens[i].val);
      i++;
      continue;
    }

    if (tokens[i].ty == '-') {
      i++;
      if (tokens[i].ty != TK_NUM)
        error(i);
      printf("  sub rax, %d\n", tokens[i].val);
      i++;
      continue;
    }

    error(i);
  }

  printf("  ret\n");
  return 0;
}

100行程度のあまり短いとはいえないコードですが、行なっていることにトリッキーなことはないので、上から読んでいけば読めるはずです。コードを読んでみるとわかるように、このコンパイラはエラーチェックが非常に弱くて、長い入力などを与えると簡単にクラッシュしてしまいますが、現在のところはそれはそれで構いません。この程度の完成度のときに最初から頑強に作っても仕方がないので、むしろ意図的にエラーチェックは省いています。読者の皆さんもこの段階ではあまり防御的になりすぎないように気をつけてください。

この改良版では空白文字がスキップできるようになったはずなので、次のようなテストを1行test.shに追加しておきましょう。

try 41 ' 12 + 34 - 5 '

そのあとgitにコミットしてみてください。これでこのステップは完了です。

文法の記述方法と再帰下降構文解析

さて、次は乗除算や優先順位のカッコ、すなわち*、/、()を言語に追加したいのですが、それをするためには1つ大きな技術的チャレンジがあります。というのも、小学校で習ったように、掛け算や割り算は式の中で最初に計算しなければいけません。例えば1+2*3という式は1+(2*3)というように解釈しなければいけないのであって、(1+2)*3というように解釈することはできません。こういった、どの演算子が最初に「くっつく」のかというルールを「演算子の優先順位」といいます。

演算子の優先順位はどのように処理すればよいのでしょうか？ ここまで作ってきたコンパイラでは、先頭からトークン列を読んでアセンブリを出力していくだけなので、素直にそのまま拡張して*と/を追加すると、1+2*3を(1+2)*3としてコンパイルしてしまうコンパイラになってしまいます。

既存のコンパイラは当然こういったものをうまく扱えています。コンパイラの構文解析は非常に強力で、どのような複雑なコードでも、文法にそっている限りは正しく解釈することができます。このコンパイラの振る舞いには人間を超える知的な能力すら感じることがありますが、実際には、コンピュータには人間のような文章読解能力はないので、構文解析はなんらかの機械的メカニズムのみによって行われているはずです。具体的にはどういう仕組みで動いているのでしょうか？

この節では、コーディングは一休みにして、構文解析のテクニックについて学んでいきましょう。

文脈自由文法

プログラミング言語の構文の大部分は「生成規則」というものを使って定義されています。生成規則は文法を再帰的に定義するルールです。

自然言語について少し考えて見ましょう。日本語において文法は入れ子構造になっています。例えば「花がきれいだ」という文の「花」という名詞を「赤い花」という名詞句に置き換えても正しい文になりますし、「赤い」というのを「少し赤い」というようにさらに展開してもやはり正しい文になっています。「少し赤い花がきれいだと私は思った」というように別の文章の中に入れることもできます。

こういった文法を、「文とは主語と述語からなる」とか「名詞句は名詞か、あるいは形容詞の後に名詞句がつづくものからなる」といったようなルールとして定義されているものと考えてみましょう。そうすると「文」を出発点にして、ルールに従って展開していくことで、その意味での文法における妥当な文というものをどのようなものでも作り出すことができます。

あるいは逆に、すでに存在している文について、それにマッチする展開手順を考えることで、その文字列がどのような構造を持っているのかどうかを考えることもできます。

元々上記のようなアイデアは自然言語のために考案されたのですが、コンピュータで扱うデータとの親和性がとても高いため、生成規則はプログラミング言語を始めとしてコンピュータの様々なところで利用されています。

生成規則は「A→α」という形式で書くことができます。この規則は、Aをαに展開できるという意味です。αは0個以上の記号の列で、それ以上展開できない記号と、さらに展開される（いずれかの生成規則で左辺に来ている）記号の両方を複数含むことができます。それ以上展開できない記号を終端記号、展開できる記号を非終端記号といいます。

非終端記号は複数の生成規則にマッチしてかまいません。例えばA→α₁とA→α₂の両方の規則があった場合、Aはα₁かα₁のどちらに展開することもできる、という意味になります。A→α₁とA→α₂は、A→α₁ | α₂と省略して書くこともできます。

例として次の生成規則を考えてみてください。

expr:   number
expr:   number "+" expr
expr:   number "-" expr
number: digit | digit number
digit:  "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

ここでは矢印の代わりにコロンを使いました。ダブルクオートでくくられた文字はその文字自身を表しています。この規則では、digitというのは0〜9の一桁の数字、numberは一桁以上の数字の列、exprというのはそれと+あるいは-を組み合わせたものということになります。

実は上の生成規則は、加減算の式の文法を定義しています。exprから出発して展開していくと、任意の加減算の文字列、例えば1や10+5や42-30+2のような文字列を作り出すことができます。以下の展開結果を確認してみてください。

expr → number → digit → "1"

expr → number "+" expr
     → number "+" number
     → digit number "+" number
     → digit digit "+" number
     → digit digit "+" digit
     → "1" digit "+" digit
     → "1" "0" "+" digit
     → "1" "0" "+" "5"

expr → number "-" expr
     → number "-" number "+" expr
     → number "-" number "+" number
     → digit number "-" digit number "+" digit
     → digit digit "-" digit digit "+" digit
     → "4" "2" "-" "3" "0" "+" "2" （digitをすべて展開）

このような展開の手順を、矢印を使ってステップごとに表すだけではなく、木で表すこともできます。そのような木を構文木（syntax tree）といいます。上の式の構文木を以下に示します。なお、numberより下のノードを書くと冗長になりすぎるので、以下の図では省略しました。

このように上記の文法はすべての加減算の式を作り出すことができます。

生成規則による演算子の優先順位の表現

生成規則は文法を表現するための大変強力なツールです。演算子の優先順位（掛け算や割り算は足し算や引き算よりも先に行うといったルール）も、文法を工夫すると、生成規則の中で表すことができます。

日本語でも少し考えてみましょう。「きれいな花がプランターに咲いている」という文では、「きれいな花」がひとかたまりになっていて、プランターがきれいだという誤解が生じることはありません。この文章の構文木を組み立てると、「きれいな」と「花」というのが枝としてひとまとまりになっていて、「プランター」というのは木の中で離れた場所にあるようになるはずです。

このような考え方を応用して、乗除算を加減算よりも優先する文法などを考案することができます。その文法を以下に示します。

expr: mul
expr: mul "+" expr
expr: mul "-" expr
mul:  number
mul:  number "*" mul
mul:  number "/" mul

以前はexprが直接numberに展開されていたのですが、今回はexprはmulを経由してnumberに展開されるルールになりました。mulというのが乗除算の生成規則で、加減算を行うexprは、mulをいわば一つのパーツとして使っています。これにより加減算が先にくっつくというルールが構文木の中で自然と表現されることになります。具体例を見てみましょう。

上の木構造では、掛け算が足し算より常に木の末端方向に現れるようになっています。実際のところ、mulからexprに戻るルールがないので、掛け算の下に足し算がある木は作りようがないのですが、そうはいってもこのような単純なルールで優先順位が木構造としてうまく表現できるのはかなり不思議に感じます。読者の皆さんも実際に試して確認してみてください。

実は上の文法には曖昧性がないので、四則演算の式が与えられるとそれに対応する構文木は一意に決まります。例えば1*2+3*4*5は(1*2)+(3*(4*5))という解釈しか不可能です。それ以外の展開順で1*2+3*4*5という式を生成することはできません。

間接的な再帰を含む生成規則

exprやmulは右辺にそれ自身が来ていて自己再帰するように定義されていました。生成文法では自己再帰だけではなく間接的に再帰する文法も普通に書くことができます。下は、優先順位のカッコを四則演算に追加した文法の生成規則です。

expr: mul
expr: mul "+" expr
expr: mul "-" expr
mul:  term
mul:  term "*" mul
mul:  term "/" mul
term: number
term: "(" expr ")"

以前の文法と比べてみると、木の末端に、いままでは数字が現れていたものが、数字かあるいは丸カッコでくくられた式が現れるようになっています。つまりこの文法では、丸カッコでくくられた式というものは単一の数と同じ「くっつき具合」で扱われるというわけです。一つ例を見てみましょう。

上の木と、下の木を比べてみると、termの展開結果だけが異なることがわかります。展開結果の末端に現れるtermというのは、1つの数字に展開してもよいし、カッコでくくられた任意の式に展開してもよい、というルールが、木構造の中にきちんと反映されています。

見ての通り上記の構文木では1*(2+3)の優先順位が木構造として見事に表されています。このように簡単な生成規則でカッコの優先順位も扱えるというのは少し感動的ではないでしょうか。

抽象構文木

今まで見てきた木は、生成規則をそのまま適用した結果なので、かなり冗長な表現になっています。こういった木は多少切り詰めたり変形しても曖昧にはなりません。例えば1*(2+3)は次の木で簡潔に表すことができます。

もう一つ例を挙げてみましょう。以下に示すのは1*2+3*4*5を簡潔に表した木です。

このようにコンパクトに表した構文木のことを抽象構文木（abstract syntax tree、AST）といいます。コンパイラで構文木を扱うときは、文法に一対一で対応している木よりも、冗長なノードを省いた木のほうが扱いやすいので、通常は構文解析をしつつ抽象構文木を構築していくことになります。

Cの文法は主に上記のような生成規則を使って定義されています。例えば関数は0個以上の式などからなり、式は項と演算子などからなり、項は整数や関数呼び出しなどからできている、といった具合です。[付録2]に9ccが扱うC言語の規則の生成規則がまとまっているので参照してみてください。

再帰下降構文解析

C言語の生成規則が与えられれば、それをどんどん展開していくことで、生成規則の観点からみて正しいあらゆるCプログラムを機械的に生成することができます。しかし9ccにおいて我々が行いたいことは、むしろ逆のことです。外部から文字列としてCプログラムが与えられていて、展開するとそれになる展開手順、すなわち入力と同じ文字列になる構文木を組み立てたいのです。

実は生成規則が与えられれば、その規則から生成される文にマッチする構文木を求めるコードは機械的に書いていくことができます。例として四則演算の文法を考えてみましょう。四則演算の文法を再掲します。

expr: mul
expr: mul "+" expr
expr: mul "-" expr
mul:  term
mul:  term "*" mul
mul:  term "/" mul
term: number
term: "(" expr ")"

パーサを書くときの基本な戦略は、こらの項一つ一つをそのまま関数一つ一つにマップするというものです。したがってパーサはexpr、mul、termという3つの関数を持つことになります。それぞれの関数は、その名前のとおりの記号列をパースします。

具体的にコードで考えてみましょう。2桁以上のnumberは複数の文字からできているわけですが、我々のコンパイラにはすでにトークナイザが導入されているので、複数の数字をまとめて1つの数として扱うことはすでに達成されています。そこで、入力は文字列ではなくトークンの列と見なすことにします。トークンの型を再掲します。

typedef struct {
  int ty;   // トークンの型
  int val;  // tyがTK_NUMの場合、その数値
} Token;

パーサからは抽象構文木を作って返したいので、抽象構文木のノードの型を定義しておきましょう。

enum {
  ND_NUM = 256,     // 整数のノードの型
};

typedef struct Node {
  int ty;           // 演算子かND_NUM
  struct Node *lhs; // 左辺
  struct Node *rhs; // 右辺
  int val;          // tyがND_NUMの場合のみ使う
} Node;

lhsとrhsいうのはそれぞれleft-hand sideとright-hand side、すなわち左辺と右辺という意味です。

新しいノードを作成する関数も定義しておきます。この文法における四則演算では、左辺と右辺を受け取る2項演算子と、数の2種類があるので、その2種類に合わせて関数を2つ用意します。

Node *new_node(int op, Node *lhs, Node *rhs) {
  Node *node = malloc(sizeof(Node))
  node->op = op;
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_node_num(int val) {
  Node *node = malloc(sizeof(Node))
  node->op = ND_NUM;
  node->val = val;
  return node;
}

これらの関数とデータ型を使ってパーサを書いていきましょう。トークン列はtokensというToken型のグローバル変数に入っているものとします。現在着目しているトークンのインデックスをint型のposという変数で表します。posの初期値は0、すなわち最初のトークンです。

exprはmul | mul "+" expr | mul "-" exprを読み込むわけですから、次のようなコードになります。

Node *expr() {
  Node *lhs = mul();
  if (tokens[pos].ty == TK_EOF)
    return lhs;
  if (tokens[pos].ty == '+') {
    pos++;
    return new_node('+', lhs, expr());
  }
  if (tokens[pos].ty == '-') {
    pos++;
    return new_node('-', lhs, expr());
  }
  error("想定しないトークンです: %s",
        tokens[pos].input);
}

expr関数をよく読んでみてください。exprの生成規則、より正確にはそれを変形した次の生成規則が、そのままコードになっていることがわかると思います。

expr:  mul expr'
expr': ε | "+" expr | "-" expr

ここでε（イプシロン）は何もないことを表す記号です。つまりexpr'は、空の記号列か、+ exprか、"-" exprに展開されるということになります。

さて、exprは完全ではありません。exprが使っているmulが定義されていないからです。mulも生成規則をそのままマップする形で関数として書いてみましょう。

Node *mul() {
  Node *lhs = term();
  if (tokens[pos] == TK_EOF)
    return lhs;
  if (tokens[pos].ty == '*') {
    pos++;
    return new_node('*', lhs, mul());
  }
  if (tokens[pos].ty == /') {
    pos++;
    return new_node('/', lhs, mul());
  }
  error("想定しないトークンです: %s",
        tokens[pos].input);
}

同様にtermも書くと次のようになります。

int term() {
  if (tokens[pos].ty == TK_NUM)
    return new_node_num(tokens[pos++].val);
  if (tokens[pos].ty == '(')
    pos++;
    Node *node = expr();
    if (tokens[pos].ty != ')')
      error("開きカッコに対応する閉じカッコがありません: %s",
            tokens[pos].input);
    pos++;
    return node;
  }
  error("数値でも開きカッコでもないトークンです: %s"
        tokens[pos].input);
}

さて、これで全ての関数が揃ったわけですが、これで本当に文字列をパースできるのでしょうか？ 一見よくわからないかもしれませんが、この関数群を使うときちんと文字列がパースできます。例として1+2*3という式を考えてみましょう。

最初に呼ばれるのはexprです。式というのは全体としてexprであると決めつけて（実際にそうなわけですが）入力を読み始めるわけです。そうすると、expr→mul→termというように関数呼び出しが行われて、1が読み込まれ、term→mul→exprというように関数からリターンして返り値として1が戻って来ます。

次に、exprの中のtokens[pos].ty == '+'という式が真になるので、+という文字が消費され、exprが再帰的に呼び出されます。この段階での残りの文字列は2*3です。

exprからは前回と同様にexpr→mul→termというように関数が呼び出され、2が読み込まれますが、今回はexprまではリターンしません。mulのtokens[pos].ty == '*'という式が真になるので、mul→termという関数呼び出しが行われ、3が読み込まれることになります。結果としてmulからは2*3すなわち6が返ることになります。

リターンした先のexprでは、lhsは1、再帰呼び出しのexprの返り値は6なので、7を返します。これが最終的な結果です。つまり正しく1+2*3がパースできたというわけです。

再帰に慣れていないプログラマの場合、上のような再帰的な関数はかなりわかりづらく感じるかもしれません。正直、再帰には非常に慣れているはずの筆者ですら、こういったコードが動くのは一種の魔法のように感じます。再帰的なコードは、仕組みがわかっていてもどこか不思議な感じがするのですが、それはおそらくそういうものなのでしょう。何度もよく頭の中でコードをトレースしてみて、きちんとコードが動作することを確認してみてください。

左再帰の除去

生成規則を関数にそのままマップすることで多くの場合パーサを書いていけるのですが、生成規則で表現可能な文法が、そのまま再帰下降構文解析で例外なく扱えるというわけではありません。ある種の生成規則は再帰下降構文解析ではパーサが書けないのです。例えば次の生成規則を見てください。

add: add "+" number | add "-" number | number

この文法における1+2+3の構文木を下に示します。

このルールをそのまま関数にマップすると、addという関数を書くことになりますが、その関数からまっさきにaddを再帰呼び出しすると無限再帰になってしまいます。再帰下降構文解析では再帰をしながらパースしていくとはいっても、同じ関数に再帰で戻ってくるまでに、少なくとも1文字は入力を読み進めていなければいけないのです。さもなければ1文字も読み進めないまま何度でも同じ関数に戻ってきてしまって、無限に再帰することになってしまいます。

addの生成規則はaddから始まっているものがありました。こういう規則のことを「左再帰」といいます。再帰的な項が左側に存在しているからです。一方で、再帰的な項が右に来ているもののことを「右再帰」といいます。

左再帰は、同じ文を生成する別の文法に生成規則を変更することで、機械的に右再帰に置き換えることができます。再帰下降構文解析を使う場合、左再帰になっている文法は、まず右再帰に置き換える必要があります。

上の生成規則を右再帰に置き換えた文法を下に示します。

add: number add'
add': "+" number add' | "-" number add' | ε

この新たな文法では、addは必ずnumberから始まっています。add'は必ず、+、-のどちらかから始まっているか、入力文字列の終端に到達していることになります。つまりこの新しい文法では、決まった終端記号を読み進めなければ再帰できないので、無限再帰になるという問題はありません。この文法では、以前と同じ文を生成することができますが、構築される構文木の形は異なります。1+2+3の構文木を下に示します。

左再帰では左側に深い木になっていましたが、右再帰では右側に深い木になっています。

さて、どのようにして左再帰を除去したのでしょうか？ 元々の生成規則を下に再掲します。

add: add "+" number | add "-" number | number

左再帰を除去するための基本的なアイデアは、生成規則の右辺で必ず最初に現れなければいけない終端記号を見つけ出して、それをくくり出すことです。上記のaddでは、一番最初にくるのはnumber、+、-のいずれかです。その記号の集合が特定できたら、生成規則の右側の1つ1つの選択肢について、その先頭の記号を取り除いたバージョンの生成規則を作ればよいのです。

生成規則の右辺で最初に現れなければならない終端記号は、右辺を再帰的にたどっていくことで決定することができます。上記のaddの場合、addの最初の項として現れることができるのはnumberだけです。addがaddに再帰しているパターンは、最終的にそうではないパターン（この場合はnumberのみ）に展開されない限り展開が停止しません。したがって、左再帰しているルールを無視して、残りのルールだけに着目すればよいのです。このようにすることで、左再帰になっている文法、同じ文を生成する右再帰の文法に変更することができます。

スタックマシン

前章ではトークン列を抽象構文木に変換するアルゴリズムについて説明しました。演算子の優先順位を考慮した文法を選ぶことによって、*や/が、+や-に比べて、常に枝の先の方に来ている抽象構文木を作ることができるようになったわけですが、この木をどのようにアセンブリに変換すればよいのでしょうか？ この章ではその方法を説明します。

まずは、加減算と同じ方法ではなぜアセンブリに変換できないのかを説明します。加減算のできるコンパイラでは、RAXを結果のレジスタとして、そこに加算や減算を行っていました。つまりコンパイルされたプログラムでは中間的な計算結果を1つだけ保持していて、それがRAXに入っていました。

しかし、乗除算が含まれる場合は中間的な計算結果が1つだけになるとは限りません。例として2*3+4*5を考えてみてください。足し算を行うためには両辺が計算済みでなければいけないので、足し算の前に2*3と、4*5を計算する必要があります。つまりこの場合は途中の計算結果を2つ保持できなければ全体の計算ができないのです。

こういったものの計算が簡単に行えるのが「スタックマシン」というコンピュータです。ここではいったんパーサの作った抽象構文木から離れて、スタックマシンについて学んでみましょう。

スタックマシンの概念

スタックマシンは、スタックをデータ保存領域として持っているコンピュータのことです。したがってスタックマシンでは「スタックにプッシュする」と「スタックからポップする」という2つ操作が基本操作になります。プッシュでは、スタックの一番上に新しい要素が積まれます。ポップでは、スタックの一番上から要素が取り除かれます。

スタックマシンにおける演算命令は、スタックトップの要素に作用します。例えばスタックマシンのADD命令は、スタックトップから2つ要素をポップしてきて、それらを加算し、その結果をスタックにプッシュします（x86-64命令との混同を避けるために、仮想スタックマシンの命令はすべて大文字で表記することにします）。別の言い方をすると、ADDは、スタックトップの2つの要素を、それらを足した結果の1つの要素で置き換える命令です。

SUB、MUL、DIV命令は、ADDと同じように、スタックトップの2つの要素を、それらを減算・乗算、除算した1つの要素で置き換える命令ということになります。

PUSH命令は引数の要素をスタックトップに積むものとします。ここでは使用しませんが、スタックトップから要素を1つ取り除くPOPという命令も考えることができます。

さて、これらの命令を使って、2*3+4*5を計算することを考えてみましょう。上のように定義したスタックマシンを使うと、次のようなコードで2*3+4*5を計算することができるはずです。

// 2*3を計算
PUSH 2
PUSH 3
MUL

// 4*5を計算
PUSH 4
PUSH 5
MUL

// 2*3 + 4*5を計算
ADD

このコードについて少し詳しくみていきましょう。スタックにはあらかじめ何らかの値が入っているものとします。ここではその値は重要ではないので、「...」で表示します。スタックは図において上から下に伸びるものとします。

最初の2つのPUSHが2と3をスタックにプッシュするので、その直後のMULが実行される時点ではスタックの状態は次のようになっています。

MULはスタックトップの2つの値、すなわち3と2を取り除いて、それを掛けた結果、つまり6をスタックにプッシュします。したがってMULの実行後にはスタックの状態は次のようになります。

次にPUSHが4と5をプッシュするので、2番目のMULが実行される直前にはスタックは次のようになっているはずです。

ここでMULを実行すると、5と4が取り除かれて、それを掛けた結果の20に置き換えられます。したがってMULの実行後には次のようになります。

2*3と4*5の計算結果がうまくスタックに入っていることに着目してください。この状態でADDを実行すると、20+6が計算され、その結果がスタックにプッシュされるので、最終的にスタックは次の状態になるはずです。

スタックマシンの計算結果はスタックトップに残っている値ということにすると、26は2*3+4*5の結果ですから、きちんとその式が計算できたことになるわけです。スタックマシンではこの式に限らず、複数の途中結果を持つどのような式でも計算することができます。スタックマシンを使うと、どのような部分式も、それを実行した結果として1つの要素をスタックに結果として残すという約束を守っている限り、上記の方法でうまくコンパイルできるのです。

スタックマシンへのコンパイル

さて、最後に、抽象構文木をスタックマシンのコードに変換する方法について説明しましょう。それができるようになれば、四則演算からなる式をパースして抽象構文木を組み立て、それをx86-64命令を使ったスタックマシンにコンパイルして実行することができるようになります。つまり四則演算のできるコンパイラが書けるようになるというわけです。

スタックマシンでは、部分式を計算すると、それが何であれその結果の1つの値がスタックトップに残るということになっていました。例えば下のような木を考えてください。

AやBというのは部分木を抽象化して表したもので、実際にはなんらかの型のノードを意味しています。しかしその具体的な型や木の形は、この木全体をコンパイルするときには重要ではありません。この木をコンパイルするときは次のようにすればよいのです。

1. 左の部分木をコンパイルする
2. 右の部分木をコンパイルする
3. スタックの2つの値を、それらを加算した結果で置き換えるコードを出力

1のコードを実行した後には、その具体的なコードが何であれ、左の部分木の結果を表す1つの値がスタックトップに置かれているはずです。同様に、2のコードを実行した後には、右の部分木の結果を表す1つの値がスタックトップに置かれているはずです。したがって、木全体の値を計算するためには、その2つの値を、その合計値で置き換えればよいというわけです。

このように、抽象構文木をスタックマシンにコンパイルするときは、再帰的に考えて、木を下りながらどんどんアセンブリを出力していくことになります。再帰の考え方に慣れていない読者にとってはやや難しく思えるかもしれませんが、木構造を扱う時には再帰を使うのはセオリーです。木のように自己相似形のデータ構造を扱う時には、部分も全体も同じように扱う必要があるので、同じ関数を全体に対しても、部分に対しても、部分のさらに一部分についても、同じように使うということになるのです。

以下の例に具体的に考えてみましょう。

コード生成を行う関数は木のルートのノードを受け取ります。

上記の手順に従うと、その関数がまず行うのは左の部分木をコンパイルすることです。つまり数値の2をコンパイルすることになります。2を計算した結果はそのまま2ですから、その部分木のコンパイル結果はPUSH 2です。

次にコード生成関数は右の部分木をコンパイルしようとします。そうすると再帰的に部分木の左側をコンパイルすることになり、結果としてPUSH 3が出力されます。次は部分木の右側をコンパイルすることになり、PUSH 4が出力されます。

そのあとコード生成関数は再帰呼び出しを元に戻りながら、部分木の演算子の型に合わせたコードを出力していきます。最初に出力されるのは、スタックトップの2つの要素を、それらを掛けたもので置き換えるコードです。その次にスタックトップの2つの要素を、それらを足したもので置き換えるコードが出力されます。結果として下のアセンブリが出力されることになります。

PUSH 2
PUSH 3
PUSH 4
MUL
ADD

このような手法を使うと、抽象構文木を機械的にアセンブリに落としていけるのです。

x86-64におけるスタックマシンの実現方法

ここまでは仮想的なスタックマシンの話でした。実際のx86-64はスタックマシンではなくレジスタマシンです。x86-64の演算は通常2つのレジスタ間に対して定義されており、スタックトップの2つの値に対して動作するように定義されているわけではありません。したがって、スタックマシンのテクニックをx86-64で使うためには、レジスタマシンでスタックマシンをある意味でエミュレートする必要があります。

レジスタマシンでスタックマシンをエミュレートするのは比較的簡単です。スタックマシンで1命令になっているものを複数の命令を使って実装すればよいのです。

そのための具体的な手法を説明しましょう。

まずスタックの先頭の要素を指すレジスタを1つ用意しておきます。そのレジスタのことをスタックポインタといいます。スタックトップの2つの値をポップしてきたいのであれば、スタックポインタの指す要素を2つ取り出して、スタックポインタを取り出した要素のぶんだけ変更しておきます。同じように、プッシュするときは、スタックポインタの値を変更しつつそれが指しているメモリ領域に書き込めばよいというわけです。

x86-64のRSPレジスタはスタックポインタとして使うことを念頭に置いて設計されています。x86-64のpushやpopといった命令は、暗黙のうちにRSPをスタックポインタとして使って、その値を変更しつつ、RSPが指しているメモリにアクセスする命令です。したがって、x86-64命令セットをスタックマシンのように使うときは、RSPをスタックポインタとして使うのが素直です。では早速、1+2という式を、x86-64をスタックマシンと見立ててコンパイルしてみましょう。以下にx86-64のアセンブリを示します。

# 左辺と右辺をプッシュ
push 1
push 2

# 左辺と右辺をRAXとRDIにポップして足す
pop rdi
pop rax
add rax, rdi

# 足した結果をスタックにプッシュ
push rax

x86-64には「RSPが指している2つの要素を足す」という命令はないので、いったんレジスタにロードして加算を行い、その結果をスタックにプッシュし直す必要があります。上記のadd命令で行っているのはそういう操作です。

同様に2*3+4*5をx86-64で実装してみると次のようになります。

# 2*3を計算して結果をスタックにプッシュ
push 2
push 3

pop rdi
pop rax
mul rax, rdi
push rax

# 4*5を計算して結果をスタックにプッシュ
push 4
push 5

pop rdi
pop rax
mul rax, rdi
push rax

# スタックトップの2つの値を足す
# つまり2*3+4*5を計算する
pop rdi
pop rax
add rax, rdi
push rax

このように、x86-64のスタック操作命令を使うと、x86-64であってもかなりスタックマシンに近いコードを動かすことができます。

次のgen関数はこの手法をそのままCの関数で実装したものです。

void gen(Node *node) {
  if (node->ty == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->ty)
  case '+':
    printf("  add rax, rdi\n");
    break;
  case '-':
    printf("  sub rax, rdi\n");
    break;
  case '*':
    printf("  mul rax, rdi\n");
    break;
  case '/':
    printf("  mov rdx, 0\n");
    printf("  div rdi\n");
  }

  printf("  push rax\n");
}

特にパースやコード生成において重要なポイントではないのですが、トリッキーな仕様のdiv命令が上のコードでは使われているので、それについて説明しておきましょう。x86-64のdivが素直な仕様になっていなければ、上のコードでは本来div rax, rdiのように書きたかったところですが、そのような2つのレジスタを取る除算命令はx86-64には存在しません。その代わりに、x86-64のdivは、暗黙のうちにRDXとRAXを取って、それを連結したものを128ビット整数とみなして、それを引数のレジスタの64ビットの値で割り、その結果をRAXにセットする、という仕様になっています。RDXをまずゼロクリアしているのはそのためです。

さて、これでスタックマシンの説明は終わりです。ここまで読み進めたことによって、読者のみなさんは複雑な構文解析と、その構文解析の結果得られた抽象構文木をマシンコードに落とすことができるようになったはずです。その知識を活用するために、コンパイラ作成の作業に戻ってみましょう！

ステップ4：四則演算のできる言語の作成

この章では、前章までに作ってきたコンパイラを変更して、優先順位のカッコを含む四則演算の式を扱えるように拡張します。必要なパーツは揃っているので、新たに書くコードはほんのわずかです。コンパイラのmain関数を変更して、新しく作成したパーサとコードジェネレータを使うようにしてみてください。下のようなコードになるはずです。

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  // トークナイズしてパースする
  tokenize(argv[1]);
  Node* node = expr();

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // 抽象構文木を下りながらコード生成
  gen(node);

  // スタックトップに式全体の値が残っているはずなので
  // それをRAXにロードして関数からの返り値とする
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

この段階まで進んだことで、加減乗除と優先順位のカッコからなる式が正しくコンパイルできるようになっているはずです。いくつかテストを追加しておきましょう。

try 47 "5+6*7"
try 15 "5*(9-6)"
try 4 "(3+5)/2"

なお、ここまでは説明の都合上、一気に*、/、()を実装しているような話の流れになっていますが、実際には、一気に実装することは避けてください。あくまでインクリメンタルに、1コミットで1つの機能を、その実装をテストするテストコード付きで追加するようにしてください。元々は加減算ができる機能があったわけですから、まずはその機能を壊さずに、抽象構文木とそれを使ったコードジェネレータを導入するようにしてみてください。そのときには新たな機能を足すわけではないので、新しいテストは必要ありません。その後に、*、/、()を、1コミットごとに（テスト込みで）実装していってください。

ステップ5：1文字のローカル変数

前章までで、四則演算ができる言語のコンパイラを作ることができました。この章では、その言語に機能を追加して、変数を使えるようにします。具体的には次のように変数を含む複数の文をコンパイルできるようになることが目標です。

a = 3;
b = 5 * 6 - 8;
a + b / 2;

一番最後の式の結果をプログラム全体の計算結果とすることにします。これの言語は、四則演算だけの言語に比べると、かなり「本物の言語」のような雰囲気が出てきていると言えるのではないでしょうか？

この章では、まず変数をどのように実装すればよいのかについて説明を行い、その後、インクリメンタルに変数を実装していくことにします。

スタック上の変数領域

Cにおける変数はメモリ上に存在します。変数はメモリのアドレスに名前をつけたものと言ってもよいでしょう。メモリアドレスに名前をつけることにで、「メモリの0x60a0番地にアクセスする」というように表現するのではなく、「変数aにアクセスする」というように表現することができるようになります。

ただし関数は再帰することができるので、ローカル変数を固定のアドレスに配置することはできません。その代わりにローカル変数はスタックに置くことになっています。関数を呼び出すごとにローカル変数分の領域をスタックに確保するようにすれば、固定の領域に縛られることがなくなるので、同じ関数を再帰的に呼び出すことができるというわけです。

スタックの内容を具体的な例を挙げて考えてみましょう。ローカル変数aとbを持つ関数fがあり、別の何らかの関数がfをcall命令で呼び出したとします。callはリターンアドレスをスタックに積むので、fが呼ばれた時点のスタックトップは、そのリターンアドレスが入っていることになります。それ以外にも、元々スタックには何らかの値が入っているものとします。ここでは具体的な値は重要ではないので「...」で表すことにします。図にすると次のようになります。

ここでは「←RSP」という表記で、現在のRSP（スタックポインタ）の値がこのアドレスを指しているということを表すことにします。aとbのサイズはそれぞれ8バイトとします。

この状態からaとbの領域を確保するためには、変数2個分、つまり合計で16バイトRSPを押し下げる必要があります。それを行うと次のようになります。

このようにすると、RSP+8の値を使うとaに、RSPの値を使うとbに、それぞれアクセスできるということになります。このように関数呼び出しごとに確保されるメモリ領域のことを「関数フレーム」や「アクティベーションレコード」といいます。

基本的にローカル変数というのは、このように単純なものとして実装されています。

ただし、この方法は一つ落とし穴があるので、実際の実装にはもう一つレジスタを使うことになります。我々のコンパイラでは（そしてそのほかのコンパイラでも）、関数を実行している間にRSPが変更されることがあることを思い出してください。9ccは式の途中の計算結果をRSPを使ったスタックにプッシュ／ポップしているので、RSPの値は頻繁に変更されます。したがって、aやbにはRSPからの固定のオフセットでアクセスすることができません。

これを解決するためには、RSPとは別に、現在の関数フレームの開始位置を常に指しているレジスタを用意します。そのようなレジスタを「ベースレジスタ」、そこに入っている値のことを「ベースポインタ」と呼びます。x86-64では慣習としてRBPレジスタをベースレジスタとして使用します。

関数実行中にはベースポインタは変化してはいけません（それこそがベースポインタを用意する理由です）。関数から別の関数を呼び出して、戻ってきたら別の値になっていた、というのではダメですから、関数呼び出しごとに元のベースポインタを保存しておいて、リターンする前に書き戻す必要があります。元のベースポインタもスタックに保存することになるので、スタックは結果的に元のベースポインタが多層的に保存されている構造になります。

ベースポインタを使った関数呼び出しにおけるスタックの状態を示したのが以下の図です。この図では、関数gがf呼んだものと仮定しています。

このようにすると、aにはRBP-8、bにはRBP-16というアドレスで常にアクセスすることができます。具体的にこのようなスタックの状態を作るアセンブリを考えてみると、それぞれの関数の冒頭に、以下のようなアセンブリをコンパイラが出力すればよいということになります。

push rbp
mov rbp, rsp
sub rsp, 16

このような、コンパイラが関数の先頭に出力する定型の命令のことを「プロローグ」といいます。

RSPがリターンアドレスを指している状態から上のコードを実行すると、期待している通りの関数フレームができあがることを確認してみてください。なお、16というのは、実際には関数ごとに変数の個数に合わせた値にする必要があります。

関数からリターンするときには、RBPに元の値を書き戻して、RSPがリターンアドレスを指している状態にして、ret命令を呼びます（ret命令はスタックからアドレスをポップして、そこにジャンプする命令です）。それを行うコードは以下のように簡潔に書くことができます。

mov rsp, rbp
pop rbp
ret

このような、コンパイラが関数の末尾に出力する定型の命令のことを「エピローグ」といいます。

上のコードの最初の2つの命令を実行したときのスタックの状態を以下に示します。RSPが指しているアドレスより下のスタック領域は、もはや無効なデータとみなしてよいので、図では省略しました。

1. mov rsp, rbpを実行した後のスタック

   gのリターンアドレス
   gの呼び出し時点のRBP
   gのローカル変数
   ...
   fのリターンアドレス
   fの呼び出し時点のRBP	← RSP, RBP

2. pop rbpを実行した後のスタック

   gのリターンアドレス
   gの呼び出し時点のRBP	← RBP
   gのローカル変数
   ...
   fのリターンアドレス	← RSP

このようにしてローカル変数というものは実現されているのです。

トークナイザの変更

変数をどのように実装すればよいのかがわかったところで、早速実装してみましょう。ただし任意の個数の変数をサポートするのは急に難しくなりすぎるので、このステップにおける変数は小文字1文字に限定することにして、変数aはRSP+8、変数bはRSP+16、変数cはRSP+24、というように、すべての変数がRSPからの固定のオフセットにあるものとします。アルファベットは26文字あるので、関数を呼び出すときには、26*8すなわち208バイト分RSPを押し下げることにすると、すべての1文字変数の領域を確保できることになります。

では早速実装してみましょう。まずはトークナイザに手を加えて、今までの文法要素の他に、一文字の変数をトークナイズできるようにします。そのためには新たなトークンの型を追加する必要があるでしょう。変数名はinputメンバーから読むことができるので、特にToken型に新たにメンバーを足す必要はありません。結果として、次のようなデータ構造になるはずです。

enum {
  TK_NUM = 256, // 整数トークン
  TK_IDENT,     // 識別子
  TK_EOF,       // 入力の終わり表すトークン
};

トークナイザに変更を加えて、アルファベットの小文字ならば、TK_IDENT型のトークンを作成するようにしてください。次のようなif文をトークナイザに加えれば良いはずです。

if ('a' <= *p && *p <= 'z') {
  tokens[i].ty = TK_IDENT;
  tokens[i].input = p;
  i++;
  p++;
  continue;
}

パーサの変更

再帰下降構文解析では文法さえわかれば機械的に関数呼び出しにマップできるのでした。したがって、パーサに加えるべき変更を考えるためには、変数名（識別子）を加えた新たな文法がどうなっているのかを考えてみる必要があります。

変数名（すなわち識別子）をidentとしましょう。これはnumberと同じように終端記号です。変数というのは数値が使えるところではどこでも使えるので、numberだったところをnumber | identというようにすると、数値の代わりに変数が使える文法になります。

それに加えて、文法に代入文を足す必要があります。変数は代入できないと仕方がないので、a=1のような式を許す文法にしたいというわけです。ここではCにあわせて、a=b=1のように書ける文法にしておきましょう。

さらに、セミコロン区切りで複数の式を書けるようにしたいので、結果として新しい文法は以下のようになります。この文法はすでに左再帰除去済みです。

program: assign program'
program': ε | assign program'

assign: expr assign' ";"
assign': ε | "=" expr assign'

expr: mul
expr: mul + expr
expr: mul "-" expr
mul: term
mul: term "*" mul
mul: term "/" mul
term: number | ident
term: "(" expr ")"

まずは42やa=b=2;a+b;のようなプログラムがこの文法に合致していることを確認してみてください。そのあと、ここまでで作成したパーサに手を入れて、上記の文法をパースできるようにしてください。この段階ではa+1=5のような式もパースできてしまいますが、それは正しい動作です。そのような意味的に不正な式の排除は次のパスで行います。パーサを改造することについては、特にトリッキーなところはなく、いままでと同じように文法要素をそのまま関数呼び出しにマップしていけばできるはずです。

セミコロン区切りで複数の式をかけるようにしたので、パースの結果として複数のノードをどこかに保存する必要があります。いまのところは次のグローバルな配列を用意して、そこにパース結果のNode *を順にストアするようにしてください。最後のノードはNULLで埋めておくとどこが末尾かわかるようになります。

Node *code[100];

抽象構文木では新たに「識別子を表すノード」を表現できるようになる必要があります。そのために、識別子の新しい型と、ノードの新しいメンバーを追加しましょう。例えば次のようになるはずです。パーサでは、識別子トークンに対してND_IDENT型のノードを作成して返すことになります。

enum {
  ND_NUM = 256,     // 整数のノードの型
  ND_IDENT,         // 識別子のノードの型
};

typedef struct Node {
  int ty;           // 演算子かND_NUM
  struct Node *lhs; // 左辺
  struct Node *rhs; // 右辺
  int val;          // tyがND_NUMの場合のみ使う
  char name;        // tyがND_IDENTの場合のみ使う
} Node;

lvalueとrvalue

代入式はそれ以外の二項演算子とは違って、左辺の値を特別に扱う必要があるので、それについてここで説明しておきましょう。

代入式の左辺はどのような式でも許されているというわけではありません。例えば1=2というように1という数に2を代入することはできません。a=2のような代入は許されていますが、(a+1)=2のような式の結果に代入することはできません。9ccにはまだポインタや構造体は存在していませんが、もし存在しているとしたら、*p=2やa.b=2のような代入は正当なものとして許さなければいけません。このような正当な式と不正な式の区別はどのようにつければよいのでしょうか？ また、結局のところ変数参照や代入というのはなにを行えばよいのでしょうか？

Cにおいて代入式の左辺にくることができるのは、メモリのアドレスを指定する式だけです。

変数というのはメモリに存在していてアドレスを持っているので、変数は代入の左辺に書くことができます。同様に、*pのようなポインタ参照も、pの値をアドレスとみなすという話なので、これも左辺に書くことができます。a.bのような構造体のメンバアクセスも、メモリ上に存在する構造体aの開始位置からbというメンバのオフセット分進んだメモリアドレスを指しているので、左辺に書くことができます。

これに対して、変数を起点にアクセスできるようなアドレスを持っていないa+2のような式は、言語仕様的に特定のアドレスを指定する式とは言えないので、左辺に書くことはできません。

左辺に書くことができる値のことをlvalue（left value、左辺値）、そうではない値のことをrvalue（right value、右辺値）といいます。現在の我々の言語では、変数のみがlvalueで、それ以外の値はすべてrvalueです。

変数のコード生成を行う際はlvalueを起点に考えることができます。代入の左辺として変数が現れている場合は、左辺の値として変数のアドレスを計算するようにして、そのアドレスに対して右辺の評価結果をストアします。それ以外のコンテキストで変数が現れている場合は、同じように変数のアドレスを計算したあとに、そのアドレスから値をロードします。

任意のアドレスから値をロードする方法

ここまでのコード生成ではスタックトップのメモリにしかアクセスしていませんでしたが、ローカル変数ではスタック上の任意の位置にアクセスする必要があります。ここではメモリアクセスの方法について説明します。

CPUはスタックトップだけではなくメモリの任意のアドレスから値をロードしたりストアすることができます。

ロードするときは、mov dst, [src]という構文を使います。この命令は「SRCレジスタの値をアドレスとみなしてそこから値をロードしDSTに保存する」という意味です。例えばmov rdi, [rax]ならば、RAXに入っているアドレスから値をロードしてRDIにセットするということになります。

ストアするときは、mov [dst], srcという構文を使います。この命令は「DSTレジスタの値をアドレスとみなして、SRCレジスタの値をそこにストアする」という意味です。例えばmov [rdi], raxならば、RAXの値を、RDIに入っているアドレスにストアするということになります。

pushやpopは暗黙のうちにRSPをアドレスとみなしてメモリアクセスをする命令なので、これらは普通のメモリアクセスを使って複数の命令で書き直すことができます。つまり、pop raxはmov rax, [rsp]; add rsp, 8という2つの命令と同じですし、push raxはsub rsp, 8; mov [rsp], raxという2つの命令と同じです。

コードジェネレータの変更

ここまでの知識を使って、変数を含む式を扱えるようにコードジェネレータに変更を加えてみましょう。今回の変更では式をlvalueとして評価するという関数を追加することになります。下のコードにおけるgen_lvalという関数はそれを行なっています。gen_lvalは、与えられたノードが変数を指しているときに、その変数のアドレスを計算して、それをスタックにプッシュします。それ以外の場合にはエラーを表示します。これにより(a+1)=2のような式が排除されることになります。

変数をrvalueとして使う場合は、まずlvalueとして評価したあと、スタックトップにある計算結果をアドレスとみなして、そのアドレスから値をロードします。

void gen_lval(Node *node) {
  if (node->ty == ND_IDENT) {
    printf("  mov rax, rbp\n");
    printf("  sub rax, %d\n",
           ('z' - node->name + 1) * 8);
    printf("  push rax\n");
    return;
  }
  error("代入の左辺値が変数ではありません");
}

void gen(Node *node) {
  if (node->ty == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  if (node->ty == ND_IDENT) {
    gen_lval(node);
    printf("  pop rax\n")
    printf("  mov rax, [rax]\n");
    printf("  push rax\n");
    return;
  }

  if (node->ty == '=') {
    gen_lval(node->lhs);
    gen(node->rhs);

    printf("  pop rdi\n");
    printf("  pop rax\n");
    printf("  mov [rax], rdi\n");
    printf("  push rdi\n");
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->ty)
  case '+':
    printf("  add rax, rdi\n");
    break;
  case '-':
    printf("  sub rax, rdi\n");
    break;
  case '*':
    printf("  mul rax, rdi\n");
    break;
  case '/':
    printf("  mov rdx, 0\n");
    printf("  div rdi\n");
  }

  printf("  push rax\n");
}

メイン関数の変更

さて、すべてのパーツが揃ったところでmain関数も変更して、コンパイラを実際に動かしてみましょう。

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  // トークナイズしてパースする
  // 結果はcodeに保存される
  tokenize(argv[1]);
  program()

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // プロローグ
  // 変数26個分の領域を確保する
  printf("  push rbp\n");
  printf("  mov rbp, rsp\n");
  printf("  sub rsp, 208\n");

  // 先頭の式から順にコード生成
  for (int i = 0; code[i]; i++) {
    gen(code[i]);

    // 式の評価結果としてスタックに一つの値が残っている
    // はずなので、スタックが溢れないようにポップしておく
    printf("  pop rax\n");
  }

  // エピローグ
  // 最後の式の結果がRAXに残っているのでそれが返り値になる
  printf("  mov rsp, rbp\n");
  printf("  pop rbp\n");
  printf("  ret\n");
  return 0;
}

分割コンパイルとリンク

この段階までは、Cファイルとテストのシェルスクリプトがそれぞれ1つだけというファイル構成で開発を進めてきました。この構成に問題があるというわけではないのですが、だんだんソースが長くなってきているので、このあたりで複数のCファイルに分割して見通しをよくすることにしましょう。このステップでは、9cc.cという1つのファイルを、以下の4つのファイルに分割します。

• 9cc.h：ヘッダファイル
• main.c：main関数
• parse.c：パーサ
• codegen.c：コードジェネレータ

main関数は小さいので他のCファイルに入れてもよかったのですが、意味的にparse.cとcodegen.cのどちらにも属さないので、別のファイルに分けることにしました。

9cc.hというのはヘッダファイルです。プログラムの構成によっては1つの.cファイルごとに1つの.hファイルを用意することもありますが、余分な宣言があっても特に害をなすことはないので、ここではそこまで細かな依存関係の管理をする必要はありません。9cc.hというファイルを一つ用意して、すべてのCファイルで#include "9cc.h"というようにインクルードしてください。

リンク

分割コンパイルにおいて複数のCファイルがどのように実行ファイルに変換されるのかを理解しておきましょう。

CコンパイラはCファイルをアセンブリファイルにコンパイルします。アセンブラはアセンブリファイルを読んで、.oという拡張子のファイルを出力します。拡張子が.oのファイルのことを「オブジェクトファイル」といいます。

オブジェクトファイルにはコンパイラがコード生成を行なった結果が含まれています。例えば、元々のCファイルで定義されていた関数や変数はオブジェクトファイルにも含まれています。一方で、別のCファイルで定義されていて、元々のCファイルでは単に使っているだけの関数や変数のコードは、オブジェクトファイルには入っていません（Cコンパイラはその関数や変数の名前だけ知っていて、実際のコードのことは知らないので、コードを出力しようがありません）。そういう情報は、コンパイル時には解決できないので、アセンブラは出力ファイルを生成するときに、未解決の名前とそのオブジェクトファイル上での位置をオブジェクトファイルに記録しておいて、後で修正してもらうようにします。

複数のオブジェクトファイルをまとめて実行ファイルを作成するのが「リンカ」と呼ばれるプログラムです。リンカは、オブジェクトファイルを連結して、未解決の名前を解決し、実行ファイルを作成します。リンカが行う動作のことを「リンク」するといいます。

リンカは未解決の名前が最後まで残ってしまったり、逆に複数のオブジェクトファイルが同じ名前を定義しているときに、それをエラーとして扱います。リンクに失敗することを「リンクエラー」といいます。

下の図は、9ccという実行ファイルが作成されるまでの流れを表したものです。

.cを.oに変換するのはコンパイラとアセンブラの役目です。普通のコンパイラではバックグラウンドでアセンブラを起動していたり、アセンブラを内蔵していたりするので、gccコマンド1つで.cから.oへの変換ができているように見えますが、概念としては分割することができます。

複数の.oファイルをまとめて9ccという実行ファイルにするのはリンカの役目です。リンカはユーザが明示的に与えたオブジェクトファイルをリンクするだけではありません。実はリンカには、暗黙のうちにlibc、すなわちC標準ライブラリが渡されていて、printfなどの関数はそこからリンクされることになります。printfやstrtolなどの関数は、標準で配布されているライブラリに含まれているというだけが特別なのであって、その実態は誰かが普通にCで書いただけのコードです。したがって、ユーザが書いたコードのオブジェクトファイルと同じように、最終的なプログラムには、標準ライブラリに含まれるそれらのオブジェクトファイルもリンクされなければいけないのです。

C標準ライブラリのオブジェクトファイルは、基本的に1つの.oファイルに1つの関数が入っているという形になっています。こうすることによって、不要なコードはファイルごとリンカによって無視されるので、使っていない関数が出力されるファイルに入ってしまうということを避けることができます。ファイルがたくさんあると冗長なので、ライブラリでは、.aという形式のアーカイブファイル（.zipや.tarのようなものです）に複数のオブジェクトファイルがまとめて入れられているのが普通です。

何をヘッダファイルに書けばよいのか

Cファイルに書くべきものと、ヘッダファイルに書くべきものの区別というのは、Cの初心者や中級者にとってはややわかりづらいようです。したがってここではそれについて説明をします。

まず端的に例を示しましょう。ヘッダファイルに書いてよいのは次のようなものです。

int plus(int x, int y);
extern int global_var;
struct StructTag { ... };
typedef struct { ... } FooType;
enum { ... };

逆に次のようなものはヘッダファイルに書いてはいけません。

int plus(int x, int y) {
  ...
}

int global_var;
struct StructTag foo;
FooType bar;

次の2行のコードを比べてみてください。

int one();
int two() { return 2; }

1行目も2行目も文法的に正しいCのコードですが、前者は関数本体が書かれていません。前者のような実体を含んでいないものを「宣言」、それに対して2行目のようなものを「定義」といいます。Cコンパイラは宣言をみることで、oneがintを返す関数だということを知ることができます。それによりoneを呼ぶことができるようになります。しかし、oneそのもののコードを出力することはできません。宣言しかみていない場合、関数本体については何も知らないのでこれは当然です。

グローバル変数についても同じように宣言と定義の区別があります。グローバル変数ではexternをつけると宣言、それがない場合に定義になります。下に例を示します。

extern int global_var; // 宣言
int global_var;        // 定義

structやunion、typedefなども宣言です。そういった型を定義すること自体はアセンブリを出力する対象にはならないからです。ただしその型の変数などを定義すると、当然ながらそれは定義になります。下に例を示します。

typdef struct { int foo; } FooType; // 宣言
FooType global_var;                 // global_varの定義

struct FooType { int foo; };        // 宣言
struct FooType global_var;          // global_varの定義

ヘッダファイルには複数のCファイルが必要とする宣言だけを書いてください。そうすることにより、ヘッダファイルをインクルードすることでコンパイラに型情報を教えることができます。ヘッダファイルはそれ単体ではコンパイル対象にはなりません。仮にヘッダファイルをコンパイルしたら、何も定義は含まれていないはずなので、空のアセンブリができあがるはずです。

ヘッダファイルに定義を書いてしまった場合はどうなるでしょうか？ 例えばヘッダファイルに関数を本体付きで書いてしまったとしましょう。そうすると、それをインクルードしているすべてのCファイルにその関数が書いてあるかのようなコンパイル結果になるので、複数のオブジェクトファイルに関数定義が含まれるようになります。結果として、名前が重複して定義されていることになるので、リンクエラーになります

同じCファイルの中からしか使われていない関数などはヘッダファイルに書く必要はありません。そういった関数の情報は、他のCファイルをコンパイルするときに必要ないからです。

ヘッダファイルに宣言を書いたグローバル変数や関数は、どれか1つのCファイルにだけ定義を書いておきます。例えばヘッダファイルに以下の宣言が書かれていたとすると

extern int foo;
int bar();

どれか1つのCファイルには次のような定義が含まれていなければいけません。

int foo;
int bar() { ... }

Makefileの変更

さて、プログラムを複数のファイルに変更したところで、Makefileも更新しておきましょう。下のMakefileは、カレントディレクトリに置かれているすべての.cファイルをコンパイル＆リンクして、9ccという実行ファイルを作成するためのものです。プロジェクトのヘッダファイルとしては、9cc.hという一つのファイルだけが存在して、そのヘッダファイルをすべての.cファイルでインクルードしているものと仮定しています。

CFLAGS=-Wall -std=c11
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

9cc: $(OBJS)

$(OBJS): 9cc.h

test: 9cc
        ./test.sh

clean:
        rm -f 9cc *.o *~

Makefileのインデントはタブ文字でなければいけないことに注意してください。

makeは高機能なツールで、必ずしも使いこなす必要はないのですが、上のMakefileくらいは読めるようになっているといろいろな場面で役に立ちます。そこで、この節では上のMakefileの説明を行います。

Makefileでは、コロンで区切られた行と、それに続くタブでインデントされた0行以上のコマンドの行が、1つのルールを構成します。コロンの前の名前のことを「ターゲット」といいます。コロンの後ろの0個以上のファイル名のことを依存ファイルといいます。

CFLAGSやSRCS、OBJSは変数です。

CFLAGSはmakeの組み込みルールによって認識される変数で、Cコンパイラに渡すコマンドラインオプションを書いておきます。ここでは、積極的に警告をだすための-Wallというフラグと、Cの最新規格であるC11で書かれたソースコードということを伝えるための-std=c11という2つのフラグを渡しています。

SRCSの右辺で使われているwildcardというのはmakeが提供している関数で、関数の引数にマッチするファイル名に展開されます。$(wildcard *.c)は、現在のところmain.c parse.c codegen.cに展開されるというわけです。

OJBSの右辺では変数の置換ルールを使っていて、それによりSRCの中の.cを.oに置き換えた値を生成しています。SRCSはmain.c parse.c codegen.cなので、OBJSはmain.o parse.o codegen.oになります。

これらを踏まえた上で、make 9ccと実行したときに何が起こるのかをトレースしてみましょう。makeは引数として指定されたターゲットを生成しようとするので、9ccファイルを作ることがコマンドの最終的な目標になります（引数がない場合は最初のルールが選ばれるので、この場合は9ccは指定しなくてもよい）。makeはそのために依存関係をたどっていって、欠けている、あるいは古くなっているファイルをビルドしようとします。

9ccの依存ファイルは、カレントディレクトリにある.cファイルに対応する.oファイルです。もし前回makeを実行したときの.oファイルが残っていて、それが対応する.cファイルより新しいタイムスタンプであるときは、makeはわざわざ同じコマンドを再実行したりはしません。.oファイルが存在しないか、.cファイルのほうが新しい場合にのみ、コンパイラを実行して.oファイルを生成します。

$(OBJS): 9cc.hというルールは、すべての.oファイルが9cc.hに依存していることを表しています。したがって9cc.hを変更した場合、すべての.oファイルが再コンパイルされることになります。

ステップ6：ベクタとマップ

いままではトークンや文の数が100個固定になっていて、それを超える長いプログラムを与えるとコンパイラがクラッシュするという仕様になっていました。最初から細部まで作り込み過ぎないほうがよいという意味で、それはむしろ望ましい仕様だったのですが、そろそろそういう制限を直してもよい段階に達したと言えるでしょう。したがってこの章では可変長ベクタを実装します。

また、任意個数の変数をサポートしたいのですが、そのためには変数名をキーとしてルックアップすることのできるマップが必要です。そのマップもこの章で実装します。

ベクタ

可変長ベクタにはvoidのポインタを入れるものとします。voidのポインタは他の型のポインタをなんでも保持することができます。整数もvoid *にキャストしてintにキャストし直すと元の整数に戻るので、やや無理やりですが、ここで作る可変長ベクタには整数も入れることができます。

可変長ベクタは実際のデータを保持するバッファに加えて、バッファの大きさと、そのうち何この要素を使っているのかという情報を保持する必要があります。可変長ベクタの構造体を以下に示します。

typedef struct {
  void **data;
  int capacity;
  int len;
} Vector;

dataはデータ本体で、capacityというのはバッファの大きさです。data[0]からdata[capacity - 1]までがバッファの領域ということになります。lenというのはベクタに追加済みの要素の個数を表しています。len == capacityのときにバッファは一杯で、それ以上要素を足すには、新たにバッファを確保して既存の要素をコピーし、dataポインタをすげ替える必要があります。

ベクタとマップの実装は小さいのでutil.cというファイル1個にまとめて入れてしまいましょう。uil.cに書くべきベクタの関数は以下の2つだけです。

Vector *new_vector() {
  Vector *vec = malloc(sizeof(Vector));
  vec->data = malloc(sizeof(void *) * 16);
  vec->capacity = 16;
  vec->len = 0;
  return vec;
}

void vec_push(Vector *vec, void *elem) {
  if (vec->capacity == vec->len) {
    vec->capacity *= 2;
    vec->data = realloc(vec->data, vec->capacity);
  }
  vec->data[vec->len++] = elem;
}

dataやlenは構造体のメンバに直接アクセスすればよいので、それらに対するアクセッサは特に定義する必要はありません。

マップ

普通のプログラミング言語やライブラリではマップはハッシュテーブルとして実装されています。ハッシュテーブルは高速にルックアップできる優れたデータ構造ですが、実装が大規模になるので、9ccで使うのには適していません。したがってここでは、連想配列によってマップを実装することにします。

連想配列というのはキーと値のペアが入ったベクタのことです。マップのデータ構造を以下に示します。

typedef struct {
  Vector keys;
  Vector vals;
} Map;

util.cに追加すべき関数は次の3つです。

Map *new_map() {
  Map *map = malloc(sizeof(Map));
  map->keys = new_vector();
  map->vals = new_vector();
  return map;
}

void map_put(Map *map, char *key, void *val) {
  vec_push(map->keys, key);
  vec_push(map->vals, val);
}

void *map_get(Map *map, char *key) {
  for (int i = map->keys->len - 1; i >= 0; i--)
    if (strcmp(map->keys->data[i], key) == 0)
      return map->vals->data[i];
  return NULL;
}

ルックアップするときは、キーを順番にスキャンして、一致するものを探します。マップに値を追加するときは、既存の同じキーが存在している場合はそれを上書きし、そうでない場合は新規にキーを追加するというのが普通ですが、連想配列の場合は特にそうする必要はありません。新しいキーから古いキーに向かってスキャンするようにすれば（リストの末尾から先頭に向かって一致するかどうかを試していけば）、同じキーの新しい値は、自然と古い値を隠すようになります。

ここで定義したベクタやマップはかなり素朴な実装ですが、今後のコンパイラ開発を進めていく上で十分な機能を持っています。

データ構造のユニットテスト

この章で作成したベクタやマップも当然テストを書きたいところですが、これらの機能は外部に直接アクセスできる形で実装されていないので、単にコマンドを実行してみるという方法ではテストできません。したがってこれらのテストは、プログラムの一部分としてテストコードを書くことにします。具体的には、9ccの一部分としてテストコードを書いて、./9cc -testと実行したときに限り、コンパイラ本体ではなくそのテスト関数を呼ぶことにします。もう一つテスト用にmain関数を作ってバイナリを分ける方法もあるのですが、それは現時点ではやや大げさなので、同じバイナリにいれるほうがよいでしょう。

util_test.cというファイルを以下のような内容で新たに作成してください。

#include "9cc.h"
#include <stdio.h>
#include <stdlib.h>

int expect(int line, int expected, int actual) {
  if (expected == actual)
    return;
  fprintf(stderr, "%d: %d expected, but got %d\n",
          line, expected, actual);
  exit(1);
}

void test_vector() {
  Vector *vec = new_vector();
  expect(__LINE__, 0, vec->len);

  for (int i = 0; i < 100; i++)
    vec_push(vec, (void *)i);

  expect(__LINE__, 100, vec->len);
  expect(__LINE__, 0, (int)vec->data[0]);
  expect(__LINE__, 50, (int)vec->data[50]);
  expect(__LINE__, 99, (int)vec->data[99]);
}

void test_vector() {
  Map *map = new_map();
  expect(__LINE__, 0, (int)map_get(map, "foo"));

  map_put(map, "foo", (void *)2);
  expect(__LINE__, 2, (int)map_get(map, "foo"));

  map_put(map, "bar", (void *)4);
  expect(__LINE__, 4, (int)map_get(map, "bar"));

  map_put(map, "foo", (void *)6);
  expect(__LINE__, 6, (int)map_get(map, "foo"));
}

void runtest() {
  test_vector();
  test_map();
  printf("OK\n");
}

テストコードはこれくらいの簡単さで十分です。上記のコードで使っている__LINE__という識別子は、Cプリプロセッサのマクロで、その識別子の現れている行番号を表します。これにより、テストが失敗した時、上のテストコードの何行目のテストが失敗しているのかすぐにわかるので便利というわけです。

その後にvoid runtest();という宣言を9cc.hに追加し、argv[1]が-testの時にruntest関数を呼ぶようにmainに変更を加えてください。最後にMakefileに以下の変更を加えて、make testとしたときに./test.shだけではなく./9cc -testも走らせるようにすれば、テストは完成です。

test: 9cc
        ./9cc -test
        ./test.sh

1972年のCコンパイラ

ここまで我々はインクリメンタルにコンパイラを作ってきました。この開発プロセスはある意味でCの歴史をそのままなぞっていると言うことができます。

現在のCを見てみると意味のよくわからない部分や不必要に複雑な部分が散見されますが、そういったものは歴史を抜きにして理解することはできません。現在のCの不可解なところも、初期のCのコードを読んで、初期のCの形とその後の言語とコンパイラの発展の様子をみてみると、いろいろ腑に落ちるところがあります。

CはUnixのための言語として1972年に開発が始まりました。1972年か1973年当時の、つまりCの歴史の中での極めて初期のソースコードがテープに残されていて、そこから読み出したファイルがインターネットに公開されています。当時のCコンパイラのコードを少し覗いてみましょう。以下に示すのは、printfフォーマットでメッセージを受け取って、それをコンパイルのエラーメッセージとして表示する関数です。

error(s, p1, p2) {
  extern printf, line, fout, flush, putchar, nerror;
  int f;

  nerror++;
  flush();
  f = fout;
  fout = 1;
  printf("%d: ", line);
  printf(s, p1, p2);
  putchar('\n');
  fout = f;
}

どことなく奇妙な、CのようなCではないような言語に見えます。当時のCはこういう言語でした。このコードを読んでまず気がつくのは、我々が作ってきたコンパイラの初期の段階と同じように、関数の返り値や引数に型がないことです。ここではsは文字列へのポインタ、p1やp2は整数のはずなのですが、当時のマシンではすべてが同じ大きさだったので、このように変数は型なしになっています。

2行目には、errorが参照しているグローバル変数と関数の宣言が書かれています。当時のCコンパイラにはヘッダファイルもCプリプロセッサもなかったので、このようにしてプログラマはコンパイラに変数や関数の存在を教えてやる必要がありました。

現在の我々のコンパイラと同じように、関数は名前が存在するかどうかがチェックされるだけで、引数の型や個数が一致しているかどうかはチェックされません。想定している個数の引数をスタックに積んだあとに、おもむろに関数本体にジャンプすれば関数呼び出しが成功するので、それでよしとしていたのでしょう。

foutというのは出力先のファイルディスクリプタの番号を持っているグローバル変数です。この頃にはまだfprintfが存在しておらず、標準出力ではなく標準エラー出力に文字列を書き出すためには、グローバル変数経由で出力先をスイッチする必要がありました。

errorの中ではprintfが2回呼ばれています。2回目のprintfではフォーマット文字列に加えて2つの値が渡されています。では、1つの値だけを取るようなエラーメッセージを表示するときにはどうしていたのでしょうか？

実はこの関数は、単に無理やりerror("invalid number: %d", n)というように少ない引数で読んでも正しく動作します。関数の引数チェックがこの時点では存在しなかったことを思い出してください。s、p1、p2といった引数は単にスタックポインタから1、2、3番目のワードを指しているだけで、実際にp2に相当する値が渡されているかどうかはコンパイラは気にしません。printfは、第一引数の文字列に含まれる%dや%sの個数ぶんだけ余分な引数にアクセスするので、%dをひとつだけ含むメッセージの場合、p2はまったくアクセスされません。したがって引数の個数が一致していなくても問題ないのです。

このように初期のCコンパイラには、現時点での9ccと類似した点がたくさんあります。

もう1つコードの例を見てみましょう。下のコードは、渡された文字列を静的に確保された領域にコピーして、その領域の先頭を指すポインタを返す関数です。つまりこれは静的な領域を使うstrdupのような関数です。

copy(s)
char s[]; {
  extern tsp;
  char tsp[], otsp[];

  otsp = tsp;
  while(*tsp++ = *s++);
  return(otsp);
}

この当時はint *pという形式の宣言の構文が考案されていませんでした。そのかわりにポインタ型はint p[]というように宣言します。関数の引数リストと関数本体との間に変数定義のようなものが入っていますが、これはsをポインタ型として宣言するためのものです。

この初期のCコンパイラには特筆するべきことが他にもあります。

• この時点では構造体は存在していませんでした。
• &&や||といった演算子もまだありません。この頃は&や|がifなどの条件式の中でだけ論理演算子になるという文脈依存の動作になっていました。
• +=といった演算子は=+というように書いていました。これはi = -1のつもりでうっかりi=-1と書いてしまうと、現代でいうところのi -= 1になってしまうという問題があります。
• 整数型はcharとintだけで、shortやlongは存在しません。「関数ポインタの配列」といった型を宣言する構文は存在せず、複雑な型を記述することができませんでした。そのほかにもいろいろな機能が欠けています。

とはいえ、このCコンパイラは、上のソースコードからわかるようにCで書かれていました。構造体すらない時代にすでにCはセルフホストしていたのです。

古いソースコードを見ると、Cの一部のわかりにくい文法がなぜ現在の形になってしまったのかを推測することもできます。externかautoかintかcharの後ろに必ず変数名が来る、という文法なら変数定義のパースは簡単です。ポインタを表す[]も単に変数名の直後に来るだけならパースするのは簡単です。ただし、この文法を、この初期のコンパイラで見えている方向性に沿って発展させていくと、現在の不必要に複雑な形になってしまうのもわかるような気がします。

さて、1972年にUnixとCの共同開発者のDennis Ritchieが行っていたのは、まさにインクリメンタルな開発でした。彼は、Cそのものを発展させるのと平行して、Cを使ってそのコンパイラを書いていたのです。現在のCは、言語の機能追加を続ける中で特別なポイントに達した何らかの完成形というわけではなく、単にDennis Ritchieがある時点で、これで言語の機能は十分、と思ったところで言語として完成ということになっただけです。

我々のコンパイラでも最初から完成形を追い求めることはしませんでした。Cの完成形は特別な意味があるものではないので、それを特別に追い求めることにそこまで意味はないでしょう。どの時点でもリーズナブルな機能のセットを持った言語として開発を続けていって、最終的にCにする、というのは、最初のCコンパイラがそうしていた由緒正しい開発手法なのです。自信を持って開発を進めていきましょう！

x86-64命令セット チートシート

この章では、このコースで製作するコンパイラで利用するx86-64命令セットの機能をまとめました。この章では簡潔に表現するために以下の省略記法を使いました。

• src, dst: 同じサイズの2つの任意のレジスタ
• r8, r16, r32, r64: それぞれ8ビット、16ビット、32ビット、64ビットのレジスタ
• imm: 即値
• reg1:r[src] 2つのレジスタreg1、reg2`をそれぞれ上位ビットと下位ビットとして、128ビットのような1つのレジスタに入らない大きな数を表す場合の記法

整数レジスタの一覧

関数から戻る際に元の値に戻さなくてよいレジスタには✔をつけました。RAXは関数からの返り値です。可変長引数を呼び出す場合は、RAXに浮動小数点数の引数の個数をセットします。

メモリアクセス

関数呼び出し

条件分岐

条件代入

整数・論理演算

Gitによるバージョン管理

GitはもともとLinuxカーネルのバージョン管理のために開発されました。Linuxカーネルは数千人の開発者からなる巨大なプロジェクトなので、そのための複雑なワークフローを満たすべく、Gitは豊富な機能を持っています。これらの機能は便利ではあるのですが、自分しかコミッターがいない個人開発ではGitの機能を使いこなす必要はありません。Gitをマスターするとなるとかなりたくさんのことを学ぶ必要がありますが、このコースで覚えるべき事項はごくわずかです。Gitを使った開発が初めてだという人のために以下にチートシートを用意しました。

• git add ファイル名

  新規作成したファイルをリポジトリに加える

• git commit -A

  作業ツリーに行ったすべての変更をまとめてコミットする（エディタが立ち上がるのでコミットメッセージを入力する）

• git reset --hard

  前回のコミット以降に作業ツリーに行った変更を全て取り消す

• git log -p

  過去のコミットを見る

• git push

  Githubなどアップストリームにリポジトリをプッシュする

バージョン管理システムを初めて使う人のために、Gitとバージョン管理システムの概念について少し説明しておきましょう。

Gitは、ファイルの変更履歴が入ったデータベースの管理ツールです。そのデータベースのことをリポジトリといいます。Githubなどからリポジトリをクローンすると、リポジトリがダウンロードされて、そのあとリポジトリから、デフォルトの最新の状態のディレクトリツリーが、あるディレクトリ以下にすべて展開されます。

リポジトリから展開されたディレクトリツリーのことを「作業ツリー」といいます。作業ツリーにあるソースファイルをエディタで編集したりコンパイルするわけですが、作業ツリー自体はリポジトリの一部分というわけではありません。作業ツリーはいわばzipファイルから展開されたファイルのようなもので、そちらにいくら変更を加えても、元々のリポジトリはそのままの状態で残っています。

自分が作業ツリーに対して行った変更は、キリの良いところで「コミット」という単位にまとめてリポジトリに書き戻します。これによりデータベースが更新され、そのあとまた別の変更点を作っていくことができるわけです。Gitを使う場合は、ファイルを変更してコミット、という繰り返しで開発を進めていくことになります。

コミットするときの注意点

コミットメッセージは日本語でよいのできちんと書いてください。例えば「*と/を演算子として追加、ただし演算子の優先順位は処理しない」といった一行メッセージでよいです。

コミット単位はなるべく小さく分けてください。例えばコードを変更していると、ちょっとしたリファクタリングがしたくなるものですが、そういう場合はリファクタリングは別のコミットとしてコミットしてください。2つ以上の別々の機能を1つのコミットにまとめるのは望ましくありません。

Gitの高度な機能を使う必要はありません。たとえばブランチを使う必要はないはずです。

機能追加のコードは、その機能をテストするコードと必ず一緒にコミットするようにしてください。また、コミットするときは、まずテストを走らせてみて、既存機能が壊れていなくて、新しい機能もきちんと動いていることを確認してからコミットするようにしてください。別の言い方をすると、どの時点でのリポジトリをチェックアウトしてきても、コンパイルとテストは通る、ということを目指してもらいます。ただしうっかりテストが通らないものをコミットしてしまったときは、gitのコミットログを改変してまで修正する必要はありません。単に次のコミットで修正を入れてください。

Gitの内部構造

Gitのドキュメントを読んでいるとトリッキーな機能がたくさんあるのですが、Gitが原理的にどのようにデータを保存しているかというモデルを自分の中に構築しておくと、機能が理解しやすくなります。そこでここではGitの内部構造について解説します。

Gitは、ユーザープログラムとして実装されたファイルシステムの一種です。Gitのデータベースの構造はファイルシステムと大変よく似ているのです。ただし、通常のファイルシステムはファイル名を使ってファイルにアクセスするのに対して、Gitではファイルのハッシュ値を名前として使うところが異なります。

ファイルの内容によって名前が決まるこういった仕組みのことを、content-addressableといいます。content-addressableなファイルシステムでは、名前が同じであれば内容は同一です。また、内容が異なっているファイルが同じ名前（同じハッシュ値）を持つことはできません。これは暗号的にセキュアなハッシュ関数を使うことにより保証されています。こういったファイルシステムでは、ファイルに別個に名前をつける必要がなく、名前が決まればファイルの内容も一意に決まるという性質があります。

コミットというのもGitの内部ではファイルになっています。そのファイルには、コミットメッセージのほかに、そのコミットに属するファイルのハッシュ値や、その一つ前のコミットのハッシュ値が書かれています。

Gitのリポジトリからファイルを取り出すためには、自分の欲しいファイルのハッシュ値がわかっていなければなりません。

コミットファイルのハッシュ値がわからなければコミットファイルが得られない、というのは鶏と卵の問題のような感じがしますが、実際には、リポジトリにはコミットファイルのハッシュ値とそれに対する名前の目録が入っているので、それを使ってコミットを見つけることができます。たとえばリポジトリには、"master"という名前（デフォルトで作業ツリーに展開される履歴）のコミットのハッシュ値はda39a3ee5e...である、といった情報が入っています。この情報を使うことで、Gitはmasterに属するファイルを作業ツリーに展開することができます。

「コミットを行う」というのが内部的にどうなっているかというと、変更があったファイルをGit内部のファイルシステムに追加し、それらのファイルのハッシュ値や一つ前のコミットのハッシュ値を含んだコミットファイルを同様に追加し、最後にそのコミットファイルのハッシュ値で目録を更新する、となっているわけです。

例えばmasterの最後のコミットをなかったことにするためには（やらないほうがよいですが）、masterが指しているコミットファイルを見て一つ前のコミットのハッシュ値を得て、そのハッシュ値でmasterを上書きすればよいわけです。「ブランチ」というのも、あるコミットを一つ前のコミットとして持っているコミットが2つ以上あって、その2つのコミットが目録に載っている、という話にすぎません。

こういったcontent-addressableなバージョン管理システムにはセキュリティ上の利点もあります。あるコミットの名前（コミットファイルのハッシュ値）には、そのコミットに属するすべてのファイルのハッシュ値と、その前のコミットファイルのハッシュ値が含まれています。その前のコミットファイルにはさらにその前のコミットファイルのハッシュが含まれているので、結局のところ最新のコミットにたどり着くすべてのコミットのハッシュ値が、最新のコミットのハッシュ値の計算に含まれていることになります。したがって、ハッシュ値を変えないままコミットの内容や履歴をこっそり改変することが原理的に不可能になっているのです。面白い性質ですね。

Gitの機能を学ぶ時には、このcontent-addressableなファイルシステムを常に念頭に置いてみてください。きっといろいろなことがわかりやすくなるはずです。