はじめに

このオンラインブックは執筆中です。完成版ではありません。フィードバックフォーム

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

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

コンパイラは、構文解析、中間パス、コード生成といった複数のステージに概念的に分割することができます。よくある教科書的アプローチでは、それぞれのトピックについて章を立てて解説を行うことになりますが、そのようなアプローチの本は話が途中で狭く深くなりすぎて、読者がついていけなくなりがちです。

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

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

そのようなインクリメンタルな開発手法では、細かいコミットを刻みつつ、ステップ・バイ・ステップでコンパイラを作っていくことになります。この開発手法では、どのコミットにおいてもコンパイラはある意味常に「完成形」です。ある段階ではただの電卓レベルのことしかできないかもしれないし、ある段階では相当限定されたCのサブセットかもしれないし、ある段階ではほぼCと言える言語かもしれない、というようになります。ポイントは、どの段階でも、その時点の完成度に合わせたリーズナブルな仕様の言語を目指すという点です。開発中に一部の機能だけを突出してC言語ぽくすることは行いません。

データ構造やアルゴリズム、コンピュータサイエンス的な知識についても、開発段階に応じて順次解説していきます。

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

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

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

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

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

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

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

本書の表記法

関数や式、コマンドなどは本文中で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'.

本書の想定する開発環境

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

$ sudo apt update
$ sudo apt install -y gcc make git binutils libc6-dev

macOSはLinuxとアセンブリのソースレベルでかなり互換性がありますが、完全互換ではありません（具体的には「スタティックリンク」という機能がサポートされていません）。この本の内容に従ってmacOS対応のCコンパイラを作成するのは不可能ではないものの、実際に試してみると、細かな点でいろいろな非互換性に悩まされることになるでしょう。Cコンパイラ作成のテクニックと、macOSとLinuxの差異を同時に学ぶというのは、お勧めできることではありません。何かがうまく動かない場合、どちらの理解が間違っているのかよくわからなくなってしまうからです。

したがって本書ではmacOSは対象外とします。macOSでは何らかの仮想環境を使ってLinux環境を用意するようにしてください。Linuxの仮想環境を用意するのが初めてだという読者は、Dockerを使って開発環境を作成する方法を付録3にまとめておいたので参考にしてください。

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

著者について

植山 類（@rui314）。高速なリンカlldのオリジナル作者かつ現メンテナで、lldはAndroid（バージョンQ以降）やFreeBSD（12以降）、Nintendo Switch、ChromeやFirefoxなど、多くのOSやプロジェクトにおいて、実行ファイルを作成する標準リンカとして採用されています（したがって筆者が書いたツールが作成したバイナリが、読者の手元のコンピュータに入っている可能性は高い）。コンパクトなCコンパイラ8ccの作者でもあります。ソフトウェアに関するエッセイは主にnoteに書いています。

機械語とアセンブラ

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

CPUとメモリ

コンピュータを構成するコンポーネントは、大きくCPUとメモリにわけることができます。メモリはデータを保持できるデバイスで、CPUは、そのメモリを読み書きしながら何らかの処理を行なっていくデバイスです。

概念的に、CPUにとってはメモリはランダムアクセス可能な巨大なバイトの配列のように見えます。CPUがメモリにアクセスするときは、メモリの何バイト目にアクセスしたいのかという情報を数値で指定するわけですが、その数値のことを「アドレス」といいます。例えば「アドレス16から8バイトのデータを読む」というのは、バイトの配列のように見えているメモリの16バイト目から8バイト分のデータを読む、という意味です。同じことを「16番地から8バイトのデータを読む」ということもあります。

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

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

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

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

特定の機械語の命令を総称として「命令セット」（instruction set）といいます。命令セットは一種類というわけではなく、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番地に置かれるようになっていて、プログラムカウンタが0x3d58のときにこの命令が実行されることになります。その次に続いている4つの16進数の数値は実際の機械語です。CPUはこのデータを読んで、それを命令として実行します。sub rsp,0x8というのは、その機械語命令に対応するアセンブリです。CPUの命令セットについては章を分けて説明しますが、この命令は、RSPというレジスタから8を引く（subtract = 引く）という命令です。

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

簡単な例

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

int main() {
  return 42;
}

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

$ cc -o test1 test1.c
$ ./test1
$ echo $?
42

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

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

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

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

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

$ cc -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コードに対応するアセンブリは次のようになります。

.intel_syntax noprefix
.global plus, main

plus:
        add rsi, rdi
        mov rax, rsi
        ret

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

1行目はアセンブリの文法を指定する命令です。2行目の.globalから始まる行は、plusとmainという2つの関数がファイルスコープではなくプログラム全体から見える関数だということをアセンブリに指示しています。これはさしあたり無視してかまいません。

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

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

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

したがってcall命令が実行されると、CPUはplus関数を実行し始めることになります。

plus関数に着目してください。plus関数には3つの命令があります。

addは足し算を行う命令です。この場合には、RSIレジスタとRDIレジスタを足した結果が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コンパイラは普通はアセンブリを出力する
• Cの関数はアセンブリでも関数になる
• 関数呼び出しはスタックを使って実装されている

電卓レベルの言語の作成

この章では、Cコンパイラ作成の最初のステップとして、四則演算やそのほかの算術演算子をサポートして、次のような式をコンパイルできるようにします。

30 + (4 - 2) * -5

これは他愛もない目標のようですが、実は結構難しい目標です。数式には、カッコの中の式が優先されるとか、掛け算が足し算より優先されるといった構造があって、それを何らかの方法で理解しなければ正しく計算を行うことはできません。しかし、入力として与えられる数式はただのフラットな文字の列であって、構造化されたデータではありません。式を正しく評価するためには、文字の並びを解析して、そこに隠れた構造をうまく導き出す必要があります。

こういった構文解析の問題は、何の前提知識もなしに解こうとすると相当大変です。実際、こういった問題は昔は難しい問題だと考えられていて、特に1950年代から1970年代にかけて精力的に研究が行われて、いろいろなアルゴリズムが開発されてきました。その成果のおかげで、今では構文解析は、やり方さえ分かっていればさほど難しい問題ではなくなっています。

この章では、構文解析の最も一般的なアルゴリズムの一つである「再帰下降構文解析法」（recursive descent parsing）を説明します。GCCやClangなど、みなさんが日常的に使っているC/C++コンパイラも、再帰下降構文解析法を使っています。

コンパイラに限らず、何らかの構造のあるテキストを読むというニーズは、プログラミングをしているとよくでてきます。この章で学ぶテクニックはそういった問題にもそのまま使うことができます。この章で学ぶ構文解析の手法は、大げさではなく一生物のテクニックといってよいでしょう。この章を読んでアルゴリズムを理解して、自分のプログラマとしての道具箱に構文解析の技を入れておきましょう。

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

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

このステップではまずその最も簡単な言語を実装することにしましょう。

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

.intel_syntax noprefix
.global main

main:
        mov rax, 42
        ret

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

読者はここで、「こんなプログラムはコンパイラとは言えない」と思うかもしれません。筆者も正直そう思います。しかし、このプログラムは、数値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 rax, 8     // Intel
mov $8, %rax   // AT&T

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

コンパイラ本体の作成

コンパイラには通常はファイルとして入力を与えますが、ここではファイルをオープンして読むのが面倒なので、コマンドの第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を実行して動作を確認してみましょう。

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

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

$ cat tmp.s
.intel_syntax noprefix
.global main
main:
  mov rax, 123
  ret

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

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

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

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

自動テストの作成

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

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

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

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

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

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

assert 0 0
assert 42 42

echo OK

上記の内容でtest.shを作成し、chmod a+x test.shを実行して実行可能にしてください。実際にtest.shを走らせてみましょう。何もエラーが起きなければ、以下のようにtest.shは最後にOKを表示して終了します。

$ ./test.sh
0 => 0
42 => 42
OK

もしエラーが起きれば、test.shはOKを表示しません。その代わりにtest.shは、失敗したテストで想定されていた値と実際の値を以下のように表示します。

$ ./test.sh
0 => 0
42 expected, but got 123

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

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

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

makeによるビルド

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

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

CFLAGS=-std=c11 -g -static

9cc: 9cc.c

test: 9cc
        ./test.sh

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

.PHONY: test clean

上記のファイルを、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年代に開発された古いツールで、伝統的にこうなってしまっています。

ccには必ず-staticというオプションを渡すようにしてください。このオプションはダイナミックリンクという章で説明します。このオプションのの意味について今は特に考える必要はありません。

gitによるバージョン管理

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

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

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

*~
*.o
tmp*
a.out
9cc

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

$ git config --global user.name "Rui Ueyama"
$ git config --global user.email "ruiu@cs.stanford.edu"

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 -m "整数1つをコンパイルするコンパイラを作成"

-mオプションでコミットメッセージを指定します。-mオプションがない場合、gitはエディタを起動します。コミットがうまくいったことは以下のようにgit log -pを実行すると確認することができます。

$ git log -p
commit 0942e68a98a048503eadfee46add3b8b9c7ae8b1 (HEAD -> master)
Author: Rui Ueyama <ruiu@cs.stanford.edu>
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にプッシュされます。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に保存してアセンブルし、実行してみます。

$ cc -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行追加しておきましょう。

assert 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つの単語でできていると考えることができます。この「単語」のことを「トークン」（token）といいます。トークンの間にある空白文字というのは、トークンを区切るために存在しているだけで、単語を構成する一部分ではありません。したがって、文字列をトークン列に分割するときに空白文字を取り除くのは自然なことでしょう。文字列をトークン列に分割することを「トークナイズする」といいます。

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

現在の加減算ができる式の文法の場合、トークンの型は、+、-、数値の3つです。さらにコンパイラの実装の都合上、トークン列の終わりを表す特殊な型を1つ定義しておくとプログラムが簡潔になります（文字列が'\0'で終わっているのと同じです）。トークンはポインタで繋いだ連結リストになるようにして、任意の長さの入力を扱えるようにしてみましょう。

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

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

// トークンの種類
typedef enum {
  TK_RESERVED, // 記号
  TK_NUM,      // 整数トークン
  TK_EOF,      // 入力の終わりを表すトークン
} TokenKind;

typedef struct Token Token;

// トークン型
struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
};

// 現在着目しているトークン
Token *token;

// エラーを報告するための関数
// printfと同じ引数を取る
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進めて
// 真を返す。それ以外の場合には偽を返す。
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進める。
// それ以外の場合にはエラーを報告する。
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("'%c'ではありません", op);
  token = token->next;
}

// 次のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。
// それ以外の場合にはエラーを報告する。
int expect_number() {
  if (token->kind != TK_NUM)
    error("数ではありません");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// 新しいトークンを作成してcurに繋げる
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// 入力文字列pをトークナイズしてそれを返す
Token *tokenize(char *p) {
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // 空白文字をスキップ
    if (isspace(*p)) {
      p++;
      continue;
    }

    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error("トークナイズできません");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

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

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

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

  // 式の最初は数でなければならないので、それをチェックして
  // 最初のmov命令を出力
  printf("  mov rax, %d\n", expect_number());

  // `+ <数>`あるいは`- <数>`というトークンの並びを消費しつつ
  // アセンブリを出力
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

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

150行程度のあまり短いとはいえないコードですが、あまりトリッキーことは行なっていないので、上から読んでいけば読めるはずです。

上のコードで使われているプログラミングテクニックをいくつか説明しておきましょう。

• パーサが読み込むトークン列は、グローバル変数tokenで表現することにしました。パーサは、連結リストになっているtokenをたどっていくことで入力を読み進めていきます。このようなグローバル変数を使うプログラミングスタイルは、きれいなスタイルには見えないかもしれません。しかし実際には、ここで行なっているように、入力トークン列を標準入力のようなストリームとして扱うほうがパーサのコードが読みやすくなることが多いようです。従ってここではそのようなスタイルを採用しました。
• tokenを直接触るコードはconsumeやexpectといった関数にわけて、それ以外の関数ではtokenを直接触らないようにしました。
• tokenize関数では連結リストを構築しています。連結リストを構築するときは、ダミーのhead要素を作ってそこに新しい要素を繋げていって、最後にhead->nextを返すようにするとコードが簡単になります。このような方法ではhead要素に割り当てられたメモリはほとんど無駄になりますが、ローカル変数をアロケートするコストはほぼゼロなので、特に気にする必要はありません。
• callocはmallocと同じようにメモリを割り当てる関数です。mallocとは異なり、callocは割り当てられたメモリをゼロクリアします。ここでは要素をゼロクリアする手間を省くためにcallocを使うことにしました。

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

assert 41 " 12 + 34 - 5 "

Unixのプロセスの終了コードは0〜255の数字ということになっているので、テストを書く際には、式全体の結果が0〜255に収まるようにしてください。

テストファイルをgitレポジトリに追加すれば、このステップは完了です。

ステップ4：エラーメッセージを改良

ここまでに作ったコンパイラでは、入力が文法的に間違っていた場合、どこかにエラーがあったことくらいしかわかりません。その問題をこのステップで改良してみましょう。具体的には下のような直感的にわかるエラーメッセージを表示できるようにします。

$ ./9cc "1+3++" > tmp.s
1+3++
    ^ 数ではありません

$ ./9cc "1 + foo + 5" > tmp.s
1 + foo + 5
    ^ トークナイズできません

このようなエラーメッセージを表示するためには、エラーが起きたときに、それが入力の何バイト目なのかを知ることができる必要があります。そのために、プログラムの文字列全体をuser_inputという変数に保存することにして、その文字列の途中を指すポインタを受け取るエラー表示関数を新たに定義することにしましょう。そのコードを以下に示します。

// 入力プログラム
char *user_input;

// エラー箇所を報告する
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // pos個の空白を出力
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

error_atが受け取るポインタは、入力全体を表す文字列の途中を指しているポインタです。そのポインタと、入力の先頭を指しているポインタとの差を取ると、エラーのある場所が入力の何バイト目かわかるので、その場所を目立つように^でマークすることができます。

argv[1]をuser_inputに保存するようにして、error("数ではありません")といったコードをerror_at(token->str, "数ではありません")といったコードにアップデートすれば、このステップは完了です。

実用レベルのコンパイラであれば、入力にエラーがあるときの振る舞いについてもテストを書くべきですが、今のところエラーメッセージはデバグを助けるために出力しているだけなので、この段階では特にテストは書かなくて構いません。

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

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

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

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

この章では、コーディングは一休みにして、構文解析のテクニックについて学んでいきましょう。この章では、構文解析のテクニックについて次の順番で説明をします。

1. パーサの出力のデータ構造を知ることで、最終的なゴールをまず把握する
2. 文法規則を定義するルールを学ぶ
3. 文法規則を定義するルールをもとに、パーサを書くテクニックを学ぶ

木構造による文法構造の表現

プログラミング言語のパーサの実装においては、入力はフラットなトークンの列で、出力は入れ子構造を表す木にするのが普通です。本書で作成するコンパイラもその構成に従っています。

C言語ではifやwhileといった文法的な要素を入れ子にすることができます。こういったものを木構造で表すというのは自然な表現方法といってよいでしょう。

数式には、カッコの中を先に計算するとか、乗除算を加減算より先に計算するといった構造があります。こういった構造は、一見、木には見えないかもしれませんが、実際には木を使うと大変シンプルに式の構造を表すことができます。たとえば1*(2+3)という式は、次の木により表現されていると考えることができます。

木の末端から順に計算していくというルールを採用した場合、上記の木は、1に2+3をかける、という式を表していることになります。つまり、上記の木では、1*(2+3)の具体的な計算順序が木の形そのもので表現されていることになります。

別の例を示します。下の木は7-3-3を表す木です。

上記の木においては、「引き算は左から順に計算しなければいけない」というルールの適用結果が、木の形として明示的に表されています。つまり、上記の木は(7-3)-3 = 1という式を表しているのであって、7-(3-3) = 7という式を表しているわけではありません。もし後者の式であったなら、それを表す木は左ではなく右に深くなるようになります。

左から計算しなければならない演算子のことを「左結合」の演算子、右から計算しなければならない演算子のことを「右結合」の演算子といいます。Cでは、代入の=を除いて、ほとんどの演算子は左結合として定義されています。

木構造においては、木を深くすることでいくらでも長い式を表すことができます。次の木は、1*2+3*4*5を表す木です。

上記のような木のことを「構文木」（こうぶんぎ、syntax tree）といいます。特に、グループ化のためのカッコなどの冗長な要素を木の中に残さずになるべくコンパクトに表現した構文木のことを「抽象構文木」（abstract syntax tree、AST）といいます。上記の構文木は、どれも抽象構文木ということができます。

抽象構文木はコンパイラの内部表現なので実装の都合で適当に定義してかまいません。とはいえ、足し算や掛け算のような算術演算子は、左辺と右辺の2つに対する演算として定義されているので、どのコンパイラでも2分木にするのが自然でしょう。一方、関数本体の式など、順番に実行されるだけで何個にでもなりうるものは、すべての子要素をフラットに持つ木で表すのが自然でしょう。

構文解析におけるゴールは抽象構文木を構築することです。コンパイラは、まず構文解析を行って入力のトークン列を抽象構文木に変換し、その構文木を次はアセンブリに変換することになります。

生成規則による文法の定義

さて、次はプログラミング言語の構文の記述方法について学んでいきましょう。プログラミング言語の構文の大部分は「生成規則」（production rule）というものを使って定義されています。生成規則は文法を再帰的に定義するルールです。

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

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

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

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

BNFによる生成規則の記述

生成規則をコンパクトかつわかりやすく記述するための一つの記法として、BNF（Backus–Naur form）と、それを拡張したEBNF（Extended BNF）というものがあります。この本では、Cの文法をEBNFを使って説明していきます。この節では、まずBNFを説明し、その後にEBNFの拡張部分を説明します。

BNFでは、一つ一つの生成規則をA = α₁α₂⋯という形式で表します。これは記号Aをα₁α₂⋯に展開できるという意味です。α₁α₂⋯は0個以上の記号の列で、それ以上展開できない記号と、さらに展開される（いずれかの生成規則で左辺に来ている）記号の両方を含むことができます。

それ以上展開できない記号を「終端記号」（terminal symbol）、どれかの生成規則の左辺に来ていて展開できる記号を「非終端記号」（nonterminal symbol）といいます。このような生成規則で定義される文法のことを一般に「文脈自由文法」（context free grammar）といいます。

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

生成規則の右辺は、空でもかまいません。そのようなルールでは、左辺の記号は長さ0の記号列に（つまり無に）展開されることになります。ただし、表示上、右辺を省略すると意味がわかりづらくなるので、そのような場合には何もないことを表す記号としてε（イプシロン）を右辺に書いておくというのが普通のBNFのルールです。本書でもそのルールを採用しています。

文字列はダブルクオートでくくって"foo"のように書きます。文字列は常に終端記号です。

上記が基本的なBNFのルールです。EBNFでは、BNFのルールに加えて、以下の記号を使って複雑なルールを簡潔に書き下すことができます。

例えばA = ("fizz" | "buzz")*では、Aは、"fizz"または"buzz"が0回以上繰り返された文字列、すなわち、

• ""
• "fizz"
• "buzz"
• "fizzfizz"
• "fizzbuzz"
• "buzzfizz"
• "buzzbuzz"
• "fizzfizzfizz"
• "fizzfizzbuzz"
• ⋯⋯

のいずれかに展開することができます。

単純な生成規則

EBNFを使った文法の記述の例として、次の生成規則を考えてみてください。

expr = num ("+" num | "-" num)*

numは別途どこかで数値を表す記号として定義されているものとします。この文法においては、exprは、まずnumが1つあって、その後に0個以上の「+とnum、あるいは-とnum」があるものということになります。この規則は、実は加減算の式の文法を表しています。

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

expr → num → "1"

expr → num "+" num
     → "10" "+" "5"

expr → num "-" num "+" num
     → "42" "-" "30" "+" "2"

このような展開の手順を、矢印を使って展開順ごとに表すだけではなく、木構造で表すこともできます。上の式の構文木を以下に示します。

木構造で表すことによって、どの非終端記号がどの記号に展開されているのかがわかりやすくなりました。

上の図のような、入力に含まれるすべてのトークンを含んだ、文法に完全に一対一でマッチしている構文木は、「具象構文木」（concrete syntax tree）と呼ばれることもあります。この用語は、抽象構文木と対比させたいときによく使われます。

なお、上記の具象構文木では、加減算を左から計算するというルールが木の形では表現されていません。そのようなルールは、ここで説明する文法では、EBNFを使って表現するのではなく、言語仕様書の中に文章で但し書きとして「加減算は左から先に計算します」と書いておくことになります。パーサではEBNFと但し書きの両方を考慮に入れて、式を表すトークン列を読み込んで、式の評価順を適切に表現している抽象構文木を構築することになります。

従って、上記の文法では、EBNFが表す具象構文木とパーサの出力となる抽象構文木の形が、おおまかにしか一致しません。抽象構文木と具象構文木がなるべく同じ構造になるように文法を定義することも可能ですが、そうなると文法が冗長になって、パーサをどう書けばよいのかわかりづらくなってしまいます。上記のような文法は、形式的な文法の記述の厳密さと、自然言語による補足のわかりやすさのバランスが取れた、扱いやすい文法の表現方法です。

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

生成規則は文法を表現するための大変強力なツールです。演算子の優先順位も、文法を工夫すると、生成規則の中で表すことができます。その文法を以下に示します。

expr = mul ("+" mul | "-" mul)*
mul  = num ("*" num | "/" num)*

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

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

再帰を含む生成規則

生成文法では再帰的な文法も普通に書くことができます。下は、優先順位のカッコを四則演算に追加した文法の生成規則です。

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

上記の文法を以前の文法と比べてみると、今までnumが許されていたところに、primary、すなわちnumあるいは"(" expr ")"が来てよいことになっています。つまりこの新しい文法では、丸カッコでくくられた式というものは、いままでの単一の数と同じ「くっつき具合」で扱われることになります。一つ例を見てみましょう。

次の木は1*2の構文木です。

次の木は1*(2+3)の構文木です。

2つの木を比べてみると、mulの右の枝のprimaryの展開結果だけが異なることがわかります。展開結果の末端に現れるprimaryというのは、1つの数字に展開してもよいし、カッコでくくられた任意の式に展開してもよい、というルールが、木構造の中にきちんと反映されています。このように簡単な生成規則でカッコの優先順位も扱えるというのは少し感動的ではないでしょうか。

再帰下降構文解析

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

実はある種の生成規則については、規則が与えられれば、その規則から生成される文にマッチする構文木を求めるコードを機械的に書いていくことができます。ここで説明する「再帰下降構文解析法」はそういったテクニックの一つです。

例として四則演算の文法を考えてみましょう。四則演算の文法を再掲します。

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

再帰下降構文解析法でパーサを書くときの基本的な戦略は、これらの非終端記号一つ一つをそのまま関数一つ一つにマップするというものです。したがってパーサはexpr、mul、primaryという3つの関数を持つことになります。それぞれの関数は、その名前のとおりのトークン列をパースします。

具体的にコードで考えてみましょう。パーサに渡される入力はトークンの列です。パーサからは抽象構文木を作って返したいので、抽象構文木のノードの型を定義しておきましょう。ノードの型を以下に示します。

// 抽象構文木のノードの種類
typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // 整数
} NodeKind;

typedef struct Node Node;

// 抽象構文木のノードの型
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
};

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

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

Node *new_node(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_node_num(int val) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = ND_NUM;
  node->val = val;
  return node;
}

さて、これらの関数とデータ型を使ってパーサを書いていきましょう。+や-は左結合の演算子ということになっています。左結合の演算子をパーズする関数は、パターンとして次のように書きます。

Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_node(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_node(ND_SUB, node, mul());
    else
      return node;
  }
}

consumeというのは以前のステップで定義した関数で、入力ストリームの次のトークンが引数とマッチするときに、入力を1トークン読み進めて真を返す関数です。

expr関数をよく読んでみてください。expr = mul ("+" mul | "-" mul)*という生成規則が、そのまま関数呼び出しとループにマップされていることがわかると思います。上記のexpr関数から返される抽象構文木では、演算子は左結合、つまり返されるノードの左側の枝のほうが深くなるようになっています。

expr関数が使っているmul関数も定義してみましょう。*や/も左結合の演算子なので、同じパターンで記述することができます。その関数を下に示します。

Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_node(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_node(ND_DIV, node, primary());
    else
      return node;
  }
}

上記のコードの関数呼び出し関係は、mul = primary ("*" primary | "/" primary)*という生成規則にそのまま対応しています。

最後にprimary関数を定義してみましょう。primaryが読み込むのは左結合の演算子ではないので、上記のパターンのコードにはなりませんが、primary = "(" expr ")" | numという生成規則をそのまま関数呼び出しに対応させることで、primary関数は以下のように記述することができます。

Node *primary() {
  // 次のトークンが"("なら、"(" expr ")"のはず
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  // そうでなければ数値のはず
  return new_node_num(expect_number());
}

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

最初に呼ばれるのはexprです。式というのは全体としてexprであると決めつけて（この場合、実際にそうなわけですが）入力を読み始めるわけです。そうすると、expr→mul→primaryというように関数呼び出しが行われて、1というトークンが読み込まれ、exprには、返り値として1を表す構文木が返ってきます。

次に、exprの中のconsume('+')という式が真になるので、+というトークンが消費され、mulが再度呼び出されます。この段階での入力の残りは2*3です。

mulからは前回と同様にprimaryが呼び出されて、2というトークンが読み込まれますが、今回はmulはすぐにはリターンしません。mulの中のconsume('*')という式が真になるので、mulは再度primaryを呼び出して、3というトークンを読み込みます。結果としてmulからは2*3を表す構文木が返ることになります。

リターンした先のexprでは、1を表す構文木と2*3を表す構文木が組み合わされて、1+2*3を表す構文木が構築され、それがexprの返り値になります。つまり正しく1+2*3がパースできたというわけです。

関数の呼び出し関係とそれぞれの関数が読み込むトークンを図に示すと次のようになります。下の図では、1+2*3全体に対応したexprの層がありますが、これが入力全体を読み込むexprの呼び出しを表しています。exprの上に2つのmulがありますが、それらは1と2*3を読み込む別のmulの呼び出しを表しています。

もう少し複雑な例を下に示します。下の図は、1*2+(3+4)をパースしているときの関数の呼び出し関係を表しています。

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

上記のような1つの生成規則を1つの関数にマップするという構文解析の手法を「再帰下降構文解析」といいます。上記のパーサではトークンを1つだけ先読みして、どの関数を呼び出すか、あるいはリターンするか、ということを決めていましたが、そのようにトークンを1つだけ先読みする再帰下降パーサのことをLL(1)パーサといいます。また、LL(1)パーサが書ける文法のことをLL(1)文法といいます。

スタックマシン

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

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

しかし、乗除算が含まれる場合は中間的な計算結果が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->kind == 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->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");
}

特にパースやコード生成において重要なポイントではないのですが、トリッキーな仕様のidiv命令が上のコードでは使われているので、それについて説明しておきましょう。

idivは符号あり除算を行う命令です。x86-64のidivが素直な仕様になっていれば、上のコードでは本来idiv rax, rdiのように書きたかったところですが、そのような2つのレジスタをとる除算命令はx86-64には存在しません。その代わりに、idivは暗黙のうちにRDXとRAXを取って、それを合わせたものを128ビット整数とみなして、それを引数のレジスタの64ビットの値で割り、商をRAXに、余りをRDXにセットする、という仕様になっています。cqo命令を使うと、RAXに入っている64ビットの値を128ビットに伸ばしてRDXとRAXにセットすることができるので、上記のコードではidivを呼ぶ前にcqoを呼んでいます。

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

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

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

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

  // トークナイズしてパースする
  user_input = argv[1];
  token = tokenize(user_input);
  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;
}

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

assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'

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

ステップ6：単項プラスと単項マイナス

引き算を行う-演算子は、5-3のように2つの項の間に書くだけではなく、-3のように単独の項の前に書くことができます。同様に+演算子も左辺を省略して+3のように書くことができます。このような1つの項だけを取る演算子のことを「単項演算子」（unary operator）といいます。それに対して、2つの項をとる演算子は「2項演算子」（binary operator）といいます。

Cには+と-以外に、ポインタを取得する&やポインタをデリファレンスする*などの単項演算子が存在しますが、このステップでは+と-だけを実装することにします。

単項+と単項-は、2項の+や-と同じ記号ですが、定義は異なっています。2項の-は左辺から右辺を引く演算として定義されていますが、単項-にはそもそも左辺がないので、2項-の定義はそのままでは意味をなしません。Cでは単項-は右辺の正負を反転する演算として定義されています。単項+は右辺をそのまま返す演算子です。これは特になくても構わない演算子なのですが、単項-が存在するついでに存在しています。

+や-は、単項と2項という、似て異なる定義の同名の演算子が複数存在していると考えるのが適切です。単項か2項かというのは文脈で見分けることになります。単項+/-を含んだ新しい文法は次のようになります。

expr    = mul ("+" mul | "-" mul)*
mul     = unary ("*" unary | "/" unary)*
unary   = ("+" | "-")? primary
primary = num | "(" expr ")"

上記の新しい文法ではunaryという新しい非終端記号が増えていて、mulがprimaryではなくunaryを使うようになっています。X?は、オプショナルな、すなわちXが0回か1回出現する要素を表すEBNFの構文です。unary = ("+" | "-")? primaryというルールでは、unaryという非終端記号は、+か-が1つあってもなくてもよくて、そのあとにprimaryが続いているものを表しています。

-3や-(3+5)、-3*+5などの式がこの新たな文法にマッチしていることを確認してみてください。以下に-3*+5の構文木を示します。

この新しい文法に従うようにパーサを変更してみましょう。例によって、文法をそのまま関数呼び出しにマップすることでパーサの変更は完了するはずです。unaryをパースする関数を下に示します。

Node *unary() {
  if (consume('+'))
    return primary();
  if (consume('-'))
    return new_node(ND_SUB, new_node_num(0), primary());
  return primary();
}

ここではパースの段階で+xをxに、-xを0-xに置き換えてしまうことにしました。したがってこのステップではコード生成器の変更は必要ありません。

テストを数個書いて、単項+/-を追加するコードと一緒にチェックインすれば、このステップは完了です。テストを書く時には、テスト結果を0〜255の範囲に収めるようにしましょう。-10+20のような式は、単項-を使いつつも全体の値は正の数になっているので、こういったテストを使ってください。

ステップ7: 比較演算子

この節では、<、<=、>、>=、==、!=を実装します。これらの比較演算子は特殊な意味を持っているように見えますが、実際には+や-などと同じように、2つの整数を受け取って1つの整数を返す普通の2項演算子です。+が両辺を足した結果を返すように、例えば==は両辺が同じ場合は1を、違う場合は0を返します。

トークナイザの変更

今までに扱ってきた記号トークンは長さがどれも1文字で、コードでもそれを前提にしてきましたが、==などの比較演算子を扱うためにはコードを一般化する必要があります。文字列の長さをトークンに保存できるように、lenというメンバをToken構造体に保存することにしましょう。新しい構造体の型を下に示します。

struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
  int len;        // トークンの長さ
};

この変更に伴って、consumeやexpectといった関数にも変更を加えて、それらの関数が文字ではなく文字列を取るように改良する必要があります。変更を加えた例を以下に示します。

bool consume(char *op) {
  if (token->kind != TK_RESERVED ||
      strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;
  token = token->next;
  return true;
}

複数の文字からなる記号をトークナイズする場合、長いトークンから先にトークナイズする必要があります。たとえば残りの文字列が>から始まっている場合、まずstrncmp(p, ">=", 2)のように>=である可能性から先にチェックしないで、>から始まっている可能性をチェックしてしまうと、>=が>と=という2つのトークンとして誤ってトークナイズされてしまいます。

新しい文法

比較演算子のサポートをパーサに追加するために、比較演算子を加えた文法がどのようになるのかを考えてみましょう。今までに出てきた演算子を優先順位の低い順から高い順に書くと次のようになります。

1. == !=
2. < <= > >=
3. + -
4. * /
5. 単項+ 単項-
6. ()

優先順位は生成文法で表現可能で、優先順位の異なる演算子は別の非終端記号にマップされるのでした。exprやmulと同様に文法を考えてみると、比較演算子を加えた新しい文法は以下のようになります。

expr       = equality
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | "(" expr ")"

equalityは==と!=を、relationalは<、<=、>、>=を表しています。これらの非終端記号は、左結合の演算子をパースするパターンを使ってそのまま関数にマップすることができます。

なお、上記の文法では、式全体がequalityであるということを表すために、exprとequalityを分離しました。exprの右辺にequalityの右辺を直接書いてもよかったのですが、おそらく上記の文法の方が見やすいと思います。

アセンブリコードの生成

x86-64では、比較はcmp命令を使って行います。スタックから2つの整数をポップして比較を行い、同一の場合に1、そうでなければ0をRAXにセットするコードは次のようになります。

pop rdi
pop rax
cmp rax, rdi
sete al
movzb rax, al

このコードは、短いアセンブリながらやや盛りだくさんなので、ステップバイステップでコードを見ていきましょう。

最初の2行では値をスタックからポップしています。3行目では、それらのポップしてきた値を比較（compare）しています。比較結果はどこにいくのでしょうか？ x86-64では、比較命令の結果は特別な「フラグレジスタ」というものにセットされます。フラグレジスタは整数演算や比較演算命令が実行されるたびに更新されるレジスタで、結果が0かどうかといったビットや、桁あふれが発生したかどうかというビット、結果が0未満かどうかといったビットなどを持っています。

フラグレジスタは通常の整数レジスタではないので、RAXに比較結果をセットしたい場合、フラグレジスタの特定のビットをRAXにコピーしてくる必要があります。それを行うのがsete命令です。sete命令は、直前のcmp命令で調べた2つのレジスタの値が同じだった場合に、指定されたレジスタ（ここではAL）に1をセットします。それ以外の場合は0をセットします。

ALというのは本書のここまでに登場していない新しいレジスタ名ですが、実はALはRAXの下位8ビットを指す別名レジスタにすぎません。従ってseteがALに値をセットすると、自動的にRAXも更新されることになります。ただし、RAXをAL経由で更新するときに上位56ビットは元の値のままになるので、RAX全体を0か1にセットしたい場合、上位56ビットはゼロクリアする必要があります。それを行うのがmovzb命令です。sete命令が直接RAXに書き込めればよいのですが、seteは8ビットレジスタしか引数に取れない仕様になっているので、比較命令では、このように2つの命令を使ってRAXに値をセットすることになります。

seteの代わりに別の命令を使うことで、その他の比較演算子を実装することができます。<ではsetl、<=ではsetle、!=ではsetneを使うようにしてください。

>と>=はコードジェネレータでサポートする必要はありません。パーサで両辺を入れ替えて<や<=として読み換えるようにしてください。

分割コンパイルとリンク

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

• 9cc.h: ヘッダファイル
• main.c: main関数
• parse.c: パーサ
• codegen.c: コードジェネレータ
• container.c: ベクタ、マップ、およびそのテストコード

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

この章では分割コンパイルの概念とその意義について説明を行い、その後に具体的な手順について説明をします。

分割コンパイルとは

分割コンパイルとその必要性

分割コンパイルとは、1つのプログラムを複数のソースファイルに分割して書いて、別々にコンパイルすることです。分割コンパイルでは、コンパイラはプログラム全体ではなく、プログラムの断片を読んで、それに対応した断片を出力することになります。単体では実行不可能なプログラムの断片の入ったファイルのことを「オブジェクトファイル」（拡張子は.o）といいます。分割コンパイルでは、最後にオブジェクトファイルをつなぎ合わせて1つのファイルを作ることになります。オブジェクトファイルをまとめて1つの実行ファイルにするプログラムのことを「リンカ」といいます。

なぜ分割コンパイルをする必要があるのかを理解しておきましょう。実は、技術的にはソースを分割しなければならない必然性というものはありません。コンパイラにソースコードを一度に全部渡せば、コンパイラはリンカの助けなしに完全な実行ファイルを出力することが論理的には可能です。

ただしそのようなやり方の場合、コンパイラは、プログラムが使っているコードを本当にすべて知っている必要があります。例えばprintfなどの標準ライブラリの関数は、普通は標準ライブラリの作者がCで書いた関数なわけですが、リンクのステップを省くためには、そういった関数のソースコードも毎回コンパイラの入力に与える必要が出てきてしまいます。何度も同じ関数をコンパイルするのは、多くの場合、単なる時間の無駄です。したがって標準ライブラリは普通はコンパイル済みのオブジェクトファイル形式で配布されていて、手元で毎回コンパイルし直さなくてよくなっています。つまり、1つのソースコードからなるプログラムでも、標準ライブラリを使っている限り、実は分割コンパイルを利用しているのです。

分割コンパイルを行わないと、1行変更しただけでもコード全体をコンパイルし直すことになります。数万行の長さのコードではコンパイルは数十秒はかかります。大きなプロジェクトではソースコードは1000万行以上あったりするので、それを1つの単位としてコンパイルすると1日では終わらないでしょう。メモリも100GiBといった単位で必要になります。そういったビルド手順は非現実的です。

また、単純に、1つのファイルにすべての関数や変数をまとめて書くと人間にとって管理が難しいという問題もあります。

上記のような理由で分割コンパイルが必要とされているのです。

ヘッダファイルの必要性とその内容

分割コンパイルでは、コンパイラはプログラムの一部分のコードだけを見ることになりますが、コンパイラはプログラムのどのような小さな断片でもコンパイルできるというわけではありません。例えば次のコードを考えてみてください。

void print_bar(struct Foo *obj) {
  printf("%d\n", obj->bar);
}

上記のコードでは、構造体Fooの型を知っていればこのコードに対応するアセンブリを出力することができますが、そうでなければこの関数をコンパイルすることはできません。

分割コンパイルする場合、個々のCファイルをコンパイルできるだけの十分な情報を、それぞれのファイルにいれておく必要があります。とはいっても、別のファイルに書かれているコードを全部書いてしまうとそもそも分割コンパイルではなくなってしまうので、ある程度情報は取捨選択する必要があります。

一つの例として、別のCファイルに入っている関数を呼び出すコードを出力するためにどのような情報をいれる必要があるのかを考えてみましょう。コンパイラは以下の情報を必要とします。

• そもそもある識別子が関数の名前であるという情報が必要です。
• コンパイラが出力する関数呼び出しのコードは、引数をある決められた順番でレジスタにセットして、call命令を使って別の関数の先頭にジャンプします。引数の型によっては整数を浮動小数点数に変換するといったことも行います。引数の型や個数が間違っている場合はエラーメッセージを表示する必要もあります。したがって関数の引数の個数や個々の引数の型が必要です。
• 呼び出した関数の先で何が行われていても、呼び出し元にとってはそのうち単にリターンしてくるだけなので、呼び出し先の関数のコードは、呼び出し元の関数をコンパイルするときには必要ありません。
• callで飛ぶ先のアドレスは分割コンパイル時にはわかりませんが、アセンブラはとりあえずアドレス0にジャンプするようなcall命令を出力しておいて、オブジェクトファイル内に「オブジェクトファイルのXバイト目をYという名前の関数のアドレスで修正する」という情報を残しておくことができます。リンカはその情報を見て、実行ファイルのレイアウトを決めた後、プログラム断片をバイナリパッチングして、ジャンプ先のアドレスを修正します（この操作を「リロケートする」といいます）。したがって、分割コンパイルするためには関数の名前は必要ですが、関数のアドレスは不要です。

上記の要件をまとめてみると、関数本体の{ ... }を省いたものさえあれば、その関数を呼び出すのに十分な情報はあるということになります。そのような関数本体を省いたものを関数の「宣言」（declaration）といいます。宣言は型と名前をコンパイラに教えているだけで、関数のコードは含まれていません。例えば、以下はstrncmpの宣言です。

int strncmp(const char *s1, const char *s2, size_t n);

コンパイラは上記の1行を見ることにより、strncmpの存在とその型を知ることができるというわけです。宣言に対して関数のコードを含むものを「定義」（definition）といいます。

関数宣言には、宣言を表すキーワードexternをつけて、

extern int strncmp(const char *s1, const char *s2, size_t n);

のように書いても構いませんが、関数の場合、関数本体が省略されていることで宣言と定義を区別できるので、externはつけなくてもかまいません。

なお、引数は型さえわかればよいので、宣言では名前は省略可能ですが、人間にとってわかりやすくするために宣言でも名前を書いておくことが一般的です。

別の例として構造体の型を考えてみましょう。同じ構造体を使っているCファイルが2つ以上ある場合、それぞれのCファイルに同じ構造体の宣言を書いておく必要があります。1つのCファイルでしか使われていない構造体であれば、特に他のCファイルはその存在について知る必要はありません。

Cでは、このように他のCファイルをコンパイルするときに必要になる宣言をまとめて、ヘッダファイル（拡張子は.h）というものに書くことになっています。foo.hに宣言を書いておいて、それを必要とする別のCファイルに#include "foo.h"のように書いておくと、#includeの行がfoo.hファイルの内容に置き換えられることになります。

typedefなどもコンパイラに型情報を教えるために使われます。こういったものも、複数のCファイルで使われている場合、ヘッダファイルに書いておく必要があります。

コンパイラは宣言を読み込んだときには特に何のアセンブリも出力しません。宣言というものは、別のファイルに含まれている関数や変数を使うために必要な情報であって、それ自体は関数や変数を定義するものではないからです。

ここまでの分割コンパイルの話を踏まえると、「printfを使うときは#include <stdio.h>をおまじないとして書いておきます」といった話が、実際には何をしているのかがわかると思います。C標準ライブラリはリンカに暗黙のうちに渡されるので、リンカはprintfの関数呼び出しが含まれたオブジェクトファイルをリンクして実行ファイルを作成することができます。一方で、コンパイラはprintfについてはデフォルトでは特に知識を持っていません。printfは組み込み関数ではなく、標準ライブラリのヘッダファイルが自動的に読み込まれるといった仕様も存在しないので、起動した直後はコンパイラはprintfについては何も知らない状態です。この状態から、C標準ライブラリについてくるヘッダファイルをインクルードすることで、printfの存在とその型をコンパイラは知ることができ、printfの関数呼び出しをコンパイルできるようになるのです。

リンクエラー

オブジェクトファイルを最後にまとめてリンカに渡すときには、全体としてプログラムを構成するのに足る情報が過不足なく含まれていなければいけません。

もしプログラムに関数fooの宣言だけが含まれていて定義がない場合、個々のCファイルは、fooを呼び出すコードも含めて普通にコンパイルすることができます。しかし、最後にリンカが完全なプログラムを作成しようとしたとき、fooのアドレスで修正するべき箇所が、fooがないために修正しようがないので、エラーになってしまいます。

リンク時のエラーのことをリンクエラーといいます。

複数のオブジェクトファイルに同じ関数や変数が含まれている場合もリンクエラーになります。リンカとしては、重複がある場合どちらを選べばよいかよくわからないからです。このような重複エラーは、ヘッダファイルに間違えて定義を書いてしまったときによく発生します。ヘッダファイルは複数のCファイルにインクルードされるので、ヘッダファイルに定義がある場合、複数のCファイルに重複して定義が書かれているのと同じ状態になるからです。このようなエラーを解消するためには、ヘッダファイルに宣言だけを書くようにして、実体はどれか1つのCファイルに移してください。

グローバル変数の宣言と定義

我々のコンパイラにはまだグローバル変数がないので、グローバル変数に対応するアセンブリの例というのはまだ出ていませんが、グローバル変数というものはアセンブリレベルでは関数とほとんど同じです。したがって関数と同様に、グローバル変数にも定義と宣言の区別があります。変数の本体が複数のCファイルに重複して存在している場合、通常それはリンクエラーになります。

グローバル変数はデフォルトでは実行禁止メモリ領域に割り付けられるので、そこにジャンプするとプログラムがセグメンテーションフォールトでクラッシュすることになりますが、本質的にはそれ以外、データとコードの違いは存在しません。実行時に関数をデータとしてグローバル変数のように読むこともできますし、実行を許可するようにメモリの属性を変更してデータにジャンプすれば、データをコードとして実行することもできます。

関数とグローバル変数がどちらも本質的にはメモリ上に存在するデータにすぎないことを、実際のコードで確認してみましょう。以下のコードでは、mainという識別子がグローバル変数として定義されています。mainの内容はx86-64の機械語です。

char main[] = "\x48\xc7\xc0\x2a\x00\x00\x00\xc3";

上記のCコードをfoo.cというファイルに保存してコンパイルして、objdumpを使って内容を確認してみましょう。objdumpのデフォルトではグローバル変数の内容は16進で表示されるだけですが、-Dオプションを渡すと、データをコードとして無理やり逆アセンブルすることができます。

$ cc -c foo.c
$ objdump -D -M intel foo.o
Disassembly of section .data:

0000000000000000 <main>:
   0:   48 c7 c0 2a 00 00 00    mov    rax,0x2a
   7:   c3                      ret

データが実行禁止領域にマップされるというデフォルトの動作は、コンパイル時に-Wl,--omagicというオプションを渡すことで変更できます。このオプションを使って実行ファイルを生成してみましょう。

$ cc -static -Wl,--omagic -o foo foo.o

関数も変数もアセンブリにおいてはただのラベルになっていて、同じ名前空間に属しているので、リンカは複数のオブジェクトファイルをまとめるときに、どれが関数でどれがデータなのかは気にしません。したがってmainがCレベルでデータとして定義されていても、mainが関数であるのと同じようにリンクは成功します。

生成されたファイルを実行してみましょう。

$ ./foo
$ echo $?
42

上記のように、42という値が正しく返ってきています。mainというグローバル変数の内容がコードとして実行されたというわけです。

Cの文法では、グローバル変数の場合、externをつけると宣言になります。以下はint型のグローバル変数fooの宣言です。

extern int foo;

fooを含んだプログラムを書く場合、上記の行をヘッダファイルに書いておくことになります。そして、どれか1つのCファイルでfooを定義することになります。以下はfooの定義です。

int foo;

なお、Cにおいては初期化式の与えられていないグローバル変数は0で初期化されるということになっているので、そのような変数は、0や{0, 0, ...}、"\0\0\0\0..."などで初期化されているのと意味的に同じです。

int foo = 3のように初期化式を書く場合は、定義だけに初期化式を書いてください。宣言は変数の型だけをコンパイラに教えるためのものなので、具体的な初期化式は必要ありません。コンパイラはグローバル変数の宣言を見たときに特にアセンブリを出力するわけではないので、その中身がどのように初期化されているかというのはその場では必要ないのです。

初期化式が省略されている場合、グローバル変数の宣言と定義はexternの有無だけなので見た目が似てしまいますが、宣言と定義は異なるものです。ここでそれをきっちり把握しておいてください。

char main[] = "\0xf0\0x0f\0xc7\0xc8";

ステップ8: ファイル分割とMakefileの変更

ファイルの分割

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

Makefileの変更

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

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

9cc: $(OBJS)
        $(CC) -o 9cc $(OBJS) $(LDFLAGS)

$(OBJS): 9cc.h

test: 9cc
        ./test.sh

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

.PHONY: test clean

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

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

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

make fooと実行すると、makeはfooというファイルを作成しようとします。指定されたターゲットのファイルがすでに存在する場合、依存ファイルよりもターゲットファイルのほうが古い場合に限り、makeはターゲットのルールを再実行します。これにより、ソースコードが変更されたときにだけバイナリを再生成するといった動作が実現されています。

.PHONYというのはダミーのターゲットを表すための特別な名前です。make testやmake cleanは、testやcleanといったファイルを作成するために実行するわけではないのですが、普通はmakeにはそのことがわからないので、testやcleanといった名前のファイルが偶然存在している場合、make testやmake cleanは何も行わなくなってしまいます。こういったダミーのターゲットは、.PHONYで指定することにより、本当にそういう名前のファイルを作りたいわけではなく、指定されたターゲットのファイルが存在しているかどうかに関わらずルールのコマンドを実行するべきということをmakeに伝えることができます。

CFLAGSやSRCS、OBJSは変数です。

CFLAGSはmakeの組み込みルールによって認識される変数で、Cコンパイラに渡すコマンドラインオプションを書いておきます。ここでは以下のフラグを渡しています。

• -std=c11: Cの最新規格であるC11で書かれたソースコードということを伝える
• -g: デバグ情報を出力する
• -static: スタティックリンクする

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

OJBSの右辺では変数の置換ルールを使っていて、それによりSRCの中の.cを.oに置き換えた値を生成しています。SRCSはmain.c parse.c codegen.c container.cなので、OBJSはmain.o parse.o codegen.o container.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ファイルが再コンパイルされることになります。

関数とローカル変数

この章では、関数とローカル変数を実装します。また、簡単な制御構造も実装します。この章が終わると次のようなコードをコンパイルできるようになります。

// mからnまでを足す
sum(m, n) {
  acc = 0;
  for (i = m; i <= n; i = i + 1)
    acc = acc + i;
  return acc;
}

main() {
  return sum(1, 10); // 55を返す
}

上記のコードはCとはまだギャップがありますが、それでもかなりCに近づいてきたと言えるのではないでしょうか。

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

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

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

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

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

スタック上の変数領域

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

ただし、関数のローカル変数は、関数呼び出しごとに別々に存在しなければいけません。実装の都合だけを考えると、例えば「関数fのローカル変数aは0x6080番地に置く」というようにアドレスを決め打ちにしてしまうのが簡単そうですが、それだとfを再帰的に呼び出した場合にうまく動きません。ローカル変数を関数呼び出しごとに別々に持たせるために、Cではローカル変数はスタックに置くことになっています。

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

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

RSPを何バイト分変更するかとか、そのようにして確保した領域に変数をどういった順番で置くかといったことは、他の関数から見えるものではないので、コンパイラの実装の都合で適当に決めて構いません。

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

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

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

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

ベースポインタを使った関数呼び出しにおけるスタックの状態を示したのが以下の図です。ローカル変数xとyを持った関数gがfを呼び出すものとしましょう。gの実行中、スタックは次のようになっています。

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

push rbp
mov rbp, rsp
sub rsp, 16

このようなコンパイラが関数の先頭に出力する定型の命令のことを「プロローグ」（prologue）といいます。なお、16というのは、実際には関数ごとに変数の個数やサイズに合わせた値にする必要があります。

RSPがリターンアドレスを指している状態から上のコードを実行すると、期待している通りの関数フレームができあがることを確認してみましょう。1命令ごとのスタックの状態を以下に示します。

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

mov rsp, rbp
pop rbp
ret

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

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

このように、エピローグを実行することにより、呼び出し元の関数gのスタックの状態がリストアされます。call命令は、call命令自体の次の命令のアドレスをスタックに積みます。エピローグのretはそのアドレスをポップしてそこにジャンプするので、callの次の命令から関数gの実行が再開されることになります。こういった動作は、我々が知っている関数の動作と完全に一致しています。

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

トークナイザの変更

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

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

enum {
  TK_RESERVED, // 記号
  TK_IDENT,    // 識別子
  TK_NUM,      // 整数トークン
  TK_EOF,      // 入力の終わりを表すトークン
} TokenKind;

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

if ('a' <= *p && *p <= 'z') {
  cur = new_token(TK_IDENT, cur, p++);
  cur->len = 1;
  continue;
}

パーサの変更

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

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

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

さらに、セミコロン区切りで複数の文（ステートメント）を書けるようにしたいので、結果として新しい文法は以下のようになります。

program    = stmt*
stmt       = expr ";"
expr       = assign
assign     = equality ("=" assign)?
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | ident | "(" expr ")"

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

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

Node *code[100];

Node *assign() {
  Node *node = equality();
  if (consume("="))
    node = new_node(ND_ASSIGN, node, assign());
  return node;
}

Node *expr() {
  return assign();
}

Node *stmt() {
  Node *node = expr();
  expect(";");
  return node;
}

void program() {
  int i = 0;
  while (!at_eof())
    code[i++] = stmt();
  code[i] = NULL;
}

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

typedef enum {
  ND_ADD,    // +
  ND_SUB,    // -
  ND_MUL,    // *
  ND_DIV,    // /
  ND_ASSIGN, // =
  ND_LVAR,   // ローカル変数
  ND_NUM,    // 整数
} NodeKind;

typedef struct Node Node;

// 抽象構文木のノード
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
  int offset;    // kindがND_LVARの場合のみ使う
};

offsetというのは、ローカル変数のベースポインタからのオフセットを表すメンバーです。今のところ、変数aはRBP-8、bはRBP-16⋯⋯というように、ローカル変数は名前で決まる固定の位置にあるので、オフセットは構文解析の段階で決めることができます。以下に識別子を読み込んでND_LVAR型のノードを返すコードを示します。

Node *primary() {
  ...

  Token *tok = consume_ident();
  if (tok) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = ND_LVAR;
    node->offset = (tok->str[0] - 'a' + 1) * 8;
    return node;
  }

  ...

左辺値と右辺値

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

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

その問いには単純な答えがあります。Cにおいて代入式の左辺にくることができるのは、基本的にメモリのアドレスを指定する式だけです。

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

一方で、a+1のような式の結果は、変数ではないので、メモリのアドレスを指定する式としては使えないということになっています。こういったテンポラリな値は、実際にレジスタだけに存在していてメモリ上にないかもしれないですし、メモリ上に存在していたとしても、既知の変数からの固定のオフセットでアクセスすることは普通はできません。こうした理由から、例えば&(a+1)のように書いても、a+1の結果のアドレスを取得することは許されておらず、コンパイルエラーになります。こういった式は代入文の左辺に書くことはできません。

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

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

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

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

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つの命令と同じです。

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

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

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

void gen_lval(Node *node) {
  if (node->kind != ND_LVAR)
    error("代入の左辺値が変数ではありません");

  printf("  mov rax, rbp\n");
  printf("  sub rax, %d\n", node->offset);
  printf("  push rax\n");
}

void gen(Node *node) {
  switch (node->kind) {
  case ND_NUM:
    printf("  push %d\n", node->val);
    return;
  case ND_LVAR:
    gen_lval(node);
    printf("  pop rax\n");
    printf("  mov rax, [rax]\n");
    printf("  push rax\n");
    return;
  case ND_ASSIGN:
    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->kind) {
  case '+':
    printf("  add rax, rdi\n");
    break;
  case '-':
    printf("  sub rax, rdi\n");
    break;
  case '*':
    printf("  imul rax, rdi\n");
    break;
  case '/':
    printf("  cqo\n");
    printf("  idiv rdi\n");
  }

  printf("  push rax\n");
}

メイン関数の変更

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

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

  // トークナイズしてパースする
  // 結果はcodeに保存される
  user_input = argv[1];
  tokenize();
  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;
}

ステップ10：複数文字のローカル変数

以前の章では変数名を1文字に決め打ちにして、aからzまでの26個のローカル変数が常に存在しているものとして扱うことにしていました。この節では、1文字より長い名前を持つ識別子をサポートして、次のようなコードをコンパイルできるようにします。

foo = 1;
bar = 2 + 3;
return foo + bar; // 6を返す

変数は定義なしに使えるものとします。したがってパーサでは、識別子一つ一つについて今までに見たことがあるかどうかを判定して、新たなものであれば自動的にスタック領域に変数を割り付ける必要があります。

まずはトークナイザを変更して、複数の文字からなる識別子をTK_IDENT型のトークンとして読み込むようにしてください。

変数は連結リストで表すことにします。LVarという構造体で一つの変数を表すことにして、先頭の要素をlocalsというポインタで持つことにしましょう。コードで表すと次のようになります。

typedef struct LVar LVar;

// ローカル変数の型
struct {
  LVar *next; // 次の変数かNULL
  char *name; // 変数の名前
  int len;    // 名前の長さ
  int offset; // RBPからのオフセット
} LVar;

// ローカル変数
LVar *locals;

パーサにおいては、TK_IDENT型のトークンが出現した場合、その識別子が今までに出現したことがあるかどうかを確認します。localsをたどって変数名を見ていくことで、既存の変数かどうかはわかります。変数が以前に出現していた場合、その変数のoffsetをそのまま使います。新たな変数の場合、新しいLVarを作って、新たなオフセットをセットして、そのオフセットを使います。

変数を名前で探す関数を以下に示します。

// 変数を名前で検索する。見つからなかった場合はNULLを返す。
LVar *find_lvar(Token *tok) {
  for (LVar *var = locals; var; var = var->next)
    if (var->len == tok->len && !memcmp(tok->str, var->name, var->len))
      return var;
  return NULL;
}

パーサでは次のようなコードを追加すればよいはずです。

Token *tok = consume_ident();
if (tok) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = ND_LVAR;

  LVar *lvar = find_lvar(tok);
  if (lvar) {
    node->offset = lvar->offset;
  } else {
    lvar = calloc(1, sizeof(LVar));
    lvar->next = locals;
    lvar->name = tok->str;
    lvar->len = tok->len;
    lvar->offset = locals->offset + 8;
    node->offset = lvar->offset;
    locals = lvar;
  }
  return node;
}

コラム: 機械語命令の出現頻度

9ccが出力したアセンブリを見てみると、movやpushといったデータ移動命令が多くて、addやmulのような「本当の計算」を行う命令が比較的少ないことに気がつくと思います。その一つの理由は、9ccが最適化を行なっておらず、無駄なデータ移動命令を出力しているからなのですが、実は最適化コンパイラでも一番多く出力されるのはデータ移動命令です。筆者の環境で/binに入っているすべての実行ファイルを逆アセンブルして、命令数をカウントした結果のグラフを以下に示します。

ご覧のようにmov命令だけで全命令の実に3割を占めています。コンピュータというものはデータ処理機械ですが、データ処理で最も頻繁に行われるのはデータの移動なのです。「データを適切な場所に移動させる」ということがデータ処理の本質の一つだと考えてみれば、このmov命令の多さは順当な結果のような気もしますが、意外に思った読者も多いのではないでしょうか。

ステップ11：return文

この章ではreturn文を追加して、次のようなコードをコンパイルできるようにします。

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

return文はプログラムの途中に書いても構わないということにします。通常のCと同様に、プログラムの実行は最初のreturnで打ち切られて関数からリターンすることになります。例えば以下のプログラムは最初のreturnの値、すなわち5を返します。

return 5;
return 8;

この機能を実装するために、まずはreturnを追加した文法がどうなるのかを考えてみましょう。いままではステートメントはただの式ということになっていましたが、新たな文法ではreturn <式>;というものを許すことになります。したがって新たな文法は次のようになります。

program = stmt*
stmt    = expr ";"
        | "return" expr ";"
...

これを実装するためには、トークナイザ、パーサ、コードジェネレータのすべてに少しづつ手を加える必要があります。

まずはトークナイザでreturnというトークンを認識できるようにして、それをTK_RETURNという型のトークンで表すようにしましょう。returnやwhile、intのように、文法上特別な意味を持つトークン（キーワードといいます）は限られた個数しか存在しないので、このようにトークンごとに別の型を持たせるようにしたほうが簡単です。

次のトークンがreturnかどうかは、トークナイザの残りの入力文字列がreturnから始まっているかどうかだけを調べれば良さそうですが、それだとreturnxのようなトークンが、誤ってreturnとxとしてトークナイズされてしまうことになります。したがってここでは、入力の先頭がreturnであることに加えて、その次の文字がトークンを構成する文字ではないことを確認する必要があります。

与えられた文字がトークンを構成する文字、すなわち英数字かアンダースコアかどうかを判定する関数を下に示します。

int is_alnum(char c) {
  return ('a' <= c && c <= 'z') ||
         ('A' <= c && c <= 'Z') ||
         ('0' <= c && c <= '9') ||
         (c == '_');
}

この関数を使って、tokenizeに次のコードを加えると、returnをTK_RETURNとしてトークナイズできるようになります。

if (strncmp(p, "return", 6) == 0 && !is_alnum(p[6])) {
  tokens[i].ty = TK_RETURN;
  tokens[i].str = p;
  i++;
  p += 6;
  continue;
}

次にパーサに手を加えて、TK_RETURNを含むトークン列をパースできるようにしましょう。そのためには、まずreturn文を表すノードの型ND_RETURNを追加します。次に、ステートメントを読み込む関数を変更して、return文を構文解析できるようにします。例によって、文法をそのまま関数呼び出しにマップすることで構文解析ができます。新しいstmt関数を以下に示します。

Node *stmt() {
  Node *node;

  if (consume(TK_RETURN)) {
    node = calloc(1, sizeof(Node));
    node->kind = ND_RETURN;
    node->lhs = expr();
  } else {
    node = expr();
  }

  if (!consume(';'))
    error_at(tokens[pos].str, "';'ではないトークンです");
  return node;
}

ND_RETURN型のノードはここでしか生成しないので、ここでは新たに関数を作るのではなく、その場でmallocして値をセットすることにしました。

最後にコードジェネレータを変更して、ND_RETURN型のノードに対して適切なアセンブリコードを出力するようにします。新しいgen関数の一部分を以下に示します。

void gen(Node *node) {
  if (node->kind == ND_RETURN) {
    gen(node->lhs);
    printf("  pop rax\n");
    printf("  mov rsp, rbp\n");
    printf("  pop rbp\n");
    printf("  ret\n");
    return;
  }
  ...

上記のコードのgen(node->lhs)という関数呼び出しで、returnの返り値になっている式のコードが出力されます。そのコードはスタックトップに1つの値を残すはずです。gen(node->lhs)の後に続くアセンブリでは、その値をスタックからポップしてRAXにセットし、関数からリターンしています。

前章までに実装した機能では、関数の最後に必ず1つのret命令を出力していました。この章で説明した方法でreturn文を実装すると、return文ごとにさらに余分なret命令が出力されることになります。それらの命令はまとめることも可能ですが、ここでは簡単に実装するために、ret命令を複数出力してもかまわないということにしました。こういう細かいところは今の時点では気にしても仕方がないので、実装のシンプルさを優先することが大切です。難しいコードを書けるというのは役立つスキルですが、そもそもコードを難しくしすぎないというのは、時にはさらに役立つスキルなのです。

1973年の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関数は、単に無理やり少ない引数で読んでも正しく動作します。関数の引数チェックがこの時点では存在しなかったことを思い出してください。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と見なされてiがデクリメントされるという意図しない動作になってしまう問題がありました。
• 整数型はcharとintだけで、shortやlongは存在しませんでした。「関数ポインタの配列」といった型を宣言する構文は存在せず、複雑な型を記述することができませんでした。

上記のほかにも70年代初期のCにはいろいろな機能が欠けていました。とはいえ、このCコンパイラは、上のソースコードからわかるようにCで書かれていました。構造体すらない時代にすでにCはセルフホストしていたのです。

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

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

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

ステップ12: 制御構文を足す

これ以降の章は執筆中です。ここまでの章は丁寧に書いたつもりですが、ここからの章は正直まだ公開するレベルには達していないと思います。ただし、ここまで読み進めてきた人ならば自分で必要なことを補完して読めないこともないでしょうし、どのような手順で進めるのがよいのか道標が欲しい人もいるでしょうから、そういう意味で公開しておきます。

この節ではif、if ... else、while、forといった制御構造を言語に追加します。これらの制御構造は一見複雑そうに見えますが、アセンブリに素直にそのままコンパイルする場合、実装は比較的簡単です。

アセンブリにはCの制御構造に対応するものが存在しないので、Cの制御構造は、アセンブリでは分岐命令とラベルで表現されます。これはある意味、制御構造をgotoを使って書き直すのと同じです。人間が制御構造を手でgoto文に書き直せるように、制御構造は、パターンにしたがってコード生成を行うだけで無理なく実装することができます。

制御構文には他にもdo ... while、goto、continue、breakなど様々な構文が存在しますが、それらはこの時点ではまだ実装する必要はありません。

if、while、forを加えた新たな文法を以下に示します。

program = stmt*
stmt    = expr ";"
        | "if" "(" expr ")" stmt ("else" stmt)?
        | "while" "(" expr ")" stmt
        | "for" "(" expr? ";" expr? ";" expr? ")" stmt
        | ...
...

expr? ";"を読み取る時には、1トークン先読みして、次のトークンが;ならばexprは存在しないということにして、そうでなければexprを読む、というようにすればよいです。

if (A) Bは次のようなアセンブリにコンパイルします。

  Aをコンパイルしたコード // スタックトップに結果が入っているはず
  pop rax
  cmp rax, 0
  je  .LendXXX
  Bをコンパイルしたコード
.LendXXX:

つまりif (A) Bは、

  if (A == 0)
    goto end;
  B;
end:

と同じように展開されるというわけです。XXXは通し番号などにして、全てのラベルがユニークになるようにしてください。

if (A) B else Cは次のようなアセンブリにコンパイルします。

  Aをコンパイルしたコード // スタックトップに結果が入っているはず
  pop rax
  cmp rax, 0
  je  .LelseXXX
  Bをコンパイルしたコード
  jmp .LendXXX
.LelseXXX
  Cをコンパイルしたコード
.LendXXX

つまりif (A) B else Cは次のように展開されます。

  if (A == 0)
    goto els;
  B;
  goto end;
els:
  C;
end:

if文を読むときは、1トークン先読みをしてelseがあるかどうかをチェックして、elseがあるときはif ... else、ないときはelseのないifとしてコンパイルします。

while (A) Bは次のようにコンパイルします。

.LbeginXXX:
  Aをコンパイルしたコード
  pop rax
  cmp rax, 0
  je  .LendXXX
  Bをコンパイルしたコード
  jmp .LbeginXXX
.LendXXX:

つまりwhile (A) Bは次のようなコードと同じように展開されます。

begin:
  if (A == 0)
    goto end;
  B;
  goto begin;
end:

for (A; B; C) Dは次のようにコンパイルします。

  Aをコンパイルしたコード
.LbeginXXX:
  Bをコンパイルしたコード
  pop rax
  cmp rax, 0
  je  .LendXXX
  Dをコンパイルしたコード
  Cをコンパイルしたコード
  jmp .LbeginXXX
.LendXXX:

for (A; B; C) Dに対応するCコードを以下に示します。

  A;
begin:
  if (B == 0)
    goto end;
  D;
  C;
  goto begin;
end:

なお、.Lから始まるラベルはアセンブラによって特別に認識される名前で、自動的にファイルスコープになります。ファイルスコープのラベルは、同じファイルの中から参照することはできますが、別のファイルから参照することはできません。したがって、ifやforのためにコンパイラが作り出したラベルを.Lから始めるようにしておくと、他のファイルに含まれているラベルと衝突する心配がいらなくなります。

ccで小さいループをコンパイルしてそのアセンブリを参考にして作ってください。

ステップ13: ブロック

このステップでは{ ... }の間に複数のステートメントを書くことのできる「ブロック」（block）をサポートします。ブロックは正式には「複文」（compound statement）と呼ばれますが、長い単語なので、往々にして単にブロックと呼ばれています。

ブロックは、複数のステートメントをまとめて1つのステートメントにする効果があります。上記のステップで実装したifやwhileは、条件式が成立したときに実行されるステートメントを1つしか許していませんでしたが、このステップでブロックを実装することにより、Cと同じように、そこに{}でくくった複数の文を書けるようになります。

関数本体も実はブロックです。文法上、関数本体は必ずブロックでなければならないことになっています。関数の定義の{ ... }は、実はifやwhileの後に書く{ ... }と構文的には同じなのです。

ブロックを追加した文法を以下に示します。

program = stmt*
stmt    = expr ";"
        | "{" stmt* "}"
        | ...
...

この文法では、stmtが"{"で始まっている場合、"}"が出現するまで0個以上のstmtがでてきてよいことになります。stmt* "}"をパースするためには、"}"が出現するまでwhile文で繰り返しstmtを呼んで、その結果をベクタとして返すようにしてください。

ブロックを実装するためには、ブロックを表すノードの型ND_BLOCKを追加してください。ノードを表す構造体Nodeには、ブロックに含まれる式を持つベクタを追加する必要があります。コードジェネレータでは、ノードの型がND_BLOCKだった場合に、そのノードに含まれるステートメントのコードを順番に生成するようにしてください。なお、1つ1つのステートメントは1つの値をスタックに残すので、それを毎回ポップするのを忘れないようにしましょう。

ステップ14: 関数の呼び出しに対応する

このステップではfoo()のような引数なしの関数呼び出しを認識できるようにして、これをcall fooにコンパイルするということを目標にします。

関数呼び出しを加えた新たな文法を下に示します。

...
primary = num
        | ident ("(" ")")?
        | "(" expr ")"

identを読んだあと1つトークンを先読みしてみることで、そのidentが変数名なのか関数名なのかを見分けることができます。

テストではint foo() { printf("OK\n"); }のような内容のCファイルを用意しておいて、それをcc -cでオブジェクトファイルにコンパイルして、自分のコンパイラの出力とリンクします。そうすると全体としてきちんとリンクできて、自分の呼び出したい関数がきちんと呼ばれていることも確認できるはずです。

それが動いたら、次はfoo(3, 4)のような関数呼び出しを書けるようにしてください。引数の個数や型のチェックはいりません。単に引数を順番に評価すると、スタック上に関数に渡すべき引数ができあがるので、それをx86-64のABIで規定されている順番でレジスタにコピーして、関数をcallします。6つより多い引数はサポートしなくてかまいません。

テストでは上と同じように、int foo(int x, int y) { printf("%d\n", x + y); }のような関数を適当に用意しておいて、それをリンクすれば動作確認できるはずです。

x86-64の関数呼び出しのABIは（上のようなやり方をしている限りは）簡単ですが、注意点が一つあります。関数呼び出しをする前にRSPが16の倍数になっていなければいけません。pushやpopはRSPを8バイト単位で変更するので、call命令を発行するときに必ずしもRSPが16の倍数になっているとは限りません。この約束が守られていない場合、RSPが16の倍数になっていることを前提にしている関数が、半分の確率で落ちる謎の現象に悩まされることにmなります。関数を呼ぶ前にRSPを調整するようにして、RSPを16の倍数になるように調整するようにしましょう。

ステップ15: 関数の定義に対応する

ここまでが終わったら次は関数定義をできるようにします。とはいえCの関数定義は構文解析が面倒なのでいきなり全部を実装したりはしません。現在のところ我々の言語にはint型しか存在しないので、int foo(int x, int y) { ... }という構文ではなく 型名を省略したfoo(x, y) { ... }という構文を実装します。

呼び出された側ではxやyといった名前で引数にアクセスできる必要があるわけですが、レジスタで渡された値にそのまま名前でアクセスすることは現状できません。ではどうするかというと、xやyといったローカル変数が存在するものとしてコンパイルして、関数のプロローグの中で、レジスタの値をそのローカル変数のためのスタック上の領域に書き出してください。そうすれば、その後は特に引数とローカル変数を区別することなく扱えるはずです。

今までは暗黙のうちに全体がmain() { ... }で囲まれているのと同じ動作になっていましたが、それは廃止して、全部のコードを何らかの関数の中に書くようにします。そうするとトップレベルをパースしているときは、まずトークンを読むとそれは必ず関数名のはずで、その後に続くのは引数リストのはずで、そのあとは関数本体が続いているはず、となるので、簡単に読めます。

このステップが終わるとフィボナッチ数列を再帰で計算しつつ表示したりできるようになるのでグッと面白くなるはずです。

バイナリレベルのインターフェイス

C言語の仕様はソースコードレベルの仕様を規定しています。例えば言語仕様では、どのような書き方をすると関数を定義できるのかとか、どのファイルをインクルードすればどの関数が宣言されるのか、といったことが決められています。一方で、標準に準拠するように書いたソースコードがどのような機械語に変換されるのかといったことは、言語仕様では規定されていません。C言語の標準は特定の命令セットを念頭に置いて決められているわけではないので、これは当然のことといえるでしょう。

したがって、機械語レベルの仕様というものは一見きちんと決める必要がなさそうに思えますが、実際にはプラットフォームごとにある程度の仕様が決まっています。その仕様のことをABI（Application Binary Interface）と言います。

本書でここまでに説明した関数の呼び出し方では、引数は特定の順番でレジスタに置かれるということになっていました。また、返り値はRAXにセットされるという約束になっていました。こういった関数の呼び出し方のルールのことを「関数呼び出し規約」（function calling convention）といいます。関数呼び出し規約はABIの一部です。

C言語のABIには、引数や返り値の渡し方の他に次のようなものも含まれています。

• 関数呼び出しで変更されるレジスタとされないレジスタ（RBPなどはリターンの前に元の値に戻されますが、いくつかのレジスタについては元の値に戻さなくてよいことになっています）
• intやlongなどの型のサイズ
• 構造体のレイアウトのルール（構造体のメンバがメモリ上で実際にどのような配置になるのかというルール）
• ビットフィールドのレイアウトのルール（例えば最下位ビットからビットフィールドを並べるのか、最上位ビットから並べるのか、など）

ABIはソフトウェアレベルのいわばただのお約束にすぎないので、本書で説明しているのとは異なるものを考えることは可能ですが、ABI互換性のないコードはお互い呼び出して使うことができないので、基本的にはCPUベンダやOSベンダがプラットフォーム標準のABIを定義しています。x86-64では、UnixやmacOSで使われているSystem V ABIいうものと、Windowsで使われているMicrosoft ABIの2つが広く使われています。なお、この2つの呼び出し規約は必然性があって別れているわけではなく、単に別々の人たちが別々に規約を策定しただけです。

本書ではここまでに、自作のコンパイラから、別のコンパイラでコンパイルした関数を呼び出すといったことを行ってきました。そういうことが可能だったのは我々のCコンパイラと別のコンパイラのABIが同じだったからです。

コンピュータにおける整数の表現

このあたりで、コンピュータでどのように整数、特に負の整数が表現されているのかを理解しておきましょう。この章では、符号なしの数の表現方法と、「2の補数表現」（two's complement）による符号ありの数の表現方法を説明します。

本書では2進のビットパターンは、0bプレフィックスをつけて、見やすくするために4桁ごとにアンダースコアで区切って、0b0001_1010のように表すことにします。0bプレフィックスは実際、コンパイラ独自拡張として多くのCコンパイラでそのまま使うことができます（ただしアンダースコアを含めることは普通できません）。

符号なし整数

符号なし整数（unsigned integer）の表現は通常の2進数と同じです。10進数の数が、下の桁から順に1の桁、10の桁、100の桁、1000の桁、⋯⋯（すなわち10⁰の桁、10¹の桁、10²の桁、10³の桁、⋯⋯）を表しているのと同じように、2進数の数は、下の桁から1の桁、2の桁、4の桁、8の桁、⋯⋯（すなわち2⁰の桁、2¹の桁、2²の桁、2³の桁、⋯⋯）を表しています。

例えば0b1110というビットパターンが表している符号なし整数の値は、1になっているビットの位置を見てみればわかります。この場合、2桁目、3桁目、4桁目、すなわち2の桁、4の桁、8の桁が1になっているので、0b1110は2 + 4 + 8 = 14を表しています。いくつかの例の図を以下に示します。

符号なし整数に1を足していくと、次のグラフで示すように値が循環します。これは4ビット整数の例です。

演算結果が桁あふれして、無限にビットがあるときとは異なる結果になることを「オーバーフローする」といいます。例えば8ビット整数では1+3はオーバーフローしませんが、200+100や20-30はオーバーフローして、それぞれ44と246になります。数学的にいうと2⁸ = 256で割った余りと同じになります。

符号あり整数

符号あり整数（signed integer）では、最上位ビット（most significant bit）を特別に扱う「2の補数表現」というものが使われます。2の補数表現におけるn桁の整数では、n桁目以外は符号なしの場合と同じ数を表していますが、最上位のn桁目だけは、2^n-1ではなく-2^n-1を表すというルールになっています。

具体的に4桁の2進数で考えてみると、それぞれの桁と、その桁が表している数は、次の表の通りになります。

符号なしと同様、あるビットパターンが表している符号ありの値は、1になっているビットの位置を見ればわかります。たとえば0b1110を4桁の符号あり整数と見なすと、2桁目、3桁目、4桁目、すなわち2の桁、4の桁、-8の桁が1になっているので、0b1110は2 + 4 + (-8) = -2を表していることになります。いくつかの例の図を以下に示します。

このルールにおいては、最上位ビットがオンになっていない限り、符号あり整数が表している数は、それを符号なし整数として解釈した数と同じです。4ビット整数の場合、0〜7は、符号ありでもなしでも同じビットパターンになります。一方、4ビット目がオンの場合、そのビットパターンは-8〜-1（0b1000〜0b1111）のいずれかの数を表していることになります。最上位ビットがオンの場合には負数になるので、最上位ビットを「符号ビット」（sign bit）ということもあります。

符号あり整数に1を足していくと、次のグラフで示すように値が循環します。これは4ビット整数の例です。

上記のルールを理解してみると、プログラミングをしていると一般的に見かける、符号あり整数の様々な一見奇妙な振る舞いの説明がつくようになります。

符号あり整数に1を足していくと、オーバーフローしたところで大きな数から極端に小さな数になってしまうのは、読者の皆さんも経験したことがあるでしょう。これは2の補数表現を考えてみると、具体的に何が起きているのか理解できます。たとえば8ビットの符号あり整数では、最大の数は0b0111_1111すなわち127です。これに1を足すと0b1000_0000になり、2の補数表現においては-128ということになります。これは絶対値が最大の負の数です。

単項-のテストでmainから例えば-3をリターンした場合、プログラム全体の終了コードは253になったはずです。これは、mainがRAXに-3すなわち0b1111_​1111_​1111_​1111_​1111_​1111_​1111_​1101をセットしたのに対して、それを受け取る側ではRAXの下位8ビットだけが意味のある値と考えていて、それを符号なし整数として扱うので、0b1111_1101すなわち253が返り値であるかのような結果になったというわけです。

このように、あるビットパターンがどういう数を表しているかというのは、読む側の想定で変わってきます。例えば紙の本の文字というのが結局のところインクのシミであって、それを文章だと思って読む人間がいるからこそ意味が生じるように、コンピュータのメモリ上にあるものもオンとオフのビットの列に過ぎず、それ自体に本来の意味というものがあるわけではありません。ある数値を受け渡しするためには、値をセットする側とそれを読む側で解釈の方法が一致している必要があります。

なお、2の補数表現では、表現可能な負の数は、表現可能な正の数より1つ多くなっています。例えば8ビット整数では、-128は表現可能ですが、+128は表現可能な範囲からぎりぎり外れています。このように正負の範囲がアンバランスになるのは、仕組み上、仕方がありません。nビットで表せるパターンは2ⁿ通り、つまり常に偶数通りありますが、0のために1つのビットパターンを割り当てると、奇数個のパターンが残るので、正の数と負の数のどちらかが多くなってしまうのです。

符号拡張

コンピュータでは、数値のビットの幅を広げるという操作がよく出てきます。たとえば8ビットの数値をメモリから読んで64ビットレジスタにセットする場合、8ビットの値を64ビットに伸ばす必要があります。

符号なし整数を扱っている場合、値を拡張するのは簡単で、単に上位ビットを0で埋めるだけで構いません。たとえば4ビットの値0b1110 = 14を8ビットに拡張すると0b0000_1110 = 14になります。

一方、符号あり整数を扱っている場合、上位ビットを0で埋めてしまうと数が変わってしまいます。例えば4ビットの値0b1110 = -2を8ビットに拡張したつもりで、0b0000_1110としてしまうと、14になってしまいます。これはそもそも符号ビットが立っていないので負の数ですらありません。

符号あり整数を拡張する場合は、符号ビットが1ならば新たな上位ビットをすべて1で、符号ビットが0ならば新たな上位ビットをすべて0で埋める必要があります。この操作は「符号拡張」（sign extension）と呼ばれます。たとえば4ビットの値0b1110 = -2を8ビットに符号拡張すると、0b1111_1110 = -2となり、うまくビット幅が伸ばせていることがわかります。

符号なし整数では、数値の左側に無限に0が続いていて、拡張するときにはそれを取り出していると考えることができます。

同様に、符号あり整数では、数値の左側に符号ビットと同じ値が無限に続いていて、拡張するときにはそれを取り出していると考えることができます。

このように、ある数値をよりビット幅の広いところにフィットさせようとしている場合、自分がいま扱っている値が符号なしなのか符号ありなのかを意識しておく必要があります。

符号の反転

2の補数表現の詳細は、コンパイラ作成のために必ずしも必要な知識というわけではないのですが、いくつか2の補数表現に関する技を覚えておくと、ちょっとしたときにいろいろ便利です。ここでは数値の正負を反転する簡単な方法を説明します。

2の補数表現では、「全てのビットを反転して1を足す」という操作をすると、数値の正負が反転します。たとえば8ビット符号あり整数で、3から-3のビットパターンを求める手順は次のようになります。

1. 数値を2進数で表す。3の場合、0b0000_0011。
2. 全ビットを反転する。この場合、0b1111_1100になる。
3. 1を足す。この場合、0b1111_1101になる。これが-3のビットパターン。

上記の方法を覚えておくと、負数のビットパターンを簡単に求めることができます。

また、符号ビットが立っているビットパターンを、同じ操作を行うことによって正の数にすることで、そのビットパターンが表している数値を簡単に求められることがあります。例えば0b1111_1101が何を表しているのか、単純に足し算で求めるのは面倒ですが、ビットを反転して1を足すと0b0000_0011になり、3の反転すなわち-3を表していたということが簡単にわかります。

上記のトリックが動く理由は割と単純です。ここまでに、2の補数表現の演算を数学的にきちんと定義をしていないので、やや曖昧な説明になりますが、アイデアは次の通りです。

全ビットを反転するというのは、-1すなわち全ビットが1のビットパターンから引くのと同じです。たとえば0b0011_0011というビットパターンは、次のようにして反転することができます。

つまり数値nを表すビットパターンを反転するのは、-1 - nを計算することと同じです。それに1を足すと、(-1 - n) + 1 = -nを計算しているということになり、nに対して-nを求めることができたということになるわけです。

ポインタと文字列リテラル

ここまでの章で、それなりに意味のある計算ができる言語が出来上がりつつありますが、我々の言語ではまだHello worldを表示することすらできません。そろそろ文字列を追加して、意味のあるメッセージをプログラムから出力できるようにしたいところです。

Cの文字列リテラルは、char型とグローバル変数、配列と密接に関係があります。例として以下の関数を考えてみてください。

int main(int argc, char **argv) {
  printf("%d\n", argc);
}

上記のコードは、下のコードと同じようにコンパイルすることになります。ただしmsgというのは他の識別子とは被らないユニークな識別子とします。

char msg[4] = "%d\n";

int main(int argc, char **argv) {
  printf(msg, argc);
}

我々のコンパイラは、文字列リテラルをサポートするための機能がまだいくつか欠けています。文字列リテラルをサポートして、printfなどでメッセージを表示できるように、この章では次の機能を順に実装していきましょう。

1. 単項&と単項*
2. ポインタ
3. 配列
4. グローバル変数
5. char型
6. 文字列リテラル

また、上記の機能をテストするために必要な機能などもこの章で追加していきます。

ステップ16: 単項&と単項*

このステップでは、ポインタを実装する最初のステップとして、アドレスを返す単項&と、アドレスを参照する単項*を実装します。

これらの演算子は本来はポインタ型の値を返したり、ポインタ型の値を取ったりする演算子ですが、我々のコンパイラにはまだ整数以外の型がないので、ポインタ型は整数型で代用することにします。すなわち、&xは変数xのアドレスを単なる整数として返します。また、*xは、xの値をアドレスとみなして、そのアドレスから値を読んでくるという演算ということになります。

そのような演算子を実装すると、次のようなコードが動くようになります。

x = 3;
y = &x;
return *y; // 3を返す

また、ローカル変数がメモリ上で連続して割り当てられているということを利用して、スタック上の変数にポインタ経由で間接的に無理やりアクセスすることもできます。以下のコードでは、スタック上の変数yの8バイト上に変数xがあることを前提にしています。

x = 3;
y = 5;
z = &y + 8;
return *z; // 3を返す

このようなポインタ型と整数型を区別しない実装では、例えば*4という式はアドレス4から値を読み出す式ということになってしまいますが、それはとりあえずよいということにしましょう。

実装は比較的簡単です。単項&と単項*を追加した文法を以下に示します。この文法に従ってパーサに変更を加えて、単項&と単項*をそれぞれND_ADDRとND_DEREFという型のノードとして読み込むようにしてください。

unary = "+"? primary
      | "-"? primary
      | "*" unary
      | "&" unary

コードジェネレータに加える変更はごくわずかです。変更点を以下に示します。

  case ND_ADDR:
    gen_lval(node->lhs);
    return;
  case ND_DEREF:
    gen(node->lhs);
    printf("  pop rax\n");
    printf("  mov rax, [rax]\n");
    printf("  push rax\n");
    return;

ステップ17: 暗黙の変数定義を廃止して、intというキーワードを導入する

いままでは変数や関数の返り値はすべて暗黙のうちにintということになっていました。したがってわざわざint x;というように変数をその型名と一緒に定義することはせず、新しい識別子はすべて新しい変数名だとみなしていました。今後はそのような仮定を置くことはできなくなります。そこで、まずその点を改造します。以下の機能を実装してください。

• 新しい識別子を変数名とみなすのはやめて、定義されていない変数が現れたらエラーにしてください。
• int x;という形で変数を定義するようにしてください。int x = 3;といった初期化式などはサポートする必要はありません。同様にint x, y;といったものも必要ありません。なるべく単純なものだけを実装します。
• 関数はいままでfoo(x, y)といった形で書いていましたが、これをint foo(int x, int y)といった形になるように改造します。現状、トップレベルは関数定義しかないはずなので、パーザはまずintを読み、そのあとは必ず関数名のはずなのでそれを読み、次にint <引数の名前>という列を読む、ということになります。これ以上難しい構文には対応する必要はないですし、「将来の拡張にそなえて」といった念のためになにかする必要もありません。単純に"int <関数名>(<int <変数名>の繰り返しからなる引数リスト>)"を読むために十分なだけのコードを書いてください。

ステップ18: ポインタ型を導入する

ポインタを表す型を定義する

このステップでは、いままでは型名にintしか許していなかったのを、intのあとに*が0個以上続く、というものを型名として許すことにします。すなわちint *xやint ***xといった定義を構文解析できるようにします。

「intへのポインタ」といった型はコンパイラの中で無論扱える必要があります。たとえば変数xがintへのポインタだとしたら、コンパイラは式*xはint型だとわからなければいけないわけです。「intへのポインタへのポインタへのポインタ」というように型はいくらでも複雑にできるので、これは固定のサイズの型だけで表すことはできません。

ではどうするかというと、ポインタを使います。今まで変数に対してマップを通して紐付けられている情報は、スタック上のベースポインタ（RBP）からのオフセットだけでした。これに変更を加えて、変数の型を持てるようにしてください。変数の型というのは、大雑把にいうと、次のような構造体になるはずです。

struct Type {
  enum { INT, PTR } ty;
  struct Type *ptr_to;
};

ここでtyはint型か「～へのポインタ」型かという2つの値のどちらかを持つことができます。ptr_toはtyが「～へのポインタ」型であるときのみに意味のあるメンバーで、そのときには、「～」が指すTypeオブジェクトへのポインタを入れておきます。たとえば「intへのポインタ」なら、その型を表すデータ構造は内部的に次のようになるわけです。

「intへのポインタへのポインタ」なら次のようになります。

このようにすればコンパイラ内部でいくらでも難しい型を表すことができるというわけです。

ポインタが指している値に代入する

代入式の左辺が単純な変数名ではない式、たとえば*p=3のような式はどのようにコンパイルすればよいのでしょうか？ こういった式も、左辺が単純な変数のときと基本的な概念は変わりません。この場合には、pのアドレスが生成されるように、*pを左辺値としてコンパイルすればよいのです。

*p=3を表す構文木をコンパイルするときは、再帰的にツリーを下りながらコード生成していくわけですが、まず最初に呼ばれるのは*pを左辺値としてコンパイルするためのコードジェネレータです。

そのコードジェネレータでは与えられた構文木の型に応じて分岐することになります。単純な変数では前述のとおりその変数のアドレスを出力するコードを出力することになるわけですが、ここではデリファレンス演算子が与えられているので、違った動作をする必要があります。デリファレンス演算子が与えられている場合、その中の構文木を「右辺値」としてコンパイルしてください。そうすると、それは何らかのアドレスを計算するコードにコンパイルされるはずです（そうでなければその結果をデリファレンスすることはできません）。そしてそのアドレスをそのままスタックに残しておけばよいというわけです。

この段階までが完成したら、次のような文をコンパイルできるようになるはずです。

int x;
int *y;
y = &x;
*y = 3;
return x; // → 3

ステップ19: ポインタの加算と減算を実装する

このステップでは、ポインタ型の値pに対してp+1やp-5のような式を書けるようにします。これはただの整数の加算と同じように見えますが、実際には結構異なる演算です。p+1は、pが持っているアドレスに1を足す、という意味ではなくて、pの次の要素を指すポインタにする、という意味なので、ポインタが指しているデータ型の幅をpに足してやらなければいけないわけです。たとえばpがintを指している場合、我々のABIでは、p+1はアドレスのバイト数としては4を足すことになります。一方でpがintへのポインタへのポインタである場合、p+1は8を足すことになります。

したがってポインタの加減算では、型のサイズを知る方法が必要になりますが、現状ではintなら4、ポインタなら8なので、そのように決め打ちでコードを書いてください。

この段階ではまだ連続してメモリをアロケートする方法がないので（我々のコンパイラにはまだ配列がない）、テストを書くのはちょっと大変です。ここは単に外部のコンパイラの助けを借りて、そちらのほうでmallocすることにして、自分のコンパイラの出力ではそのヘルパー関数を使ってテストを書くようにしてみてください。例えばこんな感じでテストできるでしょう。

int *p;
alloc4(&p, 1, 2, 4, 8);
int *q;
q = p + 2;
*q;  // → 4
q = p + 3;
return *q;  // → 8

ステップ20: sizeof演算子

sizeofは、見た目は関数のようですが、文法的には単項の演算子です。Cではほとんどの演算子は記号ですが、文法的には演算子を記号にしなければいけない理由は特になく、実際にsizeofはその例外になっています。

sizeof演算子の動作をちょっと復習してみましょう。sizeofは引数の式の型がメモリ上で何バイトなのかを返す演算子です。例えば我々のABIでは、sizeof(x)は、xがintならば4、xがポインタなら8を返します。sizeofの引数には任意の式を書くことができて、例えばsizeof(x+3)は、x+3という式の型が全体としてintならば4、ポインタならば8を返すことになります。

我々のコンパイラにはまだ配列はありませんが、sizeof(x)は、xが配列ならばx全体のサイズをバイト数として返すことになります。例えばxがint x[10]というように定義されている場合、sizeof(x)は40を返します。xがint x[5][10]というように定義されている場合、sizeof(x)は200、sizeof(x[0])は40、sizeof(x[0][0])は4になります。

sizeof演算子の引数は、型を知るために書かれているだけで、実際に実行される式ではありません。例えばsizeof(x[3])という式を書いても、x[3]へのアクセスは実際には発生しません。x[3]という式の型が全体として何であるかはコンパイル時にわかるので、sizeof(x[3])という式は、コンパイル時にその型のサイズに置き換えられることになります。したがってx[3]といったsizeofに与えられた具体的な式は実行時には存在しなくなっています。

sizeofの動作を下に示します。

int x;
int *y;

sizeof(x); // 4
sizeof(y); // 8

sizeof(x + 3); // 4
sizeof(y + 3); // 8
sizeof(*y);    // 4

// sizeofに渡す式は何でもよい
sizeof(1); // 4

// sizeofの結果は現在int型なのでsizeof(int)と同じ
sizeof(sizeof(1)); // 4

さて、このsizeof演算子を実装してみましょう。sizeof演算子を実装するためには、トークナイザとパーサの両方に手を入れることになります。

まず、トークナイザに変更を加えて、sizeofというキーワードをTK_SIZEOFという型のトークンとして認識するようにしてください。

次にパーサに変更を加えて、sizeofをint型の定数に置き換えてしまいます。sizeof演算子を追加した文法を以下に示します。以下の文法において、sizeofは単項演算子で、単項プラスや単項マイナスと同じ優先順位を持つという定義になっています。これはCの文法と同じです。

unary = "sizeof" unary
      | ("+" | "-")? primary

この文法では、sizeof(x)だけではなくsizeof xのような書き方も文法上許されることになりますが、実際のCでもそれは同じです。

パーサでは、sizeof演算子が出現したら、その引数になっている式を通常通りにパースして、その結果の構文木に紐づいている型がintならば4、ポインタならば8という数に置き換えるようにしてください。パーサで定数に置き換えてしまうのでコード生成木には変更を加える必要はありません。

ステップ21: 配列を実装する

配列型を定義する

このステップでは配列を実装します。この段階まではレジスタに入る大きさのデータしか扱ってきていませんでしたが、今回初めてそれより大きなデータが登場します。

とはいえCの文法は配列については抑制的です。関数の引数として配列を渡したり、関数の返り値として配列を返したりすることはできません。そういう意図のコードを書くと、配列そのものが値渡しされるのではなく、その配列を指すポインタが自動的に作られてそれが渡されることになります。配列に配列を直接代入してコピーする、といったこともサポートされていません（memcpyを使わないといけない）。

したがって、レジスタに入らないデータを関数や変数の間でやり取りする必要はありません。1ワードより大きいメモリ領域をスタック上に割り当てる機能があれば十分です。

次のような変数定義を読み込めるようにしてください。

int a[10];

上記のaの型は配列であり、その配列は長さが10で、要素の型はintです。ポインタ型と同様、配列の型もいくらでも複雑にできるので、ステップ7と同じように、ptr_toで配列の要素の型は指し示すようにします。型を表す構造体は次のようになるはずです。

struct Type {
  enum { INT, PTR, ARRAY } ty;
  struct Type *ptr_to;
  size_t array_size;
};

ここでarray_sizeは配列型のときにのみ意味のあるフィールドで、配列の要素数を持つ変数です。

ここまでできれば配列のための領域をスタックにアロケートするのは簡単にできるはずです。配列のバイト単位での大きさを求めるためには、配列の要素のバイト単位での大きさと配列の要素数をかければいいだけです。いままではすべての変数を1ワードとしてスタック領域を確保していたはずですが、それを変更して、配列は配列に必要な大きさを確保するようにしてください。

配列からポインタへの暗黙の型変換を実装する

配列とポインタはよく組み合わせて使われるので、Cでは構文上、ポインタと配列をあまり区別せずともなんとなく動くようになっているのですが、それが裏目に出て、配列とポインタの関係がどうなっているのか、プログラマにとってわかりにくくなってしまっているようです。そこでここでは配列とポインタの関係について説明をします。

まずCにおいては配列とポインタは完全に別々の型です。

ポインタは（x86-64では）8バイトの値の型です。intに対して+や-といった演算子が定義されているように、ポインタに対しても+や-が（やや異なる形で）定義されています。ポインタにはそれに加えて、単項*演算子が定義されていて、それを使うことでポインタの指している先を参照することができます。単項*を除けばポインタにはそれほど特別なことはないといってよいでしょう。言ってみればポインタはintのような普通の型です。

一方で配列は何バイトにでもなりうる型です。ポインタとは異なり、配列に対しては演算子がほとんど定義されていません。定義されている演算子は、配列のサイズを返すsizeof演算子と、配列の先頭の要素のポインタを返す&演算子だけです。それ以外、配列に対して適用できる演算子はありません。

ではなぜa[3]のような式がコンパイルできるのでしょうか？ Cでは、a[3]は*(a+3)と等価であるものとして定義されています。配列に対して+演算子は定義されていないのではなかったのでしょうか？

ここで配列が暗黙のうちにポインタに変換される、という文法が効いてくることになります。sizeofか単項&のオペランドとして使われるとき以外、配列は、その配列の先頭要素を指すポインタに暗黙のうちに変換されるということになっているのです。したがって、*(a+3)は、配列aの先頭要素を指すポインタに3を足したものをデリファレンスする、という式になり、それは結果的に配列の3番目の要素をアクセスするのと同じ意味になります。

Cにおいては配列アクセスのための[]演算子というものはありません。Cの[]は、ポインタ経由で配列の要素にアクセスするための簡便な記法にすぎないのです。

同様に、関数引数として配列を渡すとその配列の先頭要素へのポインタになったり、ポインタに対して配列を直接代入しているかのような書き方ができたりしますが、それも上記のような理由によります。

というわけで、コンパイラは、ほとんどの演算子の実装において、配列をポインタに型変換するということを行わなければなりません。これは実装するのはさほど難しくはないでしょう。sizeofと単項&を実装している場合を除き、演算子のオペランドをパーズしたら、その型がTの配列だったらTへのポインタということにしてしまう、とすればよいはずです。コードジェネレータでは、配列型の値は、その値のアドレスをスタックにプッシュするというコードを生成すればよいはずです。

ここまで完成すれば、次のようなコードが動くようになるはずです。

int a[2];
*a = 1;
*(a + 1) = 2;
int *p;
p = a;
return *p + *(p + 1)  // → 3

ステップ22: 配列の添字を実装する

Cでは x[y]は*(x+y)と等価であるものとして定義されています。したがって添字の実装は比較的簡単です。単純にx[y]をパーザの中で*(x+y)として読み換えるようにしてください。たとえばa[3]は*(a+3)になります。

この文法では、3[a]は*(3+a)に展開されるので、a[3]が動くなら3[a]も動くはずですが、なんとCでは3[a]のような式は実際に合法です。試してみてください。

ステップ23: グローバル変数を実装する

そろそろリテラルの文字列をプログラムに書けるようにしたいところです。Cではリテラルの文字列はcharの配列です。すでに配列は実装しているからよいのですが、リテラルの文字列はスタック上に存在している値ではない、という点が違います。文字列リテラルは、スタック上ではなく、メモリ上の固定の位置に存在しているわけです。したがって、文字列リテラルを実装するために、まずグローバル変数を足すことにします。

いままではトップレベルには関数定義しか許していなかったはずです。その文法を変更して、トップレベルにグローバル変数を書けるようにします。

変数定義は関数定義と見た目が似ているので構文解析はややトリッキーです。たとえば次の4つの定義を比べてみてください。

int *foo;
int foo[10];
int *foo() {}
int foo() {}

上の2つのfooは変数定義で、下の2つは関数定義ですが、その2つは、関数名あるいは変数名になる識別子まで到達して、その次のトークンを読んでみるまで区別がつきません。したがって、まず「型名の前半を読む」関数を呼び、そのあとに識別子が来ているはずなのでそれを読み、それからトークンを1つ先読みしてみる必要があります。先読みしたトークンが"("なら関数定義を読んでいた、ということになりますし、そうでなければ変数定義を読んでいた、ということになります。

パースしたグローバル変数の名前はマップにいれて、名前でルックアップできるようにしてください。変数名がローカル変数として解決できなかった場合に限り、グローバル変数として解決を試みます。これによりローカル変数が同名のグローバル変数を隠すという動きが自然に実装できます。

パーザでは、ローカル変数の参照とグローバル変数の参照は抽象構文木の別のノードに変換します。パースの段階で名前が解決できるので、その段階でタイプも分けてしまうというわけです。

いままではすべての変数がスタックにあったはずなので、変数の読み書きはRBP（ベースポインタ）からの相対で行なっていました。グローバル変数はスタック上にある値ではなく、メモリ上の固定の位置にある値なので、そのアドレスに直接アクセスするようにコンパイルします。実際のgccの出力を参考にしてみてください。

実装してみると、ローカル変数とグローバル変数がかなり異なるものであることにびっくりするはずです。見た目上区別することなく書くことができるのは、C言語がうまく抽象化しているからですね。ローカル変数とグローバル変数は、実は内部ではかなり違うように実装されているのです。

ステップ24: 文字型を実装する

配列は1ワードより大きくなりうる型でしたが、文字は1ワードより小さな型です。みなさんは、このステップに至るまでに、型を表すオブジェクトを受け取って、その型のサイズのバイト数を返す関数を書く必要があったと思います。まずは文字という型を足し、そのあとにその関数に変更を加え、文字型に対して1を返すようにしてください。

このステップではリテラルの文字（シングルクオートでくくられた文字）を実装する必要はありません。一気に実装したくなる気持ちは抑えてなるべく小さな変更にとどめます。

したがってこのステップでは文字というのは本当にただの小さな整数型です。movsx ecx, BYTE PTR [rax]というようにすると、RAXが指しているアドレスから1バイトを読み込んでECXに入れることができます。符号拡張が不要な場合はmovzx ecx, BYTE PTR [rax]というようにmovzx命令を使ってください。書き出す時にはmov [rax], clというように、ソースのレジスタとして8ビットレジスタを使います。

実際のコンパイラの出力を参考にしてください。

このステップが実装できれば、次のようなコードが動くようになるはずです。

char x[3];
x[0] = -1;
x[1] = 2;
int y;
y = 4;
return x[0] + y;  // → 3

ステップ25: 文字列リテラルを実装する

このステップではダブルクオートでくくられた文字列をパースしてコンパイルできるようにします。配列とグローバル変数、文字型という必要なパーツが揃ったので、比較的簡単に実装できると思います。

まずはトークナイザに手を入れて、ダブルクオートを見つけたら、次のダブルクオートまで読んで文字列トークンを作成するようにしてください。このステップではバックスラッシュによるエスケープなどは実装する必要はありません。ステップバイステップで行くのが重要なので、簡単に実装できそうに思えても、しないようにしてみてください。

文字列リテラルのデータを表すアセンブリのコードは、CPUに実行されるマシンのコードを生成している途中に出力することはできません。出力されるアセンブリでは、グローバルなデータと、コードは、混ぜずに書く必要があります。つまり、コードを出力するときには、コード中に出現していたすべての文字列リテラルをまず出力してしまいたいわけですが、そのために構文木をくだるのは面倒です。これをするためには、今までに見た文字列リテラルがすべて入っているベクタというのを用意して、パーザが文字列をみるたびにそれに単に足して行くようにするのが簡単でしょう。

実際のコンパイラの出力を参考にしてください。

ここまでくるとprintfで文字列を出力することも可能になっているはずです。自分で作ったプログラミング言語を使って、テストコードのような自明なものではなく、もうちょっと凝ったプログラムを書いてみるよい機会です。たとえば8クイーン問題のソルバーなどは自作言語で書けるのではないでしょうか？ 人類はデジタルコンピュータの発明から、このレベルで簡単にコードが書けるプログラミング言語の開発まで、何十年もかかりました。それが数週間で実装できるのは人類の、そしてあなたの素晴らしい進歩です。

（可変長引数を取る関数を呼ぶときは、浮動小数点数の引数の個数をALに入れておく、ということになっています。我々のコンパイラにはまだ浮動小数点数がありません。したがって、関数を呼ぶ前に常にALに0をセットするようにしましょう。）

ステップ26: 入力をファイルから読む

ここまでは引数の文字列に直接Cコードを渡していましたが、次第に入力が長くなってきているので、そろそろ普通のCコンパイラのようにコマンドライン引数としてファイル名を取るように改造してみましょう。与えられたファイルを開いてその内容を読み、'\0'で終端された文字列を返す関数は、次のように簡潔に書くことができます。

#include <errno.h>
#include <stdio.h>
#include <string.h>

// 指定されたファイルの内容を返す
char *read_file(char *path) {
  // ファイルを開く
  FILE *fp = fopen(path, "r");
  if (!fp)
    error("cannot open %s: %s", path, strerror(errno));

  // ファイルの長さを調べる
  if (fseek(fp, 0, SEEK_END) == -1)
    error("%s: fseek: %s", path, strerror(errno));
  size_t size = ftell(fp);
  if (fseek(fp, 0, SEEK_SET) == -1)
    error("%s: fseek: %s", path, strerror(errno));

  // ファイル内容を読み込む
  char *buf = calloc(1, size + 2);
  fread(buf, size, 1, fp);

  // ファイルが必ず"\n\0"で終わっているようにする
  if (size == 0 || buf[size - 1] != '\n')
    buf[size++] = '\n';
  buf[size] = '\0';
  fclose(fp);
  return buf;
}

コンパイラの実装の都合上、すべての行が改行文字で終わっているほうが、改行文字かEOFで終わっているデータよりも扱いやすいので、ファイルの最後のバイトが\nではない場合、自動的に\nを追加することにしました。

厳密にいうと、この関数は、ランダムアクセスできない特殊なファイルが与えられた場合にはうまく動きません。例えば標準入力を表しているデバイスファイル/dev/stdinや名前付きパイプをファイル名として指定すると、/dev/stdin: fseek: Illegal seekといったエラーメッセージが表示されることが確認できるはずです。とはいえ実用上はこの関数で問題ないでしょう。この関数を使ってファイルの内容を読み込んで、それを入力として扱うようにコードを変更してください。

入力ファイルは普通は複数の行を含んでいるので、エラーメッセージを表示する関数も強化しておきましょう。エラーが発生したときに、入力ファイル名とエラーがある行の行番号、その行の内容を表示することにすると、エラーメッセージは次のようになります。

foo.c:10: x = y + + 5;
                  ^ 式ではありません

このようなエラーメッセージを表示する関数は次のようになります。

// 入力ファイル名
char *filename;

// エラーの起きた場所を報告するための関数
// 下のようなフォーマットでエラーメッセージを表示する
//
// foo.c:10: x = y + + 5;
//                   ^ 式ではありません
void error_at(char *loc, char *msg) {
  // locが含まれている行の開始地点と終了地点を取得
  char *line = loc;
  while (user_input < line && line[-1] != '\n')
    line--;

  char *end = loc;
  while (*end != '\n')
    end++;

  // 見つかった行が全体の何行目なのかを調べる
  int line_num = 1;
  for (char *p = user_input; p < line; p++)
    if (*p == '\n')
      line_num++;

  // 見つかった行を、ファイル名と行番号と一緒に表示
  int indent = fprintf(stderr, "%s:%d: ", filename, line_num);
  fprintf(stderr, "%.*s\n", (int)(end - line), line);

  // エラー箇所を"^"で指し示して、エラーメッセージを表示
  int pos = loc - line + indent;
  fprintf(stderr, "%*s", pos, ""); // pos個の空白を出力
  fprintf(stderr, "^ %s\n", msg);
  exit(1);
}

このエラーメッセージ出力ルーチンは、かなり簡単な作りですが、そのわりに結構本格的な見た目のフォーマットでエラーを出力すると言えるのではないでしょうか。

ステップ27: 行コメントとブロックコメント

我々のコンパイラも次第に進化してきて、本格的なコードが書けるようになってきました。こうなると欲しくなるのがコメントです。この章ではコメントを実装します。

Cには2種類のコメントがあります。一つのコメントは行コメントと呼ばれるもので、//から行末までがコメントになります。もう一つはブロックコメントと呼ばれるもので、/*が開始記号、*/が終了記号ということになっています。ブロックコメントの中の文字は、*/という2文字の並びを除いてすべて読み飛ばされます。

文法上、コメントは1個の空白文字と同じ扱いということになっています。したがってコメントは、トークナイザで空白文字と同じように読み飛ばすのが自然です。コメントを読み飛ばすコードを以下に示します。

void tokenize() {
  char *p = user_input;

  while (*p) {
    // 空白文字をスキップ
    if (isspace(*p)) {
      p++;
      continue;
    }

    // 行コメントをスキップ
    if (strncmp(p, "//", 2) == 0) {
      p += 2;
      while (*p != '\n')
        p++;
      continue;
    }

    // ブロックコメントをスキップ
    if (strncmp(p, "/*", 2) == 0) {
      char *q = strstr(p + 2, "*/");
      if (!q)
        error_at(p, "コメントが閉じられていません");
      p = q + 2;
      continue;
    }
    ...

ここではブロックコメントの終端を探すために、C標準ライブラリに入っているstrstr関数を使いました。strstrは、文字列から文字列を探して、渡された文字列が見つかったときはその先頭へのポインタ、見つからなかったときにはNULLを返します。

a//*
// */ b

/* /* ... */ */

#if 0
...
#endif

ステップ28: テストをCで書き直す

このステップではテストを書き直してmake testを高速化します。このステップに至ったころにはすでにシェルスクリプトに100個以上のテストが書かれていることでしょう。シェルスクリプトのテストではテスト1つにつき何個ものプロセスが起動されます。つまりテスト1つごとに自作コンパイラ、アセンブラ、リンカ、テストそのものを起動しています。

プロセスの起動というものは小さなプログラムでもそこまで速くありません。したがってそれを何百回も行うとなると、トータルでは無視できない時間がかかるようになってしまいます。おそらくみなさんのテストスクリプトも実行に数秒かかるようになっていると思います。

そもそもシェルスクリプトでテストを書いていたのは、そうしなければまともなテストができなかったからでした。電卓レベルの言語の段階では、ifや==などがなかったので、計算結果が正しいかどうかその言語の中では検証できなかったのです。しかし今は検証できるようになりました。結果が正しいかどうかを比較して、間違っている場合は（文字列の）エラーメッセージを表示してexitする、ということが可能になっているのです。

そこで、このステップでは、シェルスクリプトで書いていたテストをCファイルに書き直してください。

プログラムの実行イメージと初期化式

さて、ここまでのステップで、我々のコンパイラは関数、グローバル変数、ローカル変数というプログラミングの主要な要素をすべてサポートするようになりました。また、読者の皆さんも、分割コンパイルとリンクについて学んだことで、プログラムを小分けにしてコンパイルして、最後にそれを1つのファイルにまとめる方法について理解することができたと思います。

この章では、OSが実行ファイルをどのように実行するのかについて説明します。この章を読むことにより、実行ファイルにどのようなデータが入っていて、main関数が呼ばれるまでに何が起こっているのかが理解できるようになります。

また、この章では、変数の初期化式、すなわち下のようなコードがどのようにコンパイルされるのかについて説明を行い、初期化式のサポートを我々のコンパイラに追加します。

int x = 3;
int y[3] = {1, 2, 3};
char *msg1 = "foo";
char msg2[] = "bar";

初期化式をサポートするためには、意外かもしれませんが、プログラムがmainに到るまでにどのように動いているのかという知識が欠かせないのです。

なお、この章では、1つの実行ファイルにすべてのコードやデータがまとめて入っている単純な実行形式について説明します。そのような実行形式のファイルのことを「スタティックリンク」された実行ファイルといいます。スタティックリンクに対して、1つのプログラムの断片が複数のファイルに分かれて入っていて、実行時にそれらがメモリ上で結合されて実行される「ダイナミックリンク」という実行形式も広く使われていますが、それについては章を分けて説明することにします。まずは基本的なモデルであるスタティックリンクについてしっかり理解してみましょう。

実行ファイルの構造

実行ファイルは、ファイルヘッダと、1つ以上の「セグメント」（segment）と呼ばれる領域からできています。1つの実行ファイルには、普通は少なくとも2つのセグメントがあって、実行可能コードとデータが別々に入っています。実行可能コードが入っているセグメントのことを「テキストセグメント」（text segment）、それ以外のデータが入っているセグメントのことを「データセグメント」（data segment）といいます。実際の実行ファイルにはその他のセグメントも入っていますが、仕組みを理解するためには不要なのでここでは省略します。

なお、用語についてですが、テキストというのはテキストファイルのテキストと同じ単語ですが、意味が違うので注意してください。伝統的に低レイヤでは、機械語を表すデータのことを「テキスト」と呼びます。また、機械語というものは単なるバイト列に過ぎないわけで、テキストもデータの一種なのですが、「テキストとデータ」というときは、「データ」は「テキスト以外のデータ」を指すことがほとんどです。この章でも、データというときはテキスト以外のデータを意味します。

リンカの入力になるオブジェクトファイルには、テキストとデータが別々に入っています。リンカは、複数のオブジェクトファイルから読んできたテキストを連結して1つのテキストセグメントに配置し、同様に複数のオブジェクトファイルから読んできたデータを連結して1つのデータセグメントに配置します。

実行ファイルのファイルヘッダには、セグメントごとに、実行時に置かれるべきメモリの番地が書かれています。実行ファイルを実行するとき、OSの「プログラムローダ」（program loader）あるいは単に「ローダ」と呼ばれるプログラムが、その情報に従って実行ファイルからメモリ上にテキストとデータをコピーしてきます。

実行ファイルと、その実行ファイルをローダがメモリに読み込んだ状態の図を以下に示します。

この図の実行ファイルでは、テキストセグメントを0x41000に、データセグメントを0x50000にロードするという情報がファイルのヘッダに書かれていたと仮定しました。

ファイルヘッダには、何番地から実行を開始するべきかという情報も入っています。例えば0x41040から実行を開始するべきという情報が書かれていた場合、ローダは実行ファイルを上の図のようにメモリにロードしてから、スタックポインタを0x7fff_ffff_ffff_ffffにセットし、そのあと0x41040にジャンプしてユーザプログラムの実行をスタートすることになります。

データセグメントの内容

テキストセグメントの内容は明らかに機械語ですが、データセグメントには何が入っているのでしょうか？ その答えですが、データセグメントにはグローバル変数やリテラルの文字列などが入っています。

ローカル変数は、テキストセグメントにもデータセグメントにも直接は入っていません。ローカル変数は、プログラムが動的にスタック領域に作り上げるものなので、メモリ上に実行ファイルをロードした直後には特に存在していません。

Cの実行モデルでは、プログラムというものは、実行ファイルをほぼそのままメモリ上に読み込むだけで、main関数の実行を始められるようになっています。したがって、グローバル変数というものは、実行ファイルのデータセグメントからメモリにコピーするだけで適切な初期値がセットされているようにしておく必要があります。

この制限により、Cでは例えば下のような関数呼び出しを使う初期化式をグローバル変数に対して使うことができません。

int foo = bar();

上記のような動的な初期化を必要とするグローバル変数があった場合、main関数を実行するより前に誰かが上記の式を実行する必要があります。しかしCにはmainより前に起動される初期化メカニズムが存在しないので、そのような初期化は行えないのです。

つまり、グローバル変数というものはリンク時に値が完成して、実行ファイルにそのままのバイト列として入れられるものでなければいけません。そのような値は次の式に限られます。

• 定数式
• グローバル変数や関数のアドレス
• グローバル変数や関数のアドレスに定数を足したもの

リテラルの数や文字列のような定数式がそのまま固定の値としてテキストセグメントに設定できるのは自明でしょう。

グローバル変数や関数のアドレスは、普通はコンパイル時には決まりませんが、リンカが実行ファイルを完成させる時には普通は決まります。従って、ポインタ型のグローバル変数の値を別のグローバル変数のアドレスで初期化するint *x = &y;のような定義は合法です。リンカは、プログラムのセグメントのレイアウトを自分で決めていて、関数やグローバル変数がロードされるアドレスも当然知っているので、xの内容をリンク時に埋められるというわけです。

また、ラベルのアドレスに定数を足すというのはリンカの機能でサポートされているので、int *x = &y + 3;のような定義も合法です。

上記のパターン以外の式を初期化式に書くことはできません。例えばグローバル変数の（アドレスではなく）値を初期化式で使うことはできません。ptrdiff_t x = &y - &z;のように2つのグローバル変数のアドレスの差を取る式は、原理的にはリンク時に値を求められる式ですが、そのような2つのラベルの差を計算する操作はリンカでサポートされていないので、そのような式を初期化式に書くことはできません。グローバル変数の初期化式というものは、あくまで上記の限られたパターンのみ許されています。

グローバル変数の初期化式として書ける式の例をCで表現すると次のようになります。

int a = 3;
char b[] = "foobar";
int *c = &a;
char *d = b + 3;

それぞれの式に対応するアセンブリは次のようになります。

a:
  .long 3
b:
  .byte 0x66 // 'f'
  .byte 0x6f // 'o'
  .byte 0x6f // 'o'
  .byte 0x62 // 'b'
  .byte 0x61 // 'a'
  .byte 0x72 // 'r'
  .byte 0    // '\0'
c:
  .quad a
d:
  .quad b + 3

連続する.byteは.asciiという記法を使って.ascii "foobar\0"のように書くこともできます。

初期化式の文法

初期化式は一見ただの代入式のように見えますが、実際は初期化式と代入式は文法的にかなり異なっていて、初期化式だけに許された特別な書き方というものがいくつかあります。ここでその特別な書き方をきちんと把握しておきましょう。

まず初期化式では配列を初期化することができます。たとえば次の式は、x[0]、x[1]、x[2]がそれぞれ0、1、2になるようにxを初期化しています。

int x[3] = {0, 1, 2};

初期化式が与えられている場合、配列の長さは右辺の要素の数を見ればわかるので、配列の長さを省略することができます。例えば上の式と下の式は同じ意味になります。

int x[] = {0, 1, 2};

配列の長さが明示的に与えられていて、初期化式が一部分だけ与えらている場合、残りの要素は0で初期化しなければいけません。従って次の2つの式は同じ意味になります。

int x[5] = {1, 2, 3, 0, 0};
int x[5] = {1, 2, 3};

また、charの配列の初期化式だけの特別な文法として、リテラルの文字列を初期化式として使う次のような書き方が許されています。

char msg[] = "foo";

上記の式は次の式と同じ意味です。

char msg[4] = {'f', 'o', 'o', '\0'};

グローバル変数の初期化式

グローバル変数の初期化式は、コンパイル時に計算する必要があります。計算結果は、単なるバイト列か、関数やグローバル変数のポインタのどちらかです。ポインタの場合、そのポインタのオフセットを表す整数を1つ持つことができます。

初期化式がまったく与えられていないグローバル変数は、全ビットが0になるように初期化する必要があります。これはCの文法でそう決まっています。

初期化式が上記の計算結果にならない場合はコンパイルエラーとして扱ってください。

ローカル変数の初期化式

ローカル変数の初期化式は、グローバル変数の初期化式と見た目は同じですが、意味は大きく異なります。ローカル変数の初期化式というものは、その場で実行される式です。したがって、その内容はコンパイル時に決まっている必要はありません。

基本的に、int x = 5;といった文は、int x; x = 5;というように2つの文に分けて書いたのと同じようにコンパイルされます。

int x[] = {1, 2, foo()};のような文は、次の文と同じようにコンパイルされます。

int x[3];
x[0] = 1;
x[1] = 2;
x[2] = foo();

初期化式がまったく与えられていないローカル変数の内容は不定です。したがってそのような変数は初期化する必要がありません。

ステップ29以降: [要加筆]

ダイナミックリンク

本書はここまでにスタティックリンクという機能だけを利用してきました。スタティックリンクというのは素直な実行モデルなので、そのモデルにフォーカスして説明を行うことにより、アセンブリコードや実行ファイルのメモリイメージなどをわかりやすく解説することができたのですが、実は一般的な実行ファイルを作成するときはスタティックリンクというのはそれほど広く使われていません。実際には、スタティックリンクではなくダイナミックリンクという機能が広く使われています。

この章ではダイナミックリンクについて説明します。

デフォルトではコンパイラやリンカはダイナミックリンクを行う実行ファイルを出力しようとします。読者のみなさんも、ここまでにccに-staticオプションを付け忘れると、次のようなエラーが出るのを見たことがあるかと思います（見たことがなければ、-staticオプションをMakefileから取り除いた上でmakeを実行してみてください）。

$ cc -o tmp tmp.s
/usr/bin/ld: /tmp/ccaRuuub.o: relocation R_X86_64_32S against `.data' can not be used when making a PIE object; recompile with -fPIC
/usr/bin/ld: final link failed: Nonrepresentable section on output

リンカはデフォルトでダイナミックリンクしようとしますが、ダイナミックリンクするためにはそうすることが可能なアセンブリコードをコンパイラから出力しなければいけません。9ccは今のところそのようなコードを出力しないので、-staticを付け忘れると上のようなエラーが表示されます。この章を読むことにより、上記のエラーの意味がわかるようになり、エラーを解決するために何をしなければいけないのかがわかるようになるはずです。

スタティックリンクとダイナミックリンク

スタティックリンクされた実行ファイルは、実行時に他のファイルを必要としない、自己完結した実行ファイルです。例えばprintfなどの関数は、ユーザが書いた関数ではなくlibc標準ライブラリに入っている関数ですが、スタティックリンクで実行ファイルを作成すると、printfのコードがlibcから実行ファイルにコピーされることになります。スタティックリンクされたプログラムを実行するときはlibcは必要ありません。なぜならlibcの中の必要なコードやデータは、すでに実行ファイルにコピーされているからです。

スタティックリンクされた実行ファイルの実行モデルは単純です。実行時にはメモリ上にはその実行ファイルしか存在しないので、実行ファイルの各セグメントはメモリ上の任意の位置にロードすることができます。リンク時に決まっているデフォルトのアドレスにロードしようとしたときに、ロードが失敗することはありません。実行ファイルがロードされる前にはメモリ上には何も置かれていないからです。従って、スタティックリンクでは、すべてのグローバル変数や関数のアドレスはリンク時に決めることができます。

スタティックリンクには以下の利点があります。

• 単純でロードが速い
• 依存しているファイルがないので、実行ファイルをコピーするだけで動作する
• 微妙に動作の異なるバージョン違いのライブラリがあったとしても、スタティックリンクでコピーされるときにライブラリのコードとデータは固定されるので、どの環境でも同じ実行ファイルが同じように動作する

スタティックリンクには以下の欠点があります。

• 実行ファイルが使っているライブラリ関数やコードがコピーされるので、ディスクやメモリが多少無駄になる
• ライブラリのバグが修正された場合、既存の実行ファイルにその変更を反映するためには再リンクが必要になる

一方、ダイナミックリンクされた実行ファイルは、実行時に他の.so（Unixの場合）や.dll（Windowsの場合）といったファイルを必要とします。.soや.dllにはprintfなどの関数のコードやerrnoのようなグローバル変数が入っています。.soや.dllなどのファイルは、動的ライブラリや単にライブラリ、あるいはDSO（dynamic shared object）と呼ばれます。

Cの型の構文

Cの型の構文は不必要に複雑なことでよく知られています。Cの開発者Dennis Ritchieが共著者の書籍「プログラミング言語C」（通称「K&R」）にも「C言語の宣言の構文、特に関数へのポインタが関係する宣言の構文は、酷評されることがあります」と書いてあります⁷。

このようにCの型の構文は、作者ですら暗に認めているような良くない設計なのですが、そうはいってもこの構文はルールさえ理解してしまえばそう難しいものでもありません。

この章ではCの型の構文の読み方を説明します。ステップ・バイ・ステップで理解を深めていくことにより、この章が終わる頃には、読者のみなさんはvoid (*x)(int)やvoid (*signal(int, void (*)(int)))(int)といった複雑な型を解読できるようになるはずです。

型を表す図

Cで表現可能な型そのものは比較的単純です。型の構文の複雑さと、型そのものの複雑さを分けて考えるために、構文はいったん横に置いておいて、型のことだけを考えてみましょう。

ポインタや配列といった複雑な型は、単純な型を矢印で繋いだ図で表現することができます。例えば次の図は、「intへのポインタのポインタ」を表している型の図です。

日本語では矢印の終点から始点に向かって「intのポインタのポインタ」と読み上げることになります。英語では逆にa pointer to a pointer to an intと矢印の向きに沿って読み上げることになります。

変数xが上記の図の型を持っているとしましょう。「xの型は何か？」という質問に対する最も簡潔な答えは「ポインタです」ということになります。最初の矢印が指している型はポインタ型だからです。xはまずはポインタなのであって、intなどの型ではないことに注意してください。「そのポインタが指している型は何か？」という質問にも「ポインタです」と答えることになります。矢印を1つ辿ったところにあるのもポインタ型だからです。最後に「そのポインタが指している型は何か？」という質問には「intです」と答えることになります。

次の図は「intへのポインタの配列」を表しています。配列の長さは20です。実際のコンパイラでも、配列の長さは、下の図のように配列を表す型のメンバとして表現されます。

変数xが上記の図の型を持っている場合、xは長さ20の配列型で、その配列の要素はポインタで、そのポインタが指しているのはintということになります。

関数の型も図で表すことができます。次の図は、intとintへのポインタの2つを引数に取って、voidへのポインタを返す関数の型を表しています。

最後にもっと複雑な例を挙げてみましょう。次の図は、intを引数に取って、intを返す関数へのポインタを返す関数へのポインタという型を表しています。言葉にすると複雑ですが、図にすると単に長いだけで、構造としては単純なことがわかると思います。

変数xが上記の図の型を持っている場合、xはポインタ型で、そのポインタが指しているのは関数で、その関数の引数の型はintで、返り値の型はポインタ型で、そのポインタが指しているのは関数で、その関数の返り値の型はintということになります。

コンパイラの内部では、上記の図と同じ方法を使って型を表しています。つまり、ポインタや配列、関数が関連する複雑な型は、コンパイラ内部では上記の図と同じ順番で、単純な型の構造体をポインタで繋いだデータ構造として表現されています。したがってこの図こそが型の真の姿と言っても過言ではないでしょう。

型を表す記法

上記のように図で表すと型の意味はわかりやすくなりますが、型を理解するために毎回図を書くのは面倒です。この節では、図のわかりやすさを損なわずに、もっとコンパクトに書ける記法について考えてみましょう。

関数型が含まれていない限り、図の中で、全ての箱は枝分かれなしに数珠つなぎに配置されることになります。したがって、ポインタや配列しかない型であれば、図の中にある型の名前をそのまま左から右に書いていくことで、図を文字で表現することができるはずです。

具体的な表記について考えてみましょう。ポインタを表す箱は*という記号で表すことにします。また、長さnの配列を表す箱は[n]、intなどの組み込みの型を表す箱は型の名前を書くというルールにしましょう。そうすると、以下の図は、* * intという文字列で表すことができます。

矢印の始点から順番にポインタ、ポインタ、intが登場しているので、* * intという表記になるというわけです。逆に* * intという表記が与えられた場合に、上の図を描くこともできます。つまりこのテキスト表現は、図と同じ情報をコンパクトにテキストで書き下すことができる記法というわけです。

下の図は[20] * intという文字列で表現できます。

関数については、「func(引数の型, ...) 返り値の型」という書き方をすることにしましょう。例えば下の図で表される型はfunc(int, * int) * voidという表記になります。読者のみなさんもこの表記と図が一致していることを確認してみてください。

最後に、下の図が表している型は* func(int) * func() intです。

ここまでに説明した記法は、おそらく型のテキスト表現としてはもっとも素直で簡単なものです。実際、プログラミング言語Goの型の構文は、ここで説明した記法とまったく同じです。GoはCを作った人たちが開発に参加している言語ですが、GoではCの反省点を生かして、型の構文はさりげなく改良されているのです⁸。

Cの型の読み方

この節では、上記で学んだ型の記法とCの型の記法を付き合わせて、Cの型を読み解く方法を学んでいきましょう。

Cの型は、先頭から次の4つの部分に分解することができます。

1. ベースの型
2. ポインタを表すアスタリスク
3. 識別子か、カッコでくくられたネストした型
4. 関数や配列を表すカッコ

たとえばint xは、ベースの型はint、ポインタを表すアスタリスクはなし、識別子はx、関数や配列のカッコはなし、という構成になっています。unsigned int *x()は、ベースの型はunsigned int、ポインタを表すアスタリスクは*、識別子はx、関数を表すカッコは()という構成です。void **(*x)()は、ベースの型はvoid、ポインタを表すアスタリスクは**、ネストした型は*x、関数を表すカッコは()、という構成です。

ネストしていない型の読み方

ポインタの後に続くものがただの識別子の場合、型を解読するのは比較的簡単です。

関数や配列のカッコがない場合、型の表記とその意味は次のようになります。意味は上記で説明したGoと同じ記法で書くことにします。

関数のカッコがある場合、ベースの型とポインタを表すアスタリスクは、返り値の型を表すことになります。以下に例を示します。

関数のカッコがないものとしてパースしたときの型、すなわちint x、int *x、int **xの型が、func(...)の後ろに続いているだけというのがわかると思います。

同様に、配列のカッコがある場合、「〜の配列」という意味になります。以下に例を示します。

例えばint *x[5]という型の場合、xの型は長さ5の配列で、その配列の要素はポインタで、そのポインタが指しているのはintです。関数の場合と同じように、配列のカッコのない場合の型が[...]の後ろに続く構成になるということがわかると思います。

ネストしている型の読み方

ポインタの後に識別子ではなくカッコがある場合、そのカッコはネストした型を表しています。ネストした型がある場合、カッコの中の型と外の型を別々に構文解析して、後でそれを組み合わせることにより、全体の型を得ることができます。

例として、int (*x)()という宣言をパースしてみることにしましょう。

int (*x)()は、最初のカッコ全体を1つの識別子（ここでは適当にyとします）のように考えて型を解釈すると、int y()という見た目になるので、カッコの外の型はfunc() intということになります。一方、カッコの中の*xという型を考えてみると、これは* ___という型を表していることになります。カッコの中の型にはintなどのベースの型というものが書かれていないので、型としては完全ではないのですが、ここでは欠けているベースの部分を___という表記で表すことにしました。

int (*x)()という型を、カッコの中と外を別々にパースすることで、2つの型func() intと* ___を得ることができました。全体としての型は、内側の型の欠けている部分___に外側の型をはめ込むとできあがります。この場合、* func() intが全体としての型になります。つまりint (*x)()という宣言では、xはポインタで、そのポインタが指している型は関数で、その関数の返り値はintということになります。

もう一つ例を挙げてみましょう。void (*x[20])(int)は、最初のカッコを識別子とみなして考えると、void y(int)と同じパターンになるので、カッコの外はfunc(int) voidという型を表しています。カッコの中の*x[20]は[20] * ___を表しています。この2つを組み合わせると[20] * func(int) voidになります。つまり、xは長さ20の配列型で、その要素の型はポインタで、そのポインタが指しているのはintを取る関数で、その関数が返す型はvoidということになります。

ここで説明した方法を使うと、どのような複雑な型でも読むことができます。一つ極端な例として、Unixのsignal関数の型を読んでみることにしましょう。signal関数は一見なんなのかまったくわからない型で有名な関数です。以下にsignal関数の宣言を示します。

void (*signal(int, void (*)(int)))(int);

このような複雑な型も、分解して読んでいくことで解読することが可能です。まずは最初のカッコの中と外を分けて考えることにしましょう。最初のカッコを識別子とみなして型を考えると、void y(int)と同じパターンになるので、カッコの外側はfunc(int) voidという型を表していることになります。

カッコの中は*signal(int, void (*)(int))という型です。これはベースの型がなし、ポインタを表すアスタリスクが*、識別子がsignal、関数を表すカッコが1組あって2つの引数が書かれている、という構成です。従って大まかな型としてはfunc(引数1, 引数2) * ___になります。引数の型について考えてみると次のようになります。

• 第一引数はintです。その型は単にintです。
• 第二引数はvoid (*)(int)です。これはベースの型がvoid、カッコでくくられたネストした型が*、関数を表すカッコが1組、という構成なので、最初のカッコを識別子とみなした場合の型はfunc(int) voidです。カッコの中の*について考えてみると、ポインタを表すアスタリスクが1つあるので、その型は* ___です。結局のところ、第二引数の型はそれらの型が組み合わさった* func(int) voidということになります。

上記の引数の型をfuncの引数の部分に入れると、func(int, * func(int) void) ___という型になります。最後にそのカッコの中の型をカッコの外の型と組みわせると、最終的な結果であるfunc(int, * func(int) void) * func(int) voidという型になります。

つまり、signalは関数で、その関数は次の2つの引数を取ります。

1. int
2. intを取ってvoidを返す関数へのポインタ

signalの返り値の型はポインタで、そのポインタはintを取ってvoidを返す関数を指しています。

練習問題

おわりに

本書の本文はMarkdown形式で記述しました。MarkdownからHTMLへの変換にはPandoc、構文木の図の作成にはGraphviz、そのほかの図の作成にはdraw.ioを使用しました。

付録1：x86-64命令セット チートシート

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

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

整数レジスタの一覧

64ビット整数レジスタの一覧とそのエイリアスの名前を表にまとめました。

ABIにおける使い方は次の通りです。関数から戻る際に元の値に戻さなくてよいレジスタには✔をつけました。

関数呼び出しを行うと きは、RSPが16の倍数になっている（16にアラインされている）状態でcall命令を呼ぶ必要があります。この条件を満たさない関数呼び出しはABIに準拠しておらず、一部の関数がクラッシュすることがあります。

メモリアクセス

関数呼び出し

条件分岐

条件代入

整数・論理演算

付録2：Gitによるバージョン管理

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

• git add ファイル名

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

• git commit -A

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

• git reset --hard

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

• git log -p

  過去のコミットを見る

• git push

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

Gitを使ったワークフロー

バージョン管理システムを初めて使う人のために、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なファイルシステムを常に念頭に置いてみてください。きっといろいろなことがわかりやすくなるはずです。

付録3：Dockerを使った開発環境の作成

この付録では、Dockerを使って、macOS上でLinuxアプリケーションをビルドして実行する方法を説明します。

DockerはLinuxの仮想環境を提供するソフトウェアです。フル機能のVMでは、PCのハードウェアがエミュレートされてその上で通常のOSが動作するのに対して、Dockerでは、Linuxのシステムコール（だけ）が仮想環境内に対して直接提供されるという違いがあります。この違いにより、フル機能の仮想化と比較して、Dockerは起動が速く全体的に軽量という利点があります。Dockerはクラウドのコンピュータに対してアプリケーションをデプロイするときなどによく使われています。

Dockerを使ってmacOS上でLinuxアプリケーションを開発する場合、次の2つのシステム構成を考えることができます。

1. Dockerの中の環境と外の環境を全く別のものとして考えて、Linuxのアプリケーションを開発するときは、すべての作業をDockerの中で行う構成
2. ソースコードの編集やgitの操作など、プラットフォームに依存しない通常の開発作業はDockerの外で行い、ビルドやテストのコマンドのみDockerの中で実行する構成

前者の構成では、Macとは別にLinuxマシンを用意して開発を行うのと同じなので構成が単純ですが、Linux上での開発環境をエディタなども含めて用意しないといけないので、セットアップがやや煩雑です。一方で後者の構成では、Dockerの中で「暮らす」わけではないので環境のセットアップは凝る必要がありませんが、Dockerの中と外を使い分けるのがやや面倒です。

上記の2つの構成はどちらを選んでも構いませんが、本書では、Linux環境のセットアップ手順を説明することを避けるために、後者の構成を選択することにします。したがって、Linux環境の中で走らせたいコマンドだけを明示的にDockerの中で実行することになります。

セットアップ手順

Dockerを使ったLinux開発環境をセットアップするためには、まずDocker Desktop for Macをダウンロードしてインストールしてください。その後、次のコマンドを実行すると、compilerbookという名前のDockerイメージを作成することができます。

$ docker build -t compilerbook https://www.sigbus.info/compilerbook/Dockerfile

「Dockerイメージ」あるいは「イメージ」とは、Linux環境に必要なすべてのファイルと設定をまとめたものです。Dockerイメージを実際に起動したものは「Dockerコンテナ」あるいは単に「コンテナ」と呼ばれます（実行ファイルとプロセスの関係と同じです）。

コンテナを作成してその中でコマンドを実行するためには、docker runコマンドの引数としてイメージ名とコマンドを与えてください。以下はls /コマンドをcompilerbookのコンテナの中で実行する例です。

$ docker run --rm compilerbook ls /
bin
root
dev
etc
...

コンテナはバックグラウンドで動作し続けるようにすることも可能ですが、我々の使い方ではインタラクティブな使い方しか必要ないので、--rmオプションを与えることで、コマンドが終了し次第コンテナも終了するようにしました。従って、上記のコマンドを入力するたびにコンテナが作成されて破棄されることになります。

コンテナを使ったビルド

コンテナの中でmakeを実行してソースファイルをコンパイルするためには、Dockerの外で編集しているソースファイルをコンテナから見えるようにする必要があります。

docker runでは、-v <source>:<dest>という形式のオプションを与えることで、外側の環境のパス<source>を、Dockerの中で<dest>として見えるようにすることができます。また、コマンドを実行するときのカレントディレクトリを-wオプションで指定することができます。これらのオプションを使うと、ソースファイルのあるディレクトリをカレントディレクトリにした上でmakeを実行することができます。

ホームディレクトリの9ccというサブディレクトリにソースファイルが置いてあるものとしましょう。そのディレクトリに対してコンテナ内からmake testを実行するためには、次のコマンドを実行してください。

$ docker run --rm -v $HOME/9cc:/9cc -w /9cc compilerbook make test

ビルドやテストのコマンドは、上記のようにして実行するようにしてください。

コンテナ内でシェルを起動してインタラクティブに使いたい場合は、以下のように-itオプションをつけてdocker runを実行してください。

$ docker run --rm -it -v $HOME/9cc:/9cc compilerbook

コンテナに新たなアプリケーションを追加

上記の手順で作成したDockerコンテナには一通りの開発ツールがインストールされていますが、追加のアプリケーションをインストールしたいこともあるでしょう。ここではその方法を説明します。

Dockerコンテナはテンポラリな存在です。コンテナを作ってその中のシェルからアプリケーションをインストールしても、そういった変更は元のイメージには書き戻されません。Dockerはこの性質によって、毎回アプリケーションが同じフレッシュな状態から起動することを保証しているのですが、イメージに変更を加えたいときはこの性質が仇となります。

コンテナに変更を加えた後それをイメージに書き戻したい場合は、明示的にdocker commitコマンドを実行する必要があります。

例として、curlコマンドをインストールしたいとしましょう。その場合、まずは次のようにコンテナを作成します。

$ docker run -it compilerbook

--rmオプションを渡していないことに注意してください。その後、次のようにコンテナの中のシェルからaptを使ってcurlをインストールして、exitコマンドでコンテナから抜けます。

$ sudo apt update
$ sudo apt install -y curl
$ exit

docker runを実行するときに--rmオプションをつけなかったので、コンテナのシェルからexitした後でもコンテナはサスペンド状態として残っています。docker container ls -aコマンドを使うと、次のようにサスペンドしたコンテナを表示することができます。

$ docker container ls -a
CONTAINER ID        IMAGE               COMMAND             CREATED             STATUS                     PORTS               NAMES
a377e570d1da        compilerbook        "/bin/bash"         7 seconds ago       Exited (0) 5 seconds ago                       pedantic_noyce

compilerbookというイメージを実行したa377e570d1daというIDのコンテナがあることがわかるはずです。docker commitコマンドを使うと、コンテナをイメージに書き戻すことができます。

$ docker commit a377e570d1da compilerbook

上記の手順で、イメージに変更を加えることができます。

サスペンドしたコンテナや古いイメージなどは、残っていても多少ディスクスペースを消費するだけで特に問題はありませんが、気になる場合はdocker system pruneを実行することにより削除することができます。

参考資料

• Compiler Explorer: 便利なオンラインコンパイラ
• N1570 [PDF]: C11言語仕様の最終ドラフト（公式の規格書と内容は同一）
• N1570: HTML版のC11言語仕様
• X4J11/86-196 [PDF]: Cプリプロセッサのマクロ展開アルゴリズムの解説
• Rationale for American National Standard for Information Systems - Programming Language - C: 標準化委員会がどのようなことを考慮してC89言語仕様を決めたのかを説明している文章
• 8cc: 筆者によるCコンパイラ
• 9cc: 筆者によるCコンパイラ
• Cコンパイラをスクラッチから開発してみた（日記）
• An Incremental Approach to Compiler Construction [PDF]: インクリメンタルなコンパイラ開発のアイデアを得た論文
• Crafting Interpreters: Robert Nystromさんによるオンラインブック
• A Retargetable C Compiler: Design and Implementation. David R. Hanson and Christopher W. Fraser: シンプルなCコンパイラlccの実装の解説書

索引