低レイヤを知りたい人のためのCコンパイラ作成入門

Rui Ueyama <ruiu@cs.stanford.edu>

2019-05-23


はじめに

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

なぜC言語なのか

数多くあるプログラミング言語の中で、この本ではなぜCを選んだのでしょうか? あるいはなぜ自作言語ではないのでしょうか? この点については、絶対にCでなければならない理由はないのですが、ネイティブコードを出力するコンパイラの制作手法を学ぶために何らかの言語を選ばなければいけないとしたら、Cはさほど多くないリーズナブルな選択肢のうちの一つだと思います。

インタプリタ方式の言語では低レイヤについて学ぶことができません。一方でCでは普通はアセンブリにコンパイルするので、C言語そのものと同時に、CPUの命令セットやメモリレイアウトなどについて学ぶことができます。

Cは広く使われているので、コンパイラがきちんと動くようになったら、ネットからダウンロードしてきた第三者のソースコードをコンパイルして遊ぶことができます。例えばミニUnixのxv6をビルドして遊ぶことができるでしょう。コンパイラの完成度が十分に高ければ、Linuxカーネルすらコンパイルすることが可能なはずです。こういった楽しみ方はマイナーな言語や自作言語ではできません。

Cのようなネイティブな機械語にコンパイルされる静的型付け言語で、Cと少なくとも同じくらい広く使われているものとして、C++があります。しかしC++は、言語仕様があまりにも巨大で、気軽に自作コンパイラを作るというのは不可能で、現実的に選択肢に入りません。

オリジナルの言語をデザインして実装するのは、言語のデザインセンスを磨くという意味ではよいのですが、落とし穴もあります。実装が面倒なところは、言語仕様でそれを避けることにより実装しないで済ませてしまうことができるのです。言語仕様が標準として与えられているCのような言語ではそうはいきません。その縛りは学習という意味ではわりとよいものだと思います。

本書の表記法

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

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

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 install gcc make git binutils libc6-dev

macOSはLinuxとアセンブリのソースレベルでかなり互換性がありますが、完全互換ではありません。この本の内容に従ってmacOS対応のCコンパイラを作成するのは不可能ではないものの、実際に試してみると、細かな点でいろいろな非互換性に悩まされることになるでしょう。Cコンパイラ作成のテクニックと、macOSとLinuxの差異を同時に学ぶというのは、あまりお勧めできることではありません。何かがうまく動かない場合、どちらの理解が間違っているのかよくわからなくなってしまうからです。したがって現時点では、本書ではmacOSは対象外とします。macOSではDockerなどを使ってLinux環境を用意するようにしてください。

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

クロスコンパイラ

コンパイラが動作するマシンのことを「ホスト」、コンパイラが出力したコードが動作するマシンのことを「ターゲット」といいます。本書ではどちらも64ビットのLinux環境ですが、ホストとターゲットは必ずしも同じである必要はありません。

ホストとターゲットが異なるコンパイラのことをクロスコンパイラといいます。たとえばRaspberry Piの実行ファイルを生成するWindowsで動くコンパイラはクロスコンパイラです。クロスコンパイラは、ターゲットのマシンがコンパイラを動かすには貧弱だったり特殊だったりするときによく使われます。

著者について

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

コンパイラをコンパイルするコンパイラ

CコンパイラがCで書かれているといった自己参照的な状況は珍しくありません。C以外でも、数多くの言語実装がその言語自体を使って書かれています。

すでに言語Xの実装がある場合、その言語自身を使って新たなXコンパイラを作ることに論理的な矛盾はありません。セルフホストするためには、単に既存のコンパイラで開発を進めていって、自作のものが完成したらスイッチすればよいだけです。この本で我々が行おうとしているのはまさにその方法です。

しかし既存のコンパイラがない場合はどうすればよいのでしょうか? そのときには別の言語を使って書くしかありません。セルフホストを目的としてX言語の最初のコンパイラを書くときには、Xと異なる既存のY言語を使って書き、コンパイラの完成度が高まったところで、コンパイラ自身をY言語からX言語に書き直す必要があります。

現代の複雑なプログラミング言語のコンパイラも、その言語の実装をコンパイルするために使った別のコンパイラ、というように系譜をさかのぼっていくと、最終的に、コンピュータの黎明期に誰かが機械語で直接書いた単純なアセンブラにたどりつくはずです。現存するすべての言語実装のある意味の究極の祖先にあたるそのアセンブラが、単一なのか複数あったのかはわかりませんが、現在のコンパイラがごく少数の祖先から出発しているのは間違いないでしょう。コンパイラ以外の実行ファイルも普通はコンパイラが生成したファイルですから、現存するほぼすべての実行ファイルは、その原始のアセンブラの間接的な子孫にあたるわけです。これは生命の起源のような面白い話ですね。


機械語とアセンブラ

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

CPUとメモリ

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

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

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

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

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

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

x86-64命令セットの名称

x86-64は、AMD64やIntel 64、x64などと呼ばれることもあります。同一の命令セットにこのように複数の名前がついているのには歴史的背景があります。

x86命令セットは1978年にIntelが作ったものですが、それを64ビットに拡張したのはAMDです。64ビットプロセッサが必要になりつつあった2000年頃、IntelはItaniumというまったく新しい命令セットに全社を挙げて取り組んでいて、それと競合することになる64ビット版x86にはあえて取り組んでいませんでした。その隙を突いてAMDが64ビット版x86の仕様を策定して公開しました。それがx86-64です。そのあとAMDはブランディング戦略の都合上か、x86-64をAMD64と改名しました。

その後Itaniumの失敗が明白になり、Intelは64ビット版x86を作ることしか選択肢がなくなってしまったのですが、そのころにはAMD64の実際のチップがそれなりに数が出ていたので、それと似て非なる拡張命令セットをいまさら策定するのも難しく、IntelもAMD互換の命令セットを採用することになりました。Microsoftからも互換性維持のプレッシャーがあったと言われています。そのときにIntelは、AMD64とほぼ全く同じ命令セットにIA-32eという名前をつけて採用しています。64ではなくIA-32e (Intel Architecture 32 extensions) という名前をつけたことには、64ビットCPUの本丸はあくまでItaniumであるという、失敗した命令セットに対する未練が透けて見えるようです。そのあとIntelはItaniumを完全に見捨てる方針を取るようになり、IA-32eはIntel 64という普通の名前に改名されました。Microsoftは長すぎる名前を嫌ってか、x86-64のことをx64と呼んでいます。

上記のような理由で、x86-64はたくさんの異なる名前を持っているのです。

オープンソースプロジェクトでは、特定の会社の名前が入っていないx86-64という名称が好まれることが多いようです。本書でもx86-64という名称を一貫して使っています。

アセンブラとは

機械語は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コンパイラが出力するアセンブリコードを少し見てみましょう。最も簡単な例として次のプログラムを考えてみます。

int main() {
  return 42;
}

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

$ gcc -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に記述して、次のコマンドを実行してみてください。

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

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

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

関数呼び出しを含む例

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

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

スタックは、スタックの一番上のアドレスを保持する1つの変数のみを使って実装することができます。そのスタックトップを保持している記憶領域のことを「スタックポインタ」といいます。x86-64は、関数を使ったプログラミングをサポートするために、スタックポインタ専用のレジスタと、そのレジスタを利用する命令をサポートしています。スタックにデータを積むことを「プッシュ」、スタックに積まれたデータを取り出すことを「ポップ」といいます。

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

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

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

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

.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から始まる行は、plusmainという2つの関数がファイルスコープではなくプログラム全体から見える関数だということをアセンブリに指示しています。これはさしあたり無視してかまいません。

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

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が行うのは次のことです。

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

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

本章のまとめ

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

まだ本書では具体的なCPU命令についてほとんど説明していないので、objdumpで表示されたアセンブリコードの個別の命令の意味はわからないと思いますが、1つ1つの命令は大したことをしていないということが、想像できると思います。本章の段階ではそういう感覚が掴めるだけで十分です。

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

オンライン・コンパイラ

Cコードとそのコンパイル結果を眺めてみるのはアセンブリ言語を覚えるためのよい方法ですが、何度もソースコードを編集してコンパイルし、その出力のアセンブリを確認するのは、意外と面倒なものです。その手間を削減できる大変良いウェブサイトがあります。それがCompiler Explorer(通称godbolt)です。Compiler Explorerで画面の左半分のテキストボックスにコードを入力すると、右半分にそれに対応するアセンブリ出力がリアルタイムに表示されます。Cコードがどのようなアセンブリに変換されるのか確認したいときはこのサイトを使うのがよいでしょう。


電卓レベルの言語の作成

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

30 + (4 - 2) * -5

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

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

この章では、構文解析の最も一般的なアルゴリズムの一つである「再帰下降構文解析法」(recursive descendent 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のリポジトリも含め、名前は後から変えられるので、適当な名前で始めて問題ありません。

Intel記法とAT&T記法

本書で使用しているIntel記法の他に、AT&T記法というアセンブラの記法もUnixを中心に広く使われています。gccやobjdumpはデフォルトではAT&T記法でアセンブリを出力します。

AT&T記法では結果レジスタが第2引数に来ます。したがって2引数の命令では引数を逆順に書くことになります。レジスタ名には%プレフィックスをつけて%raxというように書きます。数値には$プレフィックスをつけて$42というように記述します。

また、メモリを参照する場合、[]の代わりに()を使って、独特の記法で式を記述します。以下にいくつか対比のために例を示します。

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

今回作るコンパイラでは読みやすさを考慮してIntel記法を使うことにしました。Intelの命令セットマニュアルではIntel記法が使われているので、マニュアルの記述をそのままコードに書けるという利点もあります。表現力はAT&T記法もIntel記法も同じです。どちらの記法を使っても、生成される機械語命令列は同一です。

コンパイラ本体の作成

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

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

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

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

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

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

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

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

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

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

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

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

ユニットテストの作成

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

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

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

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

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

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

try 0 0
try 42 42

echo OK

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

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

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

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

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

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

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

makeによるビルド

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

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

9cc: 9cc.c

test: 9cc
        ./test.sh

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

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

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

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

gitによるバージョン管理

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

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

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

*~
*.o
tmp*
9cc

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

$ git config --global user.name "Rui Ueyama"
$ git config --global user.email "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コンパイラに育て上げることになります。まずは最初のステップが完成したことを味わってください。

コンピュータの記憶階層と経済性

プログラムを書いていると、ストレージについて、あらゆるところにサイズと速度のトレードオフがあることに気がつくと思います。レジスタは数百バイトしかないストレージですが、ディレイなしでCPUの内部からアクセスできます。DRAMから構成されるメインメモリでは、CPUからのアクセスに100クロック以上かかりますが、数GiBというサイズを確保することができます。レジスタとDRAMの間にはCPUのチップ内に実装されたキャッシュがあり、L1、L2、L3という階層ごとに、小さくて速いメモリから、比較的大きくて遅いメモリまでが用意されています。

このようなストレージの速度と容量のトレードオフはCPUやメインメモリに限りません。SSDはDRAMより大容量で1000倍くらい遅いストレージです。HDDはSSDより大きくてより遅いストレージです。DropboxやGoogle Driveのようなインターネットのストレージは、HDDよりもずっと大きくなることができて、そしてアクセスにはさらに時間がかかります。

なぜストレージには、速いものは容量が小さくて、遅いものは容量が大きいという一般的な法則があるのでしょうか?

一つの理由は、ストレージの種類によっては、容量と速度がトレードオフの関係にあることです。例えばレジスタは増やせば増やすほど良さそうですが、レジスタを増やすと回路規模が増大して、他の機能につかえるシリコンが減ってしまします。また、レジスタの数を増やした分だけ命令セットのレジスタを指定するビットの幅も増やさなければならないので、命令が長くなり、命令キャッシュの利用効率が悪くなります。レジスタを増やすことによる速度向上はある程度以上ではほとんど効果がなくなるので、多ければよいというものでもありません。

SSDやHDDのような外部ストレージについては、実際に、速くて容量が大きいストレージや、遅くて容量が小さいストレージというものは存在します。ただし、速くて大容量のストレージが登場すると、それより劣るテクノロジは市場から駆逐されてしまいますし、同様に遅くて小容量のストレージは作る意味がないので、市場に出回っているテクノロジには、小容量で速いものと、大容量で遅いものしか存在していないのです。コンピュータの博物館にいくと、コアメモリや水銀遅延菅といった、現在主流のメモリ技術と比べると小容量で低速なメモリの実物を見ることができます。

最も速くて最も大容量の不揮発性のストレージがあれば、それが究極の単一のメモリ技術になり得ますが、残念ながらそういったデバイスは今のところ存在しません。すべての評価基準において最高の性能特性を持つメモリ技術が開発されない限り、デコボコの性能特性を持ったストレージシステムをうまく階層化してコンピュータを構成していくのは、技術の選択としては自然な成り行きなのです。

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

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

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

.intel_syntax noprefix
.global main

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

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

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

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

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

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

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

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

  char *p = argv[1];

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

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

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

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

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

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

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

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

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

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

try 21 '5+20-4'

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

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

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

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

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

$ ./9cc '5 - 3' > tmp.s
予期しない文字です: ' '

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

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

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

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

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

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

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

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

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

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

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

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

// エラー箇所を報告するための関数
void error_at(char *loc, char *msg) {
  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // pos個の空白を出力
  fprintf(stderr, "^ %s\n", msg);
  exit(1);
}

// user_inputが指している文字列を
// トークンに分割してtokensに保存する
void tokenize() {
  char *p = user_input;

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

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

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

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

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

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

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

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

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

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

    if (tokens[i].ty == '-') {
      i++;
      if (tokens[i].ty != TK_NUM)
        error_at(tokens[i].input, "数ではありません");
      printf("  sub rax, %d\n", tokens[i].val);
      i++;
      continue;
    }

    error_at(tokens[i].input, "予期しないトークンです");
  }

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

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

上記のコードのerror_atは、入力のエラーを報告するための関数です。error_atが受け取るポインタは、入力全体を表す文字列の途中を指しているポインタです。そのポインタと、入力の先頭を指しているポインタとの差を取ると、エラーのある場所が入力の何バイト目かわかるので、その場所を目立つように^でマークすることができます。以下にエラーの出力例を示します。

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

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

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

try 41 " 12 + 34 - 5 "

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

ソースコードのフォーマッタ

日本語でも句読点など正書法のレベルで誤りの多い文章が読むに耐えないのと同じように、ソースコードも、インデントがおかしかったり空白の有無などが一貫していなかったりすると、ソースコードの中身以前のレベルできれいなコードとは言えません。コードのフォーマッティングといったいわばどうでもいい部分では、機械的に一定のルールを適用して、気が散らずに読めるコードを書くように気をつけてください。

複数人で開発するときにはどういったフォーマットにするか相談して決めなければいけませんが、この本では一人で開発しているので、ある程度メジャーなフォーマットのなかから自分で好きなフォーマットを選んで構いません。

最近開発された言語では、どういうフォーマットを選ぶかという、好みはわかれるけど本質的ではない議論の必要性そのものをなくすために、言語公式のフォーマッタを提供しているものがあります。たとえばGo言語ではgofmtというコマンドがあり、それを使うとソースコードをきれいに整形してくれます。gofmtはフォーマットのスタイルを選ぶためのオプションがなく、いわば唯一の「Go公式のフォーマット」にしか整形することができません。あえて選択肢を与えないことにより、フォーマットをどうするかという問題をGoは完全に解決しているわけです。

CやC++ではclang-formatというフォーマッタがありますが、本書では特にこういったツールを使うことを推奨したいわけではありません。フォーマットのおかしなコードを書いて後から整形するのではなく、最初から一貫した見た目のコードを書くように気をつけてみてください。

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

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

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

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

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

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

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

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

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

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

1*(2+3)を表す木
1*(2+3)を表す木

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

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

7-3-3を表す木
7-3-3を表す木

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

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

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

1*2+3*4*5を表す木
1*2+3*4*5を表す木

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

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

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

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

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

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

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

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

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

チョムスキーの生成文法

生成文法というアイデアを考え付いたのは、ノーム・チョムスキーという言語学者です。彼のアイデアは言語学やコンピュータサイエンスに非常に大きな影響を与えました。

チョムスキーの仮説によると、ヒトが言葉を話せる理由は、ヒトには生まれつき、生成規則を獲得するための専用の回路が脳に存在しているからだとされています。人間には再帰的な言語のルールの獲得能力があるために、言語を話せるようになるというわけです。ヒト以外の動物には言語獲得能力はありませんが、彼は、それは生成規則を獲得するための回路がヒト以外の動物の脳に存在しないためだと考えました。チョムスキーの主張は、仮説が発表されてから60年近くがたったいまでも立証も反証もされていませんが、現在でもかなり説得力があるものと考えられています。

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* Aの0回以上の繰り返し
A? Aまたはε
A | B AまたはB
( ... ) グループ化

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

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

BNFとEBNF

Extendedではない普通のBNFには、*?|( ... )といった簡潔な記法が存在していませんが、BNFで生成可能な文とEBNFで生成可能な文は同じです。なぜなら、以下のように書き換えることで、EBNFをBNFに変換することができるからです。

EBNF 対応するBNF
A = α* A = αAA = ε
A = α? A = αA = ε
A = α | β A = αA = β
A = α (β₁β₂⋯) γ A = α B γB = β₁β₂⋯

例えばA = αAA = εという生成規則を使ってAからαααという文を生成するときには、A → αA → ααA → αααA → αααという展開の順序になります。

このように、*?といった記法は単なるショートカットにすぎませんが、とはいえ短い書き方の方がわかりやすくて望ましいので、短い記法を使える場合は普通はその記法を使って簡潔に記述することが普通です。

単純な生成規則

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

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

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

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

expr → num → "1"
expr → num "+" num
     → "10" "+" "5"
expr → num "-" num "+" num
     → "42" "-" "30" "+" "2"

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

1の構文木
1の構文木
10+5の構文木
10+5の構文木
42-30+2の構文木
42-30+2の構文木

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

上の図のような文法に完全に一対一でマッチしている構文木は「具象構文木」(concrete syntax tree)と呼ばれることもあります。この用語は、抽象構文木と対比させたいときによく使われます。

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

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

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

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

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

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

1*2+3の構文木
1*2+3の構文木
1+2*3の構文木
1+2*3の構文木
1*2+3*4*5の構文木
1*2+3*4*5の構文木

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

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

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

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

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

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

1*2の構文木
1*2の構文木

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

1*(2+3)の構文木
1*(2+3)の構文木

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

再帰下降構文解析

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

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

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

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

具体的にコードで考えてみましょう。パーサに渡される入力はトークンの列です。トークンの型を再掲します。

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

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

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

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

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

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

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

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

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

最後に、便利な関数として、次のトークンが期待した型かどうかをチェックして、期待した型の場合だけ入力を1トークン読み進めて真を返す関数consumeを定義しておきます。

int consume(int ty) {
  if (tokens[pos].ty != ty)
    return 0;
  pos++;
  return 1;
}

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

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

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

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

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

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

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

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

Node *term() {
  // 次のトークンが'('なら、"(" expr ")"のはず
  if (consume('(')) {
    Node *node = expr();
    if (!consume(')'))
      error_at(tokens[pos].input,
               "開きカッコに対応する閉じカッコがありません");
    return node;
  }

  // そうでなければ数値のはず
  if (tokens[pos].ty == TK_NUM)
    return new_node_num(tokens[pos++].val);

  error_at(tokens[pos].input,
           "数値でも開きカッコでもないトークンです");
}

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

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

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

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

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

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

1+2*3のコールグラフ
1+2*3のコールグラフ

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

1*2+(3+4)のコールグラフ
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つの要素で置き換える命令です。

SUBMULDIV命令は、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が実行される時点ではスタックの状態は次のようになっています。

2
3

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

6

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

6
4
5

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

6
20

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

26

スタックマシンの計算結果はスタックトップに残っている値ということにすると、26は2*3+4*5の結果ですから、きちんとその式が計算できたことになるわけです。

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

CISCとRISC

x86-64は、1978年に発売された8086から漸進的に発展してきた命令セットで、典型的な「CISC」(シスク)と呼ばれるスタイルのプロセッサです。CISCプロセッサの特徴は、機械語の演算がレジスタだけではなくメモリアドレスを取ることが可能であるということ、機械語命令の長さが可変長であること、アセンブリプログラマにとって便利な複雑な操作を1命令で行う命令を多く備えていること、などがあります。

CISCに対して1980年代に発明されたのが「RISC」(リスク)です。RISCプロセッサの特徴は、演算は必ずレジスタ間でのみ行い、メモリに対する操作はレジスタへのロードとレジスタからのストアだけであること、機械語命令の長さがどの命令でも同じことであること、アセンブリプログラマにとって便利な複合命令を持っておらず、コンパイラが生成する簡単な命令のみを備えていること、などがあります。

x86-64はCISCの数少ない生き残りの一つで、x86-64以外の主要なプロセッサはほぼ全てRISCをベースにしています。具体的にはARM、PowerPC、SPARC、MIPS、RISC-V(リスク・ファイブ)などはすべてRISCプロセッサです。

RISCには、x86-64のようなメモリとレジスタ間の演算はありません。レジスタのエイリアスもありません。特定の整数レジスタが特定の命令で特別な使われ方をする、といったルールもありません。そういう命令セットが主流になっている現代の目から見ると、x86-64の命令セットは古めかしいものに見えます。

RISCプロセッサはその単純なデザインゆえに高速化しやすく、プロセッサ業界を席捲しました。ではなぜx86-64は生き残りに成功したのでしょうか? そこには既存のソフトウェア資産を活かせる高速なx86プロセッサを求める市場の巨大なニーズと、それに応えようとしたIntelやIntel互換チップメーカーの技術革新がありました。Intelは、CPUの命令デコーダでx86命令を内部的にある種のRISC命令に変換して、x86を内部的にRISCプロセッサ化しました。それによりRISCが高速化に成功したのと同じテクニックをx86に適用することが可能になったのです。

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

この節では、抽象構文木をスタックマシンのコードに変換する方法について説明します。それができるようになれば、四則演算からなる式をパースして抽象構文木を組み立て、それを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のpushpopといった命令は、暗黙のうちにRSPをスタックポインタとして使って、その値を変更しつつ、RSPが指しているメモリにアクセスする命令です。したがって、x86-64命令セットをスタックマシンのように使うときは、RSPをスタックポインタとして使うのが素直です。では早速、1+2という式を、x86-64をスタックマシンと見立ててコンパイルしてみましょう。以下にx86-64のアセンブリを示します。

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

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

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

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

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

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

pop rdi
pop rax
mul rax, rdi
push rax

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

pop rdi
pop rax
mul rax, rdi
push rax

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

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

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

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

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

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

  switch (node->ty) {
  case '+':
    printf("  add rax, rdi\n");
    break;
  case '-':
    printf("  sub rax, rdi\n");
    break;
  case '*':
    printf("  imul rdi\n");
    break;
  case '/':
    printf("  cqo\n");
    printf("  idiv rdi\n");
  }

  printf("  push rax\n");
}

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

imulは符号つき乗算を行う命令です。x86-64のimulが素直な仕様になっていれば、上のコードでは本来imul rax, rdiのように書きたかったところですが、そのような2つのレジスタをとる乗算命令はx86-64には存在しません。その代わりに、x86-64のimulは、暗黙のうちにRAXを取って、それを引数のレジスタの値に掛けて、その結果の上位64ビットをRDXに、下位64ビットをRAXにセットする、という仕様になっています。従って上のコードではimulにはレジスタを1つだけ渡しています。

idivは符号つき除算を行う命令です。idivは暗黙のうちにRDXとRAXを取って、それを連結したものを128ビット整数とみなして、それを引数のレジスタの64ビットの値で割り、その結果をRAXにセットする、という仕様になっています。cqo命令を使うと、RAXに入っている64ビットの値を128ビットに伸ばしてRDXとRAXにセットすることができるので、idivを呼ぶ前にcqoを呼んでいます。

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

掛け算や割り算のサイズ

一般にn桁の数を2つ掛けると、結果を表すためには2n桁必要になります。例えば3桁の10進数を掛けたときの最大の値を考えてみると、999×999=998001というように6桁の数になります。乗算をハードウェアで普通に実装すると、実際に引数のレジスタの2倍の桁数の結果が生成されます。x86-64ではその計算結果を無駄にすることなく、上位桁をRDXに、下位桁をRAXに保存することにしています。

割り算を普通に実装すると、割られる数は割る数の2倍の桁数が必要です。上位桁を0で埋めて計算を始めても構いませんが、x86-64ではRDXを使って上位桁の値を指定できるようになっています。また、割り算を行うと必然的に余りも同時に計算できてしまうのですが、それはRDXに保存されるという仕様になっています。

多くのRISCプロセッサは上記のx86-64のような機能は実装していません。RISCでは、掛け算では下位桁の結果だけがレジスタに保存され、割り算では上位桁は暗黙のうちに0で初期化される、といった仕様になっていることが多いようです。

そのような命令セットとx86-64を比較してみると、せっかく計算した値を無駄にしないx86-64の仕様の方が優れているように思えますが、実際には特にそういうわけでもありません。例えば掛け算においてアセンブリレベルでは常に2倍幅の結果が計算されているとはいっても、Cやそのほかの言語では結果の上位桁にアクセスする方法が特に規定されていないので、使いようがないというのが実際のところです。

また、多くのRISCプロセッサでは掛け算の上位桁と下位桁を計算する命令を別々に持っていて、2つの命令を使って2倍幅の結果を計算することが可能になっています。それらの命令は、連続して実行されるとき、ハードウェアが特別にそのパターンを認識して、内部的に1つの命令として実行するという最適化が行われていることがよくあります。したがって現代のプロセッサにおいては、RISCで大きな桁の数字を扱いたい時も、x86-64に比べて特に不利ということはありません。

x86-64の命令セットが現在の形になっている理由は歴史的事情によるところが多いのですが、掛け算や割り算もその一つの例です。

最適化コンパイラ

この章で筆者が説明に使ったx86-64のアセンブリはかなり非効率的に見えるかもしれません。例えばスタックに数値をpushしてそれをpopする命令は、直接レジスタにその値をmovする命令で書けば1命令で済むはずです。読者の中には、そういったアセンブリから冗長さを取り除いて最適化したいという気持ちが湧き上がってきている人もいることでしょう。しかし、その誘惑には決して負けないようにしてください。一番最初のコード生成では、コンパイラの実装の容易さを優先して冗長なコードを出力するのは、望ましいことなのです。

9ccには必要ならば後から最適化パスを付け足すことができます。生成されたアセンブリを再度スキャンして、特定のパターンで現れている命令列を別の命令列で置き換えることは難しくありません。例えば「push直後のpopmovに置き換える」とか「連続しているaddが、即値(そくち)を同じレジスタに足している場合、その即値を合計した値を足す1つのaddに置き換える」といったルールを作って、それを機械的に適用すれば、冗長なコードを、意味を変えることなくより効率的なコードに置き換えることができます。

コード生成と最適化を混ぜてしまうとコンパイラが複雑になってしまいます。最初から難しいコードになってしまうと、後から最適化パスを足すのはむしろ困難です。Donald Knuthが言っていたように「早すぎる最適化は全ての悪の元凶」なのです。読者の皆さんが作成するコンパイラでも、実装の簡単さだけを考慮するようにしてください。出力に含まれる明白な冗長さは後から取り除けるので心配する必要はありません。

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

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

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

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

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

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

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

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

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

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

9ccにおけるメモリ管理

読者は本書をここまで読んだところで、このコンパイラにおけるメモリ管理がどうなっているのか不思議に思っているかもしれません。ここまでに出てきたコードでは、mallocは使っていますが、freeは呼んでいません。つまりアロケートしたメモリは解放されません。これは、いくらなんでも手抜きではないでしょうか?

実際にはこの「メモリ管理を行わないことをメモリ管理ポリシーとする」という設計は、いろいろなトレードオフを考慮した上で、筆者が意図的に選択したデザインです。このデザインチョイスには多くのメリットがあります。

まず、メモリを解放しないことによって、まるでガベージコレクタがある言語のようにコードを書けるという点があります。これにより、メモリ管理を行うコードを書かなくてよくなるだけではなく、手動メモリ管理にまつわる不可解なバグを元から断つことができます。

次に、freeをしないことによって発生する問題というのは、普通のPCのようなコンピュータで動かすことを考えると、実質的にあまり存在しません。コンパイラは1つのCファイルを読み込んでアセンブリを出力するだけの短命なプログラムです。プログラム終了時に確保されているメモリはOSによってすべて自動的に解放されます。したがって、トータルでどれくらいメモリを割り当てるかということだけが問題になるわけですが、筆者の実測ではかなり大きなCファイルをコンパイルしたときでもメモリ使用量は100 MiB程度にすぎません。したがってfreeしないというのは現実的に有効な戦略なのです。例えばD言語のコンパイラDMDも、同じ考えから、mallocだけを行いfreeはしないというポリシーを採用しています。1

ステップ5:単項プラスと単項マイナス

引き算を行う-演算子は、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 = ("+" | "-")? term
term  = num | "(" expr ")"

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

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

-3*+5の構文木
-3*+5の構文木

また、-+3のような式が文法にマッチしないことを確認してみてください。-(+3)は正当な式ですが、プラスマイナスの単項演算子が複数連続する-+3のような式は、Cを含む多くの言語において不正な式ということになっています。

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

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

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

テストを書く際には、式全体の結果が0〜255に収まるようにしてください。Unixのプロセスの終了コードは0〜255の数字ということになっているので、mainから負数を返しても、それを正の数として解釈した数が返ることになって、意味がよくわからなくなってしまいます。-10+15などの式は、単項-を使いつつも全体の結果は正の数になっています。このような式を使ってテストを書いてください。

テストを数個書いて、単項+/-を追加するコードと一緒にチェックインすれば、このステップは完了です。

単項プラスと文法の良し悪し

単項+演算子はオリジナルのCコンパイラには存在しておらず、1989年にANSI(アメリカ国家規格協会)でCが標準化されたときに、公式に言語に追加されました。単項-がある以上、単項+もあったほうが対称性が高くてその意味でよいのは確かですが、実際のところは単項+は特に使い道がありません。

一方で単項+を文法に追加したことによる副作用もあります。Cに慣れていない人が+=演算子を誤ってi =+ 3のように書いてしまったとしましょう。単項+がなければこれは文法エラーになりますが、単項+があるためにこれはi = +3のように解釈されて、正当な代入式としてコンパイラに黙って受け付けられてしまいます。このように、文法を拡張すると思わぬところに副作用が出てしまうことは、言語を設計しているとよくあります。

ANSIのC言語標準化委員会は、上記の問題を理解した上で単項+を言語に追加するという判断を下したわけですが、読者の皆さんはどう思いますか? あなたがそのときC標準化委員会に属していたら、賛成しますか? 反対しますか?

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

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

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

符号なし整数

符号なし(unsigned)の数の表現は通常の2進数と同じです。10進数の数が、下の桁から順に1の桁、10の桁、100の桁、1000の桁、⋯⋯(すなわち100の桁、101の桁、102の桁、103の桁、⋯⋯)を表しているのと同じように、2進数の数は、下の桁から1の桁、2の桁、4の桁、8の桁、⋯⋯(すなわち20の桁、21の桁、22の桁、23の桁、⋯⋯)を表しています。

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

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

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

オーバーフローが引き起こした面白いバグ

数値のオーバーフローは時に思わぬバグを引き起こすことがあります。ここではゲーム「Civilization」のファーストバージョンにあったバグを紹介します。

Civilizationは文明間で戦う戦略シミュレーションゲームで、チンギスハンとかエリザベス女王みたいなプレイヤーを選んで、世界制覇か宇宙開発競争での勝利を目指すというゲームです。

初代Civilizationにあったバグは、非暴力主義のガンジーが突然核攻撃してくるというものでした。原因は文明が民主主義を採用すると攻撃性が2下がるというロジックでした。初代Civilizationではガンジーの攻撃性は全プレイヤー中で最小の1なのですが、ゲームが進んでインド文明が民主主義を採用すると、攻撃性がマイナス2されてオーバーフローで255になり、ガンジーがゲーム中で突如、極度に攻撃的なプレイヤーになってしまっていました。そして、そのころには大抵、科学技術の面で各文明が核兵器を持っているレベルまでゲームが進行しているので、結果的にガンジーがあるターンで突然核戦争を仕掛けてくるという行動が引き起こされていました。この「核ガンジー」はむしろゲーム的に面白いということで、それ以降のCivilizationシリーズでは定番化したのですが、初代ではこれは意図しないバグだったのです。

符号つき整数

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

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

4 3 2 1
符号なしの場合 8 4 2 1
符号つきの場合 -8 4 2 1

符号なしと同様、あるビットパターンが表している符号つきの値は、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ビットで表せるパターンは2n通り、つまり常に偶数通りありますが、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)0、(-2)1、(-2)2、⋯⋯を表していることになります。各桁が表す数について、4ビットの場合の比較表を以下に示します。

4 3 2 1
符号なし 8 4 2 1
2の補数 -8 4 2 1
マイナス2進数 -8 4 -2 1

4ビットのマイナス2進数では、次のように、-10〜5の計16個の整数を表すことができます。

5 0b0101
4 0b0100
3 0b0111
2 0b0110
1 0b0001
0 0b0000
-1 0b0011
-2 0b0010
-3 0b1101
-4 0b1100
-5 0b1111
-6 0b1110
-7 0b1001
-8 0b1000
-9 0b1011
-10 0b1010

マイナス2進数は、見るからに桁上がりなどの処理が大変で、表現可能な範囲の中央付近に0がこないという欠点がありますが、一方で符号ビットがいらないという面白い特徴があります。したがって、ある桁のマイナス2進数をより大きい桁数に拡張するときは、上位ビットは常に0で埋めて構いません。

このように、コンピュータ上での整数の表現は、2の補数表現に限らず様々な方法が考えられます。2の補数表現はその中で、ハードウェアで最も扱いやすい表現として、現存するほぼすべてのコンピュータで使われています。

符号の反転

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を求めることができたということになるわけです。

リテラルの数の基数

Cの標準規格では数を8進、10進、16進のいずれかで書くことができます。普通に123のように数を書くと10進数、0x8040のように先頭に0xをつけて書くと16進数、0737のように先頭に0をつけて書くと8進数になります。

Cで8進数で数を書く機能なんて使ったことないよ、と思う読者も多いかもしれませんが、この文法においては単なる0も8進数表記ということになるので、どのCプログラマも実は8進数をとても頻繁に書いています。これはちょっとしたトリビアですが、よく考えてみると深いような深くないような理由があります。

そもそも0というのは数の記法としてやや特殊です。普通、1のような数は、10の桁や100の桁が0だからといって001のように書いたりしないわけですが、そのルールを0にそのまま適用すると空文字列になってしまいます。0を書きたい時に何も書かないというのでは困るので、その場合は特別な記法として0と書いているわけですが、そうするとCの文法ではやや特殊なカテゴリということになってしまうわけです。

ステップ6: 比較演算子

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

トークナイザの変更

==!=<=>=を表すために、新たなenumの値TK_EQTK_NETK_LETK_GEを定義してください。EQ、NE、LE、GEというのは、それぞれequal、not equal、less than or equal、greater than or equalの省略形です。

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

新しい文法

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

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

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

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

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

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

単純で冗長なコードと、高度で簡潔なコード

再帰下降構文解析では生成規則にほぼそのまま対応したコードを書くことになるので、同じような規則をパースする関数は、同じような見た目になります。ここまでに書いたrelationalequalityaddmulも、同じような見た目の関数になっているはずです。

そういった関数に共通するパターンを、CのマクロやC++のテンプレート、高階関数やコード生成などのメタプログラミングのテクニックを使ってうまく抽象化できないかと考えることは、おそらく自然な発想でしょう。実際、そのようなことを行うことは可能です。しかし本書では、あえてそういったことを行なっていません。その理由は以下の通りです。

単純なコードは、やや冗長であっても理解するのは簡単です。似たような関数に同じような変更を後で加えることになったとしても、実際のところそれは大した手間ではありません。一方、高度に抽象化されたコードは、その抽象化メカニズムをまず理解し、それをどう使っているのかを次に理解する必要があるので、理解しづらくなりがちです。実際、メタプログラミングを使って再帰下降構文解析の関数を生成する関数を書くところから本書の解説を始めていたら、この本はもっと難しい本になってしまっていたでしょう。

技巧を凝らした簡潔なコードを書くことを常に目指す必要はありません。そういうことを目指していると、それ以上難しくできないところまでコードを難しくしてしまいがちです。

自分が書いたコードを自分で読むときに感じる感覚と、他の人が同じコードを読むときに感じる感覚は大きく異なります。コードを書いている本人はそのコードのエキスパートになるので、エキスパート目線から見た簡潔できれいなコードというものを良いコードだと感じがちですが、大半の読者は筆者と同じ感覚は共有していないので、筆者としての自分の感覚は疑ってかかる必要があります。

文章を読者のために書くように、コードも読者のために書くようにしましょう。自分のコードの読者の気持ちを忘れずに、「もっといい書き方がありそうな単純なコード」を必要に応じて書くというのは、理解しやすくメンテナンスしやすいプログラムを作るための重要なテクニックなのです。

アセンブリコードの生成

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を使うようにしてください。

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

フラグレジスタとハードウェア

値の比較結果が、普通の整数レジスタと異なる特別なレジスタに暗黙のうちに保存されるというこれはx86-64の仕様は、最初はわかりにくく感じるかもしれません。実際、RISCプロセッサでは、フラグレジスタを持つのを嫌って、値の比較結果を普通のレジスタにセットするという命令セットを持っているものがあります。たとえばRISC-Vはそのような命令セットです。

しかし、ハードウェアを実装する立場からすると、素朴な実装であれば、フラグレジスタを作るのはとても簡単です。つまり、整数演算を行うときに、その結果の線を分岐して別のロジックにつないで、そちらで結果がゼロかどうか(すべての線が0かどうか)とか、結果がマイナスかどうか(最上位ビットの線が1かどうか)などを見て、その結果をフラグレジスタにセットしてしまえばよいのです。フラグレジスタを持つCPUはまさにそのように実装されていて、整数演算を行うたびにフラグレジスタもついでに更新されることになります。

そのような仕組みでは、cmpだけではなくaddsubなどでもフラグレジスタは更新されます。実際、cmpの実体は、フラグレジスタだけを更新する特殊なsub命令ということになっています。sub rax, rdiというようにして、その後にフラグレジスタを見ればRAXとRDIの大小関係がわかるのですが、それだとRAXが更新されてしまうので、整数レジスタへの書き込みを行わないsubとしてcmpが用意されています。

ソフトウェアの場合、「ついでに何かを計算する」ということをすると必ず余分な時間がかかってしまいますが、ハードウェアでは、線を分岐して余分にトランジスタを使うこと自体に時間的ペナルティは発生しないので、フラグレジスタを毎回更新するコストは、素朴なハードウェア実装の場合には存在しないのです。

ステップ7:任意長の入力のサポート

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

可変長ベクタ

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

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

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

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

ベクタのために9cc.cに書くべき関数は以下の2つだけです。

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

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

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

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

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

テストコードを以下に示します。このコードを9cc.cに追加してください。

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

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

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

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

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

  printf("OK\n");
}

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

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

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

ベクタを使う

上記で定義した可変長ベクタを使って任意の長さの入力をサポートできるようにしてください。

[要加筆]

コンパイラを使ったバックドアの作成

システムのコンパイラを悪意あるバージョンに置き換えて、それを使ってコンパイルしたプログラムに、悪意あるコードを勝手に埋め込むという攻撃手法があります。

例えばスクリーンセーバは、自分自身を全画面で表示したうえで、フォームに正しいパスワードが入力されるまで終了しないプログラムとして書かれています。これを破ることを考えてみましょう。

コンパイラは、いまコンパイルしているソースファイルがスクリーンセーバの一部分なのかどうかは、ある程度はわかります。任意のスクリーンセーバを識別するのは無理ですが、オープンソースのスクリーンセーバの特定のバージョンのコードをそれなりの精度で識別するのは簡単でしょう。

パスワードが正しいかどうかを判定する関数がスクリーンセーバにあるとして、それをコンパイルしているということがわかったときだけ、秘密のパスワードを追加で勝手に受け付けるコードを出力するコンパイラというものを考えてください。そうすると、そのコンパイラでコンパイルしたスクリーンセーバは、正しいパスワードを知っている正当なユーザだけであhなく、攻撃者もアンロックできるようになってしまいます。

こういった攻撃では、スクリーンセーバのソースコードをどれだけ検査してみてもバックドアを発見することはできません。バックドアはそこではなくコンパイラのバイナリに埋め込まれているからです。

こういった攻撃手法はコンパイラに限りません。例えばOSに変更を加えて、特定のユーザがスクリーンセーバを実行しようとした時に限り、別の悪意あるスクリーンセーバを黙って実行するOSというのを考えることができます。検査を妨害するためにobjdumpやデバッガ、OSのファイルIOに変更を加えて、バックドアを巧妙に隠蔽する仕組みも考えられます。

結局のところ、ソフトウェアというものは、信頼できるソフトウェアを使って作成、実行したときにしか、本当に信用することはできないのです。


分割コンパイルとリンク

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

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

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

分割コンパイルとは

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

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

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

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

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

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

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

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

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

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

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

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

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

上記の要件をまとめてみると、関数本体の{ ... }を省いたものさえあれば、その関数を呼び出すのに十分な情報はあるということになります。そのような関数本体を省いたものを関数の「宣言」(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の関数呼び出しをコンパイルできるようになるのです。

ワンパスコンパイラと前方宣言

Cでは、1つのファイルに全部の関数をまとめて書くときでも、宣言が必要になることがあります。Cの言語仕様では、コンパイラがファイル全体を読み込むことをせずに、関数1つ1つを先頭から順にコンパイルしていけるようになっています。したがって、どの関数も、その関数がファイル中で出現するところまでに書かれた情報だけでコンパイルできるようになっていなければいけません。よって、ファイルの後ろで定義されている関数を使いたい場合、事前にその関数の宣言を書いておく必要があります。そういった宣言のことを「前方宣言」(forward declaration)といいます。

関数をファイルに書く順番を工夫することで、ほとんどの前方宣言は書かずに済ませることができますが、相互再帰している関数を書きたい場合には、前方宣言は必須です。

ファイル全体を読み込まずにコンパイルすることを許すというC言語の仕様は、メインメモリが非常に小さかった時代には意味がありましたが、今となっては時代遅れな仕様と言わざるをえないでしょう。コンパイラがもう少し賢ければ、同じファイルに書いてある定義については宣言を書かずに済ませることができるはずです。とはいえこの動作は言語仕様の一部ということになっているので、覚えておく必要があります。

リンクエラー

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

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

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

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

重複した定義とリンクエラー

重複した定義があるときに、どれか一つを選んで残りの定義を無視するというリンカの動作もありえます。そのようなリンカでは重複定義をしてもエラーにはなりません。

実際のオブジェクトファイルでも、定義ごとに重複を許すかどうかを選ぶことが可能になっていて、インライン関数やC++のテンプレートの展開結果などは重複を許す形でオブジェクトファイルに含められます。オブジェクトファイルのフォーマットやリンカの動作というのは意外に複雑で、例外が多いのですが、しかしそういった動作はあくまで例外です。デフォルトでは、重複した定義はエラーになることが普通です。

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

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

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

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

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

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

$ gcc -c -o 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というオプションを渡すことで変更できます。このオプションを使って実行ファイルを生成してみましょう。

$ gcc -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の有無だけなので見た目が似てしまいますが、宣言と定義は異なるものです。ここでそれをきっちり把握しておいてください。

リンカの歴史

複数の断片的な機械語ルーチンをつなぎ合わせて1つのプログラムにまとめるというリンカの機能は、コンピュータの黎明期から必要とされていました。1947年にJohn Mauchly(最初のデジタルコンピュータ、ENIACのプロジェクトリーダー)は、テープから読み込んだサブプログラムをリロケートして1つのプログラムにまとめるプログラムについて記述しています2

最初期のコンピュータにおいても、汎用的なサブルーチンは1回だけ書いていろいろなプログラムから使いたかったわけですが、そうなると、プログラムの断片を結合して実行可能なプログラムにするリンカというものが必要になるわけです。1947年というのは、アセンブラがまだ使われておらず、機械語で直接コードを書いていた時代なので、実はプログラマにとってリンカというのはアセンブラよりも先に作りたくなるプログラムなのです。

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

ファイルの分割

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

Makefileの変更

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

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

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

$(OBJS): 9cc.h

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

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

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

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

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

CFLAGSSRCSOBJSは変数です。

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

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

OJBSの右辺では変数の置換ルールを使っていて、それによりSRCの中の.cを.oに置き換えた値を生成しています。SRCSmain.c parse.c codegen.c container.cなので、OBJSmain.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ではローカル変数はスタックに置くことになっています。

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

...
リターンアドレス ← RSP

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

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

...
リターンアドレス
a
b ← RSP

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

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

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

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

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

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

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

...
gのリターンアドレス
gの呼び出し時点のRBP ← RBP
x
y ← RSP

ここからfを呼び出すと次の状態になります。

...
gのリターンアドレス
gの呼び出し時点のRBP
x
y
fのリターンアドレス
fの呼び出し時点のRBP ← RBP
a
b ← RSP

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

push rbp
mov rbp, rsp
sub rsp, 16

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

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

  1. fcallで呼び出した直後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP ← RBP
    x
    y
    fのリターンアドレス ← RSP
  2. push rbpを実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP ← RBP
    x
    y
    fのリターンアドレス
    fの呼び出し時点のRBP ← RSP
  3. mov rbp, rspを実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP
    x
    y
    fのリターンアドレス
    fの呼び出し時点のRBP ← RSP, RBP
  4. sub rsp, 16を実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP
    x
    y
    fのリターンアドレス
    fの呼び出し時点のRBP ← RBP
    a
    b ← RSP

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

mov rsp, rbp
pop rbp
ret

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

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

  1. mov rsp, rbpを実行する前のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP
    x
    y
    fのリターンアドレス
    fの呼び出し時点のRBP ← RBP
    a
    b ← RSP
  2. mov rsp, rbpを実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP
    x
    y
    fのリターンアドレス
    fの呼び出し時点のRBP ← RSP, RBP
  3. pop rbpを実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP ← RBP
    x
    y
    fのリターンアドレス ← RSP
  4. retを実行した後のスタック

    ...
    gのリターンアドレス
    gの呼び出し時点のRBP ← RBP
    x
    y ← RSP

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

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

スタックの伸びる方向

x86-64のスタックは、上記で説明したようにアドレスの大きい方から小さい方に成長します。逆方向、つまりスタックが上に伸びる方が自然な感じがしますが、なぜスタックは下に伸びるように設計されているのでしょうか?

実はスタックが下に成長する技術的な必然性はありません。実際のCPUやABIでは、スタックの開始地点を上位アドレスにして下に成長するようにするものが主流ですが、逆方向のものもあります。例えば8051マイクロコントローラや、PA-RISCのABI3、Multics4などではスタックは上位アドレス方向に成長します。

とはいえ、スタックが下方向に成長するという設計は、とりたてて不自然なものというわけでもありません。

電源投入直後、まっさらの状態からCPUがプログラムの実行を始めるにあたって、実行を開始するアドレスというのは、普通はCPUの仕様で決まっています。よくある設計では、CPUはアドレス0のような下位アドレスから実行を始めることになっています。そうすると普通はプログラムのコードはまとめて下位アドレスに置くことになります。スタックが成長してプログラムのコードと被ることがないように、その2つをなるべく離して配置すると、スタックを上位アドレスに置いて、アドレス空間の中央方向に向かって成長するように設計することになります。このようにすると、スタックは下に成長することになります。

もちろん上記のCPUとは違った設計をまた考えることができて、そうするとスタックを上に伸ばすことは可能です。これは正直どちらでもよい問題で、単に業界の一般的な認識としてマシンスタックは下に成長するということになっている、というのが実際のところです。

トークナイザの変更

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

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

enum {
  TK_NUM = 256, // 整数トークン
  TK_IDENT,     // 識別子
  ...

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

if ('a' <= *p && *p <= 'z') {
  tokens[i].ty = TK_IDENT;
  tokens[i].input = p;
  i++;
  p++;
  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      = ("+" | "-")? term
term       = 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('=', node, assign());
  return node;
}

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

Node *stmt() {
  Node *node = expr();
  if (!consume(';'))
    error_at(tokens[pos].input, "';'ではないトークンです");
  return node;
}

void program() {
  int i = 0;
  while (tokens[pos].ty != TK_EOF)
    code[i++] = stmt();
  code[i] = NULL;
}

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

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

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

左辺値と右辺値

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

代入式の左辺はどのような式でも許されているというわけではありません。例えば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に入っているアドレスにストアするということになります。

pushpopは暗黙のうちに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->ty != ND_IDENT)
    error("代入の左辺値が変数ではありません");

  int offset = ('z' - node->name + 1) * 8;
  printf("  mov rax, rbp\n");
  printf("  sub rax, %d\n", offset);
  printf("  push rax\n");
}

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

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

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

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

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

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

  switch (node->ty) {
  case '+':
    printf("  add rax, rdi\n");
    break;
  case '-':
    printf("  sub rax, rdi\n");
    break;
  case '*':
    printf("  imul 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) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

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

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

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

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

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

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

ASCIIコード

ASCIIコードでは、0〜127までの数に対して文字が割り当てられています。ASCIIコードにおける文字の割り当ての表を下に示します。

0 NUL SOH STX ETX EOT ENQ ACK BEL
8 BS HT NL VT NP CR SO SI
16 DLE DC1 DC2 DC3 DC4 NAK SYN ETB
24 CAN EM SUB ESC FS GS RS US
32 sp ! " # $ % & '
40 ( ) * + , - . /
48 0 1 2 3 4 5 6 7
56 8 9 : ; < = > ?
64 @ A B C D E F G
72 H I J K L M N O
80 P Q R S T U V W
88 X Y Z [ \ ] ^ _
96 ` a b c d e f g
104 h i j k l m n o
112 p q r s t u v w
120 x y z { | } ~ DEL

0〜31にあるのは制御文字です。現在ではNUL文字や改行文字などを除いて、このような制御文字を使う機会はほとんどなく、ほとんどの制御文字は文字コードの一等地を無駄に占めているだけの存在になってしまっていますが、ASCIIコードが策定された1963年当時には、これらの制御文字は実際によく使われていました。ASCII標準の策定時には、アルファベットの小文字を入れる代わりにさらに多くの制御文字を入れようという提案すらありました5

48〜58には数字、65〜90には大文字、97〜122には小文字が割り当てられています。これらの文字が連続したコードに割り当てられていることに注目してください。つまり0123456789やabcdefg...は文字コード上で連続しています。順番が定義されている文字をこのように連続した位置に置くのは当然のことに思えますが、EBCDICといった当時はメジャーだった文字コードでは、パンチカードの影響でアルファベットはコード上で連続していませんでした。

Cでは文字は単なる小さな整数型の値で、文字に対応するコードを数値として書くのと意味は変わりません。つまりASCIIを前提にすると、例えば'a'は97、'0'は48と等価です。上記のコードでは'z'から別の文字を数値として引いている式がありましたが、そのようにすると、与えられた文字がzから何文字離れているかを計算することができます。これはASCIIコード上でアルファベットが連続して並べられているからこそできる技なのです。

ステップ10: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という型のトークンで表すようにしましょう。returnwhileintのように、文法上特別な意味を持つトークン(キーワードといいます)は限られた個数しか存在しないので、このようにトークンごとに別の型を持たせるようにしたほうが簡単です。

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

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

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

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

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

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

Node *stmt() {
  Node *node;

  if (consume(TK_RETURN)) {
    node = malloc(sizeof(Node));
    node->ty = ND_RETURN;
    node->lhs = expr();
  } else {
    node = expr();
  }

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

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

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

void gen(Node *node) {
  if (node->ty == 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命令を複数出力してもかまわないということにしました。こういう細かいところは今の時点では気にしても仕方がないので、実装のシンプルさを優先することが大切です。難しいコードを書けるというのは役立つスキルですが、そもそもコードを難しくしすぎないというのは、時にはさらに役立つスキルなのです。

ステップ11:複数文字のローカル変数

以前の章では変数名を1文字に決め打ちにして、aからzまでの26個のローカル変数が常に存在しているものとして扱いました。この章では、任意の長さの変数名を使えるようにします。変数の個数も任意の個数ということにします。

マップ

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

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

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

マップのために9cc.cに追加すべき関数は次の3つです。

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

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

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

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

マップのテストは、ベクタのテストと同じように行うことができます。マップのテストを行う関数test_mapを以下に示します。

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

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

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

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

現在はruntest関数に直接ベクタのテストコードが書かれていると思いますが、そのコードをtest_vector関数に移して、runtestからtest_vectortest_mapを呼ぶようにしてください。最後にテストがうまく動いていることをmake testを実行して、このステップは完了です。

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

複数文字のローカル変数をサポート

この節では、1文字より長い名前を持つ識別子をサポートして、次のようなコードをコンパイルできるようにします。

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

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

まずはトークナイザを変更して、複数の文字からなる識別子をTK_IDENT型のトークンとして読み込むようにしてください。識別子はstrdupなどで文字列のコピーを作って、Tokenのメンバーに保存してください。識別子の名前のメンバーを含む新たなToken構造体の定義を下に示します。

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

パーサにおいては、現在までに出現したローカル変数の個数と、変数からその変数のRBPからのオフセットのマップの2つを新たに管理します。パーサは、識別子を見るたびに、その識別子がマップに存在するかを確認します。もしマップに存在していなければ、識別子をキーとして、ベースポインタからのオフセットをマップに挿入します。新たな変数のためのベースポインタからのオフセットは、現在までに見たローカル変数の個数から計算することができます。もし識別子がマップに存在していれば、マップをルックアップして帰ってきた値をそのままベースポインタからのオフセットとして使います。

機械語命令の出現頻度

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

命令の出現頻度
命令の出現頻度

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

1972年のCコンパイラ

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

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

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

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

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

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

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

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

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

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

実はこのerror関数は、単に無理やり少ない引数で読んでも正しく動作します。関数の引数チェックがこの時点では存在しなかったことを思い出してください。sp1p2といった引数は単にスタックポインタから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コンパイラには特筆するべきことが他にもあります。

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

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

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

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

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

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

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

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

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

ifwhileforを加えた新たな文法を以下に示します。

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

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

ステップ13: ブロック

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

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

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

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

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

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

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

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

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

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

...
term = 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の倍数になっていなければいけません。pushpopはRSPを8バイト単位で変更するので、call命令を発行するときに必ずしもRSPが16の倍数になっているとは限りません。この約束が守られていない場合、RSPが16の倍数になっていることを前提にしている関数が、半分の確率で落ちる謎の現象に悩まされることにmなります。関数を呼ぶ前にRSPを調整するようにして、RSPを16の倍数になるように調整するようにしましょう。

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

intへのポインタを表すデータ構造
intへのポインタを表すデータ構造

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

intへのポインタのポインタを表すデータ構造
intへのポインタのポインタを表すデータ構造

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

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

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

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

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

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

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

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

このステップでは、ポインタ型の値pに対してp+1p-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

intやlongのサイズ

x86-64 System V ABIのような、intが32ビット、longとポインタが64ビットのデータモデルのことを、LP64といいます。これはLongとPointerが64ビットという意味です。同じx86-64上のABIでも、WindowsはLLP64、すなわちintやlongは32ビットで、long longとポインタが64ビットというデータモデルを採用しています。

LP64とLLP64はlongのサイズが異なっているのでABI互換性がありません。たとえばlongのメンバを含む構造体を作って、構造体全体をそのままファイルに書き出して、読み込むときはファイル上のデータをその構造体に直接キャストして扱っているといった場合、UnixとWindowsでファイルを相互に渡して読むことはできません。

Cの仕様では、intは「そのマシンで自然な整数のサイズ」と定められています。そう言われると64ビットマシンではintを64ビットにしなければいけない感じがしますが、何が自然かというのは主観的な問題ですし、64ビットマシンでも普通は32ビット演算は自然に扱えるので、64ビットマシンでもintを32ビットにするというのはあながち間違ってはいません。それに現実的に考えると、intに64ビットもの大きさが必要なケースは少ないので、64ビットにしてもメモリが無駄になるだけのことが多いですし、shortが16ビットでintとlongが64ビットだと32ビット整数を表す型がなくなってしまうので、現存するほとんどの64ビットマシンではintは32ビットになっています。とはいえintが64ビットのILP64も存在はします。たとえば昔のCrayのスーパーコンピュータはILP64だったそうです。

ステップ19: sizeof演算子

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

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

我々のコンパイラにはまだ配列はありませんが、sizeof(x)は、xが配列ならばx全体のサイズをバイト数として返すことになります。例えばxint x[10]というように定義されている場合、sizeof(x)は40を返します。xint 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という型のトークンとして認識するようにしてください。

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

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

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

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

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

配列型を定義する

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

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

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

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

int a[10];

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

struct Type {
  enum { INT, PTR, ARRAY } ty;
  struct Type *ptrof;
  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

言語弁護士

フォーマルな言語仕様をよく理解している人のことを、言語仕様を法律に見立てて、「言語弁護士」(language lawyer)ということがあります。プログラマの俗語辞典「ジャーゴン・ファイル」では、言語弁護士は次のように説明されています6

Language lawyerという単語は、動詞として使ってlanguage lawyering(言語弁護士する)ということもあります。

熟練の言語弁護士は他のプログラマから一目置かれることが多いようです。筆者がGoogleのC++コンパイラチームで働いていた時には、チームに究極の言語弁護士というべき人がいて、C++でわからないことがあったときは、彼に訊いてみようという結論になることがよくありました(C++コンパイラを作っている人にもC++の仕様にはわからないところがたくさんあります)。実際、彼はメジャーなC++コンパイラのClangの主要な部分を実装した人で、C++に関して世界最高レベルに詳しい人物でしたが、その彼でも「C++はわかったと思ったらよくわからなくなる」と言っていたので、C++の言語仕様の巨大さと細部の複雑さは相当なものだなと思った記憶があります。

本書では、コンパイラの完成度が高まるまで、意図的にCの言語仕様の詳細に深入りしないようにしています。それには理由があります。仕様の存在するプログラミング言語を実装する場合、ある程度は言語弁護士になる必要があるものの、最初からあまり細かい点を気にしすぎるのは開発手法として望ましくないからです。絵を描くときに、一箇所だけを細かく描き込むのではなく、全体のラフなスケッチをまず完成させるように、プログラミング言語を実装している場合、最初はあまり言語弁護士しすぎないようにバランスを保ちつつ開発していく必要があります。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

配列は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

8ビットレジスタと32ビットレジスタの違い

なぜ1バイトの値を読み込むときにmovsxやmovzxを使う必要があるのでしょうか? 4バイトの値を読み込む時は、EAXのような下位32ビットのエイリアスのレジスタに普通のmovで読み込むだけでよかったので、charを読み込むときには、普通のmovでALにロードするだけでよさそうです。しかしそれではきちんと動きません。この謎の答えはx86-64の仕様にあります。

x86-64では、下位32ビットのエイリアスのレジスタに読み込むと、値が自動的に符号拡張されて、上位32ビットは0か1にリセットされます。しかし、下位8ビットのエイリアスのレジスタに読み込むときには、上位56ビットは以前の値がそのまま入ったままになるのです。一貫していない仕様ですが、x86-64は歴史が長い命令セットなので、こういった不一致はいろいろなところに存在しています。

x86-64は8086という16ビットプロセッサから、32ビット、64ビットと進化してきたので、まずALがあり、EAXができて、そのあとRAXができました。つまりALにロードしたときは、EAXの上位24ビットはリセットしない(そのままになる)という仕様がもともと存在していて、それを64ビットに拡張したとき、EAXにロードしたときはRAXの上位32ビットはリセットする、という仕様を策定したはずです。なぜこういう一貫性を損なう仕様にしたかというと、きちんと理由があります。

現代のプロセッサでは命令の依存関係をみて、無関係の命令(前の命令の結果を使っていない命令)はどんどん並列に実行していくようになっています。ここで仮に上位32ビットをリセットしない、という命令セットにしたとして、単にゴミとして上位32ビットも存在しているけど最後まで無視して下位32ビットだけを使い続ける、といったプログラミングスタイルにすると、結局のところ無視される上位32ビットを生成した命令と、その後に続く、同じレジスタを使っている命令の間に偽の依存関係が生じてしまうことになります。上位32ビットを符号拡張してリセットする仕様にすると、以前の値は完全に上書きされるので、依存関係を断ち切ることができます。そのためにx86を64ビット化するときには、一貫性を損なうのは承知の上で高速化しやすい仕様に決めたのです。

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

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

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

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

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

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

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

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

ここまでは引数の文字列に直接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 = malloc(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);
}

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

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

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

Cには2種類のコメントがあります。

一つのコメントは行コメントと呼ばれるもので、//から行末までがコメントになります。

もう一つはブロックコメントと呼ばれるもので、/*が開始記号、*/が終了記号ということになっています。コメントの中の文字は、*/という2文字の並びを除いてすべて読み飛ばされます。したがってブロックコメントは入れ子にすることはできません。/*はコメント中では特別な意味を持たないので、既存のブロックコメントをコメントアウトして

/* /* ... */ */

のようにすると、最初の*/でコメントが終了することになり、普通は2個めの*/で構文エラーが発生することになります。

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

void tokenize(char *p) {
  int i = 0;
  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を返します。

ステップ27: テストを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つ以上の「セグメント」(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"のように書くこともできます。

グローバル変数の動的な初期化

Cではグローバル変数の内容は静的に決まっている必要がありますが、C++ではグローバル変数を任意の式を使って初期化することができます。つまり、C++では、main関数が呼ばれるより前にグローバル変数の初期化式が実行されます。それは次のようなメカニズムで動いています。

このように、コンパイラとリンカ、プログラムローダの共同作業によって、グローバル変数の動的な初期化が可能になっているわけです。

C++と同じメカニズムを使うようにすれば、Cでもグローバル変数の動的な初期化をサポートできますが、そのような機能はあえて言語仕様から外されています。

C言語仕様のデザインチョイスでは、プログラムを書く側にとっては制限は多くなりますが、プログラムを実行する側では、貧弱なローダやローダのない環境(コンピュータの起動時にROMから直接実行されるコードなど)でも言語仕様を完全に満たすことができることになります。したがってこれは割り切りの問題であって、どちらが優れているという話ではありません。

初期化式の文法

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

まず初期化式では配列を初期化することができます。たとえば次の式は、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;と同じようにコンパイルされます。

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

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

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

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

おわりに

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


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

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

整数レジスタの一覧

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

64 32 16 8
RAX EAX AX AL
RDI EDI DI DIL
RSI ESI SI SIL
RDX EDX DX DL
RCX ECX CX CL
RBP EBP BP BPL
RSP ESP SP SPL
RBX EBX BX BL
R8 R8D R8W R8B
R9 R9D R9W R9B
R10 R10D R10W R10B
R11 R11D R11W R11B
R12 R12D R12W R12B
R13 R13D R13W R13B
R14 R14D R14W R14B
R15 R15D R15W R15B

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

レジスタ 使い方
RAX 返り値 / 引数の数
RDI 第1引数
RSI 第2引数
RDX 第3引数
RCX 第4引数
RBP ベースポインタ
RSP スタックポインタ
RBX (特になし)
R8 第5引数
R9 第6引数
R10 (特になし)
R11 (特になし)
R12 (特になし)
R13 (特になし)
R14 (特になし)
R15 (特になし)

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

メモリアクセス

mov dst, [src] srcのアドレスからdstに値をロード
mov [dst], src srcの値をdstのアドレスにストア
push r64/imm RSPを8減らして、r64/immをRSPにストア
pop r64 RSPからr64にロードして、RSPを8増やす

関数呼び出し

call label RIPをスタックにプッシュしてlabelにジャンプ
call *r64 RIPをスタックにプッシュしてr64のアドレスにジャンプ
ret スタックをポップしてそのアドレスにジャンプ
leave mov rsp, rbpの後pop rbpと同等

条件分岐

cmp reg1, reg2/imm
je label
reg1 == reg2/immならlabelにジャンプ
cmp reg1, reg2/imm
jne label
reg1 != reg2/immならlabelにジャンプ
cmp reg1, reg2/imm
jl label
reg1 < reg2ならlabelにジャンプ
(符号ありでの比較)
cmp reg1, reg2/imm
jle label
reg1 <= reg2ならlabelにジャンプ
(符号ありでの比較)

条件代入

cmp reg1, reg2/imm
sete al
movzb eax, al
RAX = (reg1 == reg2) ? 1 : 0
cmp reg1, reg2/imm
setne al
movzb eax, al
RAX = (reg1 != reg2) ? 1 : 0
cmp reg1, reg2/imm
setl al
movzb eax, al
RAX = (reg1 > reg2) ? 1 : 0
(符号ありでの比較)
cmp reg1, reg2/imm
setle al
movzb eax, al
RAX = (reg1 >= reg2) ? 1 : 0
(符号ありでの比較)

整数・論理演算

add dst, src/imm dst = dst + src/imm
sub dst, src/imm dst = dst - src/imm
mul src RDX:RAX = RAX * src
imul src mulの符号つきバージョン
div r32 EAX = EDX:EAX / r32
EDX = EDX:EAX % r32
div r64 RAX = RDX:RAX / r64
RDX = RDX:RAX % r64
idiv r32/r64 divの符号つきバージョン
cqo RAXを128ビットに符号拡張して
RDX:RAXにストア
and dst, src dst = src & dst
or dst, src dst = src | dst
xor dst, src dst = src ^ dst
neg dst dst = -dst
not dst dst = ~dst
shl dst, imm/CL immかCLレジスタの値だけdstを左シフトする(レジスタでシフト量を指定する場合、CLしか使えない)
shr dst, imm/CL immかCLレジスタの値だけdstを論理右シフトする
シフトインされてきた上位ビットはゼロクリアされる
sar dst, imm/CL immかCLレジスタの値だけdstを算術右シフトする
シフトインされてきた上位ビットは、もともとのdstの符号ビットと同じになる
lea dst, [src] [src]のアドレス計算を行うが、メモリアクセスは行わずアドレス計算の結果そのものをdstにストア
movsb dst, r8 r8を符号拡張してdstにストア
movzb dst, r8 r8を符号拡張せずにdstにストア
movsw dst, r16 r16を符号拡張してdstにストア
movzw dst, r16 r16を符号拡張せずにdstにストア

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

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

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なファイルシステムを常に念頭に置いてみてください。きっといろいろなことがわかりやすくなるはずです。


参考資料


  1. http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941

    DMD does memory allocation in a bit of a sneaky way. Since compilers are short-lived programs, and speed is of the essence, DMD just mallocs away, and never frees.

  2. Linkers and Loaders, ISBN 978-1558604964, John R. Levine (1999) 1.2章

    Perhaps surprisingly, these two basic linker functions — relocation and library search — appear to predate even assemblers, as Mauchly expected both the program and subprograms to be written in machine language.

  3. https://parisc.wiki.kernel.org/images-parisc/b/b2/Rad_11_0_32.pdf The 32-bit PA-RISC run-time architecture document, v. 1.0 for HP-UX 11.0, 2.2.3章

    When a process is initiated by the operating system, a virtual address range is allocated for that process to be used for the call stack, and the stack pointer (GR 30) is initialized to point to the low end of this range. As procedures are called, the stack pointer is incremented to allow the called procedure frame to exist at the address below the stack pointer. When procedures are exited, the stack pointer is decremented by the same amount.

  4. https://www.acsac.org/2002/papers/classic-multics.pdf

    Thirty Years Later: Lessons from the Multics Security Evaluation, "Third, stacks on the Multics processors grew in the positive direction, rather than the negative direction. This meant that if you actually accomplished a buffer overflow, you would be overwriting unused stack frames, rather than your own return pointer, making exploitation much more difficult.

  5. https://en.wikipedia.org/wiki/ASCII#cite_note-Mackenzie_1980-1

    There was some debate at the time whether there should be more control characters rather than the lowercase alphabet.

  6. http://catb.org/~esr/jargon/html/L/language-lawyer.html

    language lawyer: n. A person, usually an experienced or senior software engineer, who is intimately familiar with many or most of the numerous restrictions and features (both useful and esoteric) applicable to one or more computer programming languages. A language lawyer is distinguished by the ability to show you the five sentences scattered through a 200-plus-page manual that together imply the answer to your question “if only you had thought to look there”. Compare wizard, legal, legalese.