# 言語処理系を作りたい人のためのC言語入門 **自分の手でインタプリタやコンパイラを書いてみたい。** そう思ったとき、最初の壁になりがちなのが「実装に使う言語」です。世の中の本格的な言語処理系の多くは、いまでもC言語（あるいはその親戚であるC++）で書かれています。Rubyも、Pythonの標準実装CPythonも、Luaも、その心臓部はCで書かれています。 この本は、**「簡単な言語処理系を作る」という目的のために必要なC言語の知識だけを、最短距離で速習する**ためのテキストです。C言語の機能をすべて網羅することはしません。そのかわり、トークンを並べ、構文木を組み立て、値を表現し、実行を速くする。そうした言語処理系づくりの場面で実際に効いてくる道具を、なぜそれが必要なのかという理由とともに丁寧に説明します。 ## この本が想定する読者 - 情報系の学部1年生くらいの知識を持っている人 - C言語は授業で少し触れたか、まったく触れていないくらいの人 - 「式を計算するインタプリタ」のような小さな言語処理系を、自分の手で作ってみたい人 数学やアルゴリズムの高度な前提知識は要りません。プログラミングを何か一つでもかじったことがあれば読み進められます。 ## この本で扱う主な道具 型と `typedef`、ポインタ、構造体（`struct`）、共用体（`union`）、関数ポインタ、`const`、動的メモリ管理、そして最適化の基礎と発展。これらはどれも、言語処理系を書くときに繰り返し登場する道具です。 > [!NOTE] > 本書のサンプルコードは、四則演算を解釈する小さな「電卓言語」のインタプリタを少しずつ育てながら進みます。章をまたいで同じ題材が育っていくので、順番に読むことをおすすめします。 # なぜ言語処理系にC言語なのか この章では、本書全体の地図を描きます。そもそも「言語処理系」とは何か、なぜその実装にC言語がよく使われるのか、そして本書をどう読み進めればよいのかを説明します。手を動かすための開発環境の準備にも触れます。 ## 言語処理系とは何か **言語処理系（language processor）**とは、プログラミング言語で書かれたソースコードを受け取り、それを実行したり、別の形式に変換したりするソフトウェアの総称です。代表的なものに次の二種類があります。 - **インタプリタ（interpreter）**：ソースコードを読みながら、その場で意味を解釈して実行する処理系。Rubyの標準実装やPythonの標準実装CPythonがこの方式です。 - **コンパイラ（compiler）**：ソースコードを、機械語や別の言語など、より低レベルな形式へ一括変換する処理系。CコンパイラのGCCやClangがこれにあたります。 どちらも内部では似た段階を踏みます。文字の並びを意味のある単位（**トークン**, token）に区切る**字句解析（lexical analysis）**、トークンの並びから文法構造を組み立てる**構文解析（parsing）**、そして組み立てた構造を実行または変換する段階です。構文解析の結果は普通、木構造の形にまとめられ、これを**抽象構文木（abstract syntax tree, AST）**と呼びます。たとえば `1 + 2 * 3` という式は、次のような木になります。 ```mermaid graph TD A["+"] --> B["1"] A --> C["*"] C --> D["2"] C --> E["3"] ``` 掛け算が足し算より深い位置にあるのは、掛け算が先に計算されるからです。この木を根からたどって計算すれば `1 + 6 = 7` が得られます。本書の後半では、まさにこの「木を作って、たどって、計算する」処理をC言語で書けるようになることを目指します。言語処理系の全体像をより深く学びたい場合は、定番の教科書であるドラゴンブック[](#cite:aho2006)や、手を動かしながら学べる[Crafting Interpreters](#cite:nystrom2021)が良い道案内になります。 > [!NOTE] > 本書は「C言語の入門書」であって「言語処理系の作り方の本」ではありません。言語処理系づくりは、Cの機能がなぜ必要になるかを示すための**題材**として使います。木の作り方そのもの（構文解析アルゴリズムなど）は深追いせず、Cの道具立てに集中します。 ## なぜC言語なのか 世の中には便利な言語がたくさんあるのに、なぜいまさらCを学ぶのでしょうか。言語処理系という文脈では、いくつもの理由があります。 第一に、実物がCで書かれていることです。前述のCPythonやLua、Rubyの処理系MRIなど、広く使われている言語処理系の心臓部はCで書かれています。それらのソースコードを読んだり改造したりしたいなら、Cが読めることは大きな武器になります。 第二に、メモリの仕組みが見えることです。言語処理系は、値やASTといったデータを大量に作っては捨てます。どこにメモリが確保され、いつ解放されるのかを意識できることは、効率的な処理系を書くうえで欠かせません。Cはメモリを隠さない言語なので、この感覚が自然に身につきます。 第三に、速いことです。インタプリタの内側のループは、プログラムの実行中に何百万回も回ります。ここが遅いと処理系全体が遅くなります。Cは機械語に近い制御ができるため、速い処理系を書きやすいのです。インタプリタの速さがどこから来るのかは、Ertlらの研究[](#cite:ertl2003)でも詳しく分析されています。 > [!TIP] > 「速い言語」が常に正解というわけではありません。試作の段階ではPythonやRubyのような書きやすい言語で書き、性能が問題になったところだけをCで書き直す、という進め方も現実的です。本書はあくまで「Cという選択肢を取れるようになる」ことを目指します。 ## 本書の進め方 本書は三部構成です。第I部でCの基礎（コンパイルの流れ、型、ポインタ）を固め、第II部でデータを表現する道具（構造体、共用体、関数ポインタ、`const`、メモリ管理）を学び、第III部で処理系を速くする最適化を扱います。 各章は前の章を前提に進みます。とくにポインタ（[](pointers.md)）は後のほとんどの章で使うので、飛ばさずに読んでください。巻末には用語集（[](glossary.md)）と、さらに学ぶための文献案内（[](further-reading.md)）を用意しました。知らない言葉が出てきたら用語集を引いてください。 ## 開発環境を用意する C言語のプログラムを動かすには、コンパイラが必要です。代表的なものにGCCとClangがあります。多くのLinux環境やmacOSでは、どちらかが最初から入っているか、簡単に導入できます。 コンパイラが入っているかは、ターミナル（端末）で次のように打って確かめられます。 ```bash cc --version ``` `cc` は「Cコンパイラ」を指す慣習的な名前で、GCCやClangへの別名になっていることが多いです。バージョン情報が表示されれば準備完了です。表示されない場合は、Linuxなら `build-essential`（GCC一式）パッケージを、macOSなら「Command Line Tools」を導入してください。 簡単なプログラムをコンパイルして実行する流れは次のようになります。`hello.c` というファイルに書いて、 ```c #include int main(void) { printf("こんにちは、言語処理系\n"); return 0; } ``` 次のコマンドでコンパイルし、できた実行ファイルを動かします。 ```bash cc hello.c -o hello ./hello ``` `-o hello` は「`hello` という名前の実行ファイルを作れ」という指示です。`./hello` で実行すると、メッセージが表示されます。各行が何をしているのかは次の章で詳しく説明するので、いまは「こうやって動かすのだ」という流れだけつかめれば十分です。 > [!IMPORTANT] > 本書を読むうえで一番効果的なのは、**サンプルコードを実際にコンパイルして動かしてみる**ことです。エラーメッセージに出会い、それを直す経験こそがC言語の習得を早めます。読むだけでなく、ぜひ手を動かしてください。 # 第I部　C言語の足場を固める 言語処理系を書く前に、まずC言語そのものの足場を固めます。この部では、Cプログラムがどうやって動く形になるのか（コンパイルの流れ）、値を入れる「型」とは何か、そしてC言語を理解するうえで避けて通れない「ポインタ」を扱います。 ここで紹介する道具は、後の部で構文木や値を表現するときの土台になります。急がば回れ。まずはこの三つの章でCの世界の地面を踏み固めましょう。 # C言語の基礎 この章では、C言語のプログラムが「文字の並び」から「動くもの」になるまでの流れと、どんなプログラムにも共通する基本部品（変数、式、制御構造、関数）を一通り押さえます。すでにCを少しかじったことがある人にとっては復習になりますが、後の章で使う言葉をそろえる意味でも目を通してください。 ## ソースコードから実行ファイルまで Cのプログラムは、人間が読める**ソースコード**として書かれます。これはそのままでは動きません。コンピュータが実行できるのは、CPUが直接理解する**機械語（machine code）**だけだからです。ソースコードを機械語に翻訳する道具が**コンパイラ**です。 実は、`cc hello.c -o hello` という一つのコマンドの裏で、いくつかの段階が順に実行されています。 ```mermaid graph LR A[ソースコード
hello.c] --> B[プリプロセス] B --> C[コンパイル] C --> D[アセンブル] D --> E[リンク] E --> F[実行ファイル
hello] ``` - **プリプロセス（preprocess）**：`#include` や `#define` といった、`#` で始まる命令を処理します。`#include ` は「`stdio.h` というファイルの中身をここに貼り付けよ」という意味で、`printf` などの機能を使えるようにします。`#define` で定義する**マクロ（macro）**は、コンパイル前にテキストを置き換える仕組みです。 - **コンパイル（compile）**：プリプロセス済みのCコードを、CPUごとの**アセンブリ言語**に翻訳します。 - **アセンブル（assemble）**：アセンブリ言語を機械語に翻訳し、**オブジェクトファイル**を作ります。 - **リンク（link）**：複数のオブジェクトファイルや、`printf` のような既製の部品（**ライブラリ**）をつなぎ合わせ、一つの実行ファイルにまとめます。 ふだんは一つのコマンドにまとまっているので意識する必要はありませんが、「ヘッダファイルを include し忘れた」「関数の定義が見つからない（リンクエラー）」といった失敗の原因を理解するには、この段階分けを知っておくと役に立ちます。各段階の詳細は[](#cite:kernighan1988)の付録や[](#cite:seacord2020)で丁寧に解説されています。 > [!NOTE] > C言語には**規格（standard）**があります。「C99」「C11」「C17」などはその版を表す呼び名で、最新のものの一つがC17[](#cite:iso2018)です。規格はコンパイラごとの方言を防ぎ、「正しいCプログラムとは何か」を定めています。コンパイル時に `cc -std=c17 hello.c` のように版を指定できます。 ## main関数とプログラムの入り口 すべてのCプログラムは、`main` という名前の関数から実行が始まります。 ```c #include int main(void) { printf("計算を始めます\n"); return 0; } ``` `int main(void)` を分解してみましょう。先頭の `int` は、この関数が**整数（integer）**を返すことを示します。`main` が返す整数は**終了コード**と呼ばれ、`0` は「正常終了」を、それ以外は「何らかの異常」を意味する慣習です。括弧の中の `void`（ボイド、「空」の意）は「引数を受け取らない」という意味です。`{` から `}` までが関数の中身で、上から順に実行されます。`return 0;` でこの値を呼び出し元（OS）に返してプログラムは終わります。 `printf` は文字列を画面に表示する関数です。末尾の `\n` は**改行**を表す特殊な書き方で、これがないと次の出力と同じ行にくっついてしまいます。 ## 変数とデータ型 **変数（variable）**は、値に名前を付けて覚えておく入れ物です。Cでは、変数を使う前にその**型（type）**を宣言しなければなりません。型とは「その入れ物に何を入れるか」を表すもので、たとえば整数なら `int`、小数なら `double` です。 ```c int count = 0; // 整数の変数 count を 0 で初期化 double pi = 3.14159; // 小数の変数 pi char grade = 'A'; // 1文字を表す変数（'A' は文字定数） ``` `//` から行末まではコメントで、コンパイラに無視されます。複数行のコメントは `/* ... */` でも書けます。 変数に最初の値を与えることを**初期化（initialization）**と呼びます。初期化していない変数の中身は不定（何が入っているかわからない）で、これはバグの温床です。宣言と同時に初期化する習慣をつけましょう。型については次章[](types.md)でさらに詳しく扱います。 > [!WARNING] > 初期化していない変数を読むのは、Cでよくある間違いの一つです。`int x;` とだけ書いて値を入れる前に `x` を使うと、ゴミの値が読まれて結果が不定になります。コンパイラの警告を有効にする `-Wall` オプション（`cc -Wall ...`）を付けると、こうした危険を多く知らせてくれます。 ## 式と演算子 **式（expression）**は、計算して値を生み出す断片です。`1 + 2` も `count * 3` も式です。Cの主な算術演算子は次のとおりです。 | 演算子 | 意味 | 例 | 結果 | |--------|------|----|------| | `+` | 加算 | `3 + 4` | `7` | | `-` | 減算 | `10 - 6` | `4` | | `*` | 乗算 | `3 * 4` | `12` | | `/` | 除算 | `7 / 2` | `3`（整数同士なら切り捨て） | | `%` | 剰余（余り） | `7 % 2` | `1` | 注意したいのは `/` です。整数同士の割り算は**小数点以下が切り捨て**られ、`7 / 2` は `3` になります。`3.5` がほしければ `7.0 / 2` のように、どちらかを小数にする必要があります。この「型によって演算の意味が変わる」性質は、言語処理系で割り算を実装するときに必ず向き合う問題です。 比較演算子（`==` 等しい、`!=` 等しくない、`<`、`>`、`<=`、`>=`）は、条件が成り立てば `1`、成り立たなければ `0` という値を返します。Cには本来「真偽」専用の型がなく、**0を偽、0以外を真**として扱う点を覚えておいてください。 > [!CAUTION] > 「等しい」を表す `==` と、代入の `=` を取り違える間違いはよく起こります。`if (x = 0)` と書くと、`x` に `0` を代入したうえでその結果（`0`＝偽）で条件判定してしまい、意図と違う動きになります。比較のつもりなら必ず `==` を使ってください。 ## 条件分岐とくり返し プログラムを「上から順に実行する」だけでなく、条件によって枝分かれさせたり、くり返したりするのが**制御構造（control flow）**です。 条件分岐は `if` と `else` で書きます。 ```c if (n % 2 == 0) { printf("偶数です\n"); } else { printf("奇数です\n"); } ``` くり返しは `while` や `for` を使います。次は1から10までの合計を求める例です。 ```c int sum = 0; for (int i = 1; i <= 10; i++) { sum += i; // sum = sum + i と同じ } printf("合計は %d です\n", sum); ``` `for (初期化; 継続条件; 更新)` の三つの部分を見てみましょう。まず `int i = 1` でカウンタを用意し、`i <= 10` が成り立つ間くり返し、各回の最後に `i++`（`i` を1増やす）を実行します。`sum += i` は `sum = sum + i` の短い書き方です。`printf` の中の `%d` は「ここに整数を10進数で埋め込め」という指示で、後ろの `sum` の値に置き換わります。 くり返しは言語処理系にとって特別に重要です。なぜなら、インタプリタの本体は「次の命令を取り出して実行する」ことの巨大なくり返しだからです。このループの効率が処理系全体の速度を左右します（[](optimization-advanced.md)で詳しく扱います）。 ## 関数 **関数（function）**は、ひとまとまりの処理に名前を付けて、何度でも呼び出せるようにする仕組みです。`main` も関数の一つでした。自分で関数を定義してみましょう。 ```c #include // 二つの整数を受け取り、大きいほうを返す関数 int max(int a, int b) { if (a > b) { return a; } else { return b; } } int main(void) { int result = max(3, 8); printf("大きいほうは %d\n", result); // 8 と表示される return 0; } ``` `int max(int a, int b)` の読み方は、`main` のときと同じです。返り値の型が `int`、名前が `max`、そして括弧の中の `int a, int b` が**引数（argument）**、つまり呼び出し時に渡される値の受け皿です。`max(3, 8)` と呼ぶと、`a` に `3`、`b` に `8` が入り、`return` で返された値が `result` に代入されます。 関数を使うと、複雑な処理を小さな部品に分けて考えられます。言語処理系のような大きなプログラムでは、「字句解析をする関数」「構文解析をする関数」「式を評価する関数」のように役割ごとに関数を分けるのが定石です。良い関数分割は、プログラムを読みやすく、直しやすくします[](#cite:kernighan1988)。 > [!IMPORTANT] > 関数は呼び出される前に、コンパイラがその存在を知っている必要があります。上の例では `max` を `main` より前に定義しているので問題ありません。順序を入れ替えたいときは、関数の中身を書かずに型だけを宣言する**プロトタイプ宣言**（`int max(int a, int b);`）をファイルの先頭に置きます。これは関数を別ファイル（ヘッダファイル）にまとめるときの基本でもあります。 ## この章のまとめ - Cのソースコードは、プリプロセス・コンパイル・アセンブル・リンクを経て実行ファイルになる。 - プログラムは `main` 関数から始まる。 - 変数は型を持ち、使う前に宣言・初期化する。 - 式は値を生み、`/` は整数だと切り捨てになるなど型に注意がいる。 - `if`／`for`／`while` で処理の流れを制御する。 - 処理は関数に分けて名前を付ける。 次章では、この「型」という考え方をさらに詳しく扱います。 # 基本型 前章で「変数には型がある」と述べました。型はC言語の根幹であり、言語処理系を書くときには「処理系自身を実装するための型」と「処理系が扱う言語の型」の二つを同時に考えることになります。この章では、Cが持つ基本型の正体を見ていきます。型に別名を付ける `typedef` は、構造体や共用体を学んだ後の章（[](typedef.md)）で扱います。 ## ビットの解釈の仕方としての型 コンピュータのメモリに入っているのは、突き詰めれば `0` と `1` の並び、すなわち**ビット（bit）**の列だけです。同じビット列でも、それを「整数」と思って読むか「小数」と思って読むかで、意味はまったく変わります。型とは、そのビット列をどう解釈し、どれだけの幅（バイト数）を占め、どんな演算ができるかを決める情報です。 たとえば32個のビット列 `01000001...` は、整数として読めばある数値ですが、文字として読めば `'A'` かもしれません。型がこの解釈を確定させます。だからこそCは、変数を宣言するときに型を要求するのです。この「ビットの解釈」という見方は、後で共用体（[](union.md)）を理解するときの土台になります。 ```mermaid graph TD A["メモリ上のビット列
01000001 00000000 ..."] --> B["int として解釈 → 65"] A --> C["char として解釈 → 'A'"] A --> D["float として解釈 → 別の値"] ``` ## 整数型と、その幅 Cの整数型は一種類ではありません。表せる値の範囲（＝占めるビット数）によって、いくつかの型があります。 | 型 | おおよその幅 | 用途の目安 | |----|------------|-----------| | `char` | 1バイト（8ビット） | 文字、または小さな整数・バイト列 | | `short` | 2バイト | 小さめの整数 | | `int` | 4バイト（多くの環境） | ふつうの整数。基本はこれ | | `long` | 4または8バイト | 大きめの整数 | | `long long` | 8バイト | とても大きな整数 | ここで「おおよそ」と書いたのには理由があります。**Cの規格は、各型の正確なバイト数を固定していません**[](#cite:iso2018)。「`int` は `short` 以上、`long` は `int` 以上」といった大小関係は決まっていますが、具体的な幅は環境（CPUやコンパイラ）に委ねられています。手元の環境での実際の幅は `sizeof` 演算子で調べられます。 ```c #include int main(void) { printf("int は %zu バイト\n", sizeof(int)); printf("long は %zu バイト\n", sizeof(long)); return 0; } ``` `sizeof(型)` はその型が占めるバイト数を返します。`printf` の `%zu` は `sizeof` が返す型（`size_t` という符号なし整数型）を表示するための書式です。 > [!WARNING] > 「`int` は必ず4バイト」と思い込むと、別の環境に移したときに動かなくなることがあります。言語処理系のように長く使われ、いろいろな環境で動かしたいソフトウェアでは、この**移植性（portability）**の問題が現実になります。次節の固定幅整数型がその対策です。 ## 符号の有無と固定幅整数型 整数型には、負の数を表せる**符号付き（signed）**と、負の数は表せないかわりに同じビット数でより大きな正の数まで表せる**符号なし（unsigned）**の区別があります。`unsigned int` のように `unsigned` を付けると符号なしになります。バイト列の長さ（バイナリのサイズ）や文字コードなど、負にならない量を扱うときは符号なしが自然です。 幅が環境依存だと困る場面のために、Cは**幅を名前で固定した整数型**を用意しています。`` を include すると使えます。 ```c #include int32_t token_id; // ちょうど32ビットの符号付き整数 uint8_t byte; // ちょうど8ビットの符号なし整数（バイト1個） int64_t big_value; // ちょうど64ビットの符号付き整数 ``` `int32_t` なら、どの環境でも必ず32ビットです。言語処理系では「バイトコードの1命令を `uint8_t` で表す」「整数値を `int64_t` で持つ」のように、幅をきっちり決めたい場面が多く、これらの型が活躍します[](#cite:nystrom2021)。 > [!CAUTION] > 符号なし整数の引き算には落とし穴があります。`unsigned int a = 0;` のとき `a - 1` は「−1」にはならず、表せる最大値（環境により約42億）に**回り込み（ラップアラウンド）**ます。配列の添字計算などでこれを踏むと、見つけにくいバグになります。引き算が負になりうるなら符号付きを使いましょう。 ## 浮動小数点型と文字 小数を扱うには**浮動小数点型**を使います。`float`（単精度、約4バイト）と `double`（倍精度、約8バイト）があり、精度が必要なら `double` を使うのが無難です。浮動小数点数は「だいたいの値」を表すもので、`0.1 + 0.2` がちょうど `0.3` にならないなど、誤差が出ます。言語処理系で小数リテラルを実装するときは、この誤差の存在を前提に設計します。 文字は前章で触れたとおり `char` で表します。Cの世界では、`char` は実は小さな整数でもあります。`'A'` は文字コード（多くの環境ではASCIIの65）という整数として扱われ、`'A' + 1` は `'B'` の文字コードになります。字句解析で「この文字は数字か？」を `c >= '0' && c <= '9'` のように判定できるのは、文字が整数だからです。 ## 暗黙の型変換と明示の型変換 異なる型の値が混ざった式では、型の**変換（conversion）**が起こります。Cはしばしば自動で変換します。これを**暗黙の型変換（implicit conversion）**と呼びます。たとえば `int` と `double` を足すと、`int` のほうが `double` に変換されてから計算されます。 自分の意思で変換するときは、**キャスト（cast）**と呼ぶ書き方を使います。 ```c int a = 7; int b = 2; double result = (double)a / b; // a を double に変換してから割る → 3.5 ``` `(double)a` が「`a` を `double` として扱え」という明示の変換です。これがないと `a / b` は整数の割り算になって `3` に切り捨てられ、その後 `double` にしても `3.0` のままです。前章で触れた `/` の落とし穴は、こうしたキャストで回避できます。 > [!NOTE] > 暗黙の変換は便利な反面、意図しない情報の欠落を招くことがあります。`double` を `int` に代入すると小数点以下が捨てられます。コンパイラの `-Wconversion` 警告を使うと、危ない変換を知らせてくれます。本書の方針どおり、警告は積極的に拾って消していきましょう。 ## この章のまとめ - 型とは「ビット列をどう解釈し、どれだけの幅を取り、何ができるか」を決める情報。 - 整数型の幅は環境依存。移植性が要るなら `int32_t` などの固定幅整数型を使う。 - 符号なし整数の回り込みや、整数除算の切り捨てに注意する。 - 型変換には暗黙のものと明示（キャスト）のものがある。警告を活用する。 次章では、C言語最大の山場であるポインタに挑みます。型の話がここでも土台になります。 # ポインタとメモリ ポインタはC言語でいちばん難しいと言われる概念です。しかし言語処理系を書くなら避けて通れません。構文木のノードをつなぐのも、文字列を扱うのも、関数を値として渡すのも、すべてポインタが土台になります。この章では、メモリのモデルから始めて、ポインタを「こわくない道具」にしていきます。 ## メモリは巨大な番地付きの棚である ポインタを理解する第一歩は、**メモリ（memory）**のイメージを持つことです。コンピュータのメモリは、1バイトずつ区切られた巨大な棚だと考えてください。それぞれの区画には**番地（address、アドレス）**という通し番号が振られています。0番地、1番地、2番地……と続く、ロッカーの番号のようなものです。 変数を宣言すると、その型に応じた区画がメモリ上に確保されます。`int x = 42;` と書くと、どこかの番地に4バイト分の場所が取られ、そこに `42` が書き込まれます。 ```mermaid graph LR subgraph メモリ A["番地 1000
42"] B["番地 1004
..."] C["番地 1008
..."] end X["変数 x"] -.指している.-> A ``` **ポインタとは、この「番地」を値として持つ変数**です。普通の変数が「数値そのもの」を持つのに対し、ポインタは「値がどこにあるか（番地）」を持ちます。住所を書いたメモのようなものだと考えるとよいでしょう。メモには家そのものは入っていませんが、それをたどれば家にたどり着けます。 ## アドレス演算子と間接参照演算子 ポインタを扱う基本の道具は二つです。**アドレス演算子 `&`** と、**間接参照演算子 `*`** です。 ```c #include int main(void) { int x = 42; int *p = &x; // p は「x の番地」を持つポインタ printf("x の値 : %d\n", x); // 42 printf("x の番地 : %p\n", (void *)p); // 例: 0x7ffd... printf("p の指す先: %d\n", *p); // 42（p をたどって読む） *p = 100; // p の指す先（＝x）に 100 を書く printf("x の値 : %d\n", x); // 100 に変わっている return 0; } ``` 一つずつ読み解きましょう。`int *p` は「`p` は `int` を指すポインタだ」という宣言です。型の `int` に `*` を付けると「それを指すポインタ型」になります。`&x` は「`x` の番地」を取り出す式で、これを `p` に入れています。 `*p` は「`p` が指す先の値」を表します。これを**間接参照（dereference）**と呼びます。`*p` は読み出しにも書き込みにも使えて、`*p = 100;` と書くと `p` が指す場所（つまり `x`）に `100` が書き込まれます。`p` 自身は番地を持ったままで、その指す先を通して `x` を書き換えているのです。 > [!NOTE] > `*` という記号は、宣言（`int *p`）と式（`*p`）で見た目が同じですが、役割が違います。宣言の `*` は「ポインタ型である」という印、式の `*` は「指す先をたどる」という操作です。最初は紛らわしいですが、文脈で読み分けます。 ## なぜポインタが必要なのか 「値そのものを使えばいいのに、なぜわざわざ番地を介すのか」と思うかもしれません。言語処理系づくりの観点から、ポインタが要る理由は大きく三つあります。 第一に、関数に変更を持ち帰らせるためです。Cでは、関数に値を渡すとその**コピー**が渡されます（**値渡し**）。だから関数の中で引数を書き換えても、呼び出し元の変数は変わりません。呼び出し元の変数そのものを書き換えてほしいときは、その番地（ポインタ）を渡します。 ```c void increment(int *n) { *n = *n + 1; // 指す先を書き換える } int main(void) { int count = 5; increment(&count); // count の番地を渡す // count はここで 6 になっている return 0; } ``` 第二に、大きなデータを安く渡すためです。構文木のノードのように大きな構造体を関数に渡すたびにコピーしていては、時間もメモリも無駄になります。番地（多くの環境で8バイト）だけを渡せば、中身はコピーせず共有できます。 第三に、データ構造を組み立てるためです。木やリストのように「あるノードが別のノードを指す」構造は、ポインタなしには作れません。これは後の章で構文木を作るときの核心になります[](#cite:appel1998)。 ## ヌルポインタ ポインタは「どこも指していない」状態を表せます。それが**ヌルポインタ（null pointer）**で、`NULL` という名前で書きます（`` などで定義されています）。 ```c int *p = NULL; // いまは何も指していない if (p != NULL) { printf("%d\n", *p); // 指す先があるときだけ読む } ``` ヌルポインタは「まだ値がない」「探したが見つからなかった」といった状況を表すのに使います。たとえば「シンボルテーブルから変数を探したが未定義だった」ときに `NULL` を返す、という設計はよくあります。 > [!CAUTION] > ヌルポインタを間接参照する（`*p` で `NULL` をたどる）と、プログラムは異常終了します（多くの環境で「セグメンテーション違反 / Segmentation fault」というエラーになります）。ポインタをたどる前に `NULL` でないかを確かめるのは、安全なCプログラムの基本です[](#cite:seacord2020)。 ## 配列とポインタの関係 **配列（array）**は、同じ型の値をメモリ上に連続して並べたものです。 ```c int nums[5] = {10, 20, 30, 40, 50}; printf("%d\n", nums[2]); // 30（添字は 0 から数える） ``` `nums[2]` の `[2]` が**添字（index）**で、先頭を `0` として数えます。だから3番目の要素は `nums[2]` です。 Cでは配列とポインタが深く結びついています。配列の名前は、多くの場面で先頭要素の番地として振る舞います。そのため `nums[i]` は、内部的には「先頭の番地から `i` 個分ずらした場所をたどる」という計算になっています。この「番地をずらす」計算を**ポインタ演算（pointer arithmetic）**と呼びます。 ```c int *p = nums; // 配列名は先頭の番地。p は nums[0] を指す printf("%d\n", *p); // 10 printf("%d\n", *(p + 2)); // 30 … nums[2] と同じ意味 ``` `p + 2` は「2バイト先」ではなく「`int` 2個分先」を指します。ポインタ演算は型の幅を考慮してくれるのです。この性質は、字句解析で文字列を1文字ずつ読み進めるときなどに自然に使われます。 > [!NOTE] > 「振る舞います」と書いたとおり、配列とポインタは**同じものではありません**。違いがはっきり出るのが `sizeof` です。`sizeof(nums)` は配列全体のバイト数（`int` 5個分）を返しますが、`sizeof(p)` はポインタ1個分のサイズです。また、配列を関数の引数に渡すと、関数が受け取るのは配列ではなく先頭の番地（ポインタ）です。だから、関数の中では `sizeof` で要素数を知ることはできず、長さは別の引数で渡すのが C の定石です（`void f(int *a, int len)` のように）。 > [!WARNING] > 配列の範囲外をアクセスしてもCは止めてくれません。`nums[5]` や `nums[100]`（要素数5の配列に対して）を読み書きすると、関係ないメモリを壊し、原因のわかりにくいバグになります。これを**バッファオーバーフロー**と呼び、深刻な不具合やセキュリティ問題の原因になります。添字が範囲内かは自分で管理する必要があります。 ## 文字列と char 配列 Cには専用の「文字列型」がありません。**文字列は `char` の配列**として表され、末尾に `'\0'`（**ヌル文字**、値が0の文字）を置いて「ここで終わり」を示します。 ```c char word[] = "let"; // 'l' 'e' 't' '\0' の4バイトが並ぶ ``` `"let"` と書くと文字3個に見えますが、終端の `'\0'` を含めてメモリ上は4バイトです。文字列を扱う関数（`strlen` で長さを測る、`strcmp` で比較する、など）は、この `'\0'` を目印に文字列の終わりを判断します。言語処理系の字句解析では、ソースコードをこの「char の並び」として受け取り、先頭からポインタで読み進めていきます。 > [!WARNING] > 上の例の `char word[] = "let";` は、リテラルの中身を配列にコピーしているので、`word[0] = 'L';` のように書き換えられます。一方、`char *s = "let";` と書くと、`s` はプログラムに埋め込まれた**文字列リテラルそのもの**を指します。このリテラルを書き換えること（`s[0] = 'L';`）は未定義動作で、多くの環境ではクラッシュします。「書き換えたいならコピー（配列）、読むだけならポインタ」と覚えてください。読むだけのつもりのポインタには `const char *s` と書いておくと、うっかり書き換えようとしたときにコンパイラが止めてくれます（const の章で詳しく扱います）。 ## 言語処理系でトークンを読み進める ここまでの道具を組み合わせると、字句解析の最初の一歩が書けます。次の関数は、文字列の中の空白を読み飛ばし、最初の非空白文字を指すポインタを返します。 ```c #include // p が指す位置から空白を飛ばし、次の文字の位置を返す const char *skip_spaces(const char *p) { while (*p == ' ' || *p == '\t') { p++; // ポインタを1文字進める } return p; } int main(void) { const char *src = " 1 + 2"; const char *p = skip_spaces(src); printf("最初の文字は '%c'\n", *p); // '1' return 0; } ``` `while (*p == ' ' || ...)` は「`p` が指す文字が空白である間」くり返す、という意味です。`p++` でポインタを1文字進め、空白でない文字に出会ったらループを抜けます。最後に、その位置を指すポインタを返します。ソースコード全体を先頭から終端までこうやって舐めていくのが、字句解析の骨組みです[](#cite:nystrom2021)。`const` という見慣れない語が付いていますが、これは「指す先を書き換えない」という約束で、専用の章（[](const.md)）で詳しく扱います。 ## この章のまとめ - メモリは番地付きの棚であり、ポインタはその番地を値として持つ。 - `&` で番地を取り、`*` で指す先をたどる（間接参照）。 - ポインタは「関数に変更を持ち帰らせる」「大きなデータを安く渡す」「データ構造を組む」ために要る。 - どこも指さないポインタは `NULL`。たどる前に確認する。 - 配列とポインタは地続きで、添字アクセスはポインタ演算で説明できる。範囲外アクセスに注意。 - 文字列は `'\0'` 終端の `char` 配列。字句解析はこれをポインタで読み進める。 ポインタを手にしたことで、次の部では複雑なデータ構造（構文木や値の表現）を組み立てられるようになります。 # 第II部　データを形にする 言語処理系の仕事の半分は「データの表現」です。トークン、構文木（AST）、実行時の値、シンボルテーブル、どれもメモリ上のデータ構造として表現しなければなりません。 この部では、複数の値をまとめる構造体（`struct`）、同じ場所を複数の解釈で使い分ける共用体（`union`）、関数そのものをデータとして扱う関数ポインタ、変更しないことを宣言する `const`、そして必要なときにメモリを確保する動的メモリ管理を学びます。これらを組み合わせると、構文木のような複雑なデータ構造がきれいに書けるようになります。 # 複数の値をひとまとめにする構造体 言語処理系では、「いくつかの値がセットで意味を持つ」場面が無数にあります。トークンは「種類」と「位置」と「文字列」をセットで持ちますし、構文木のノードは「演算子」と「左の子」と「右の子」をセットで持ちます。こうした「関連する値の束」を表すのが**構造体（struct）**です。この章では構造体を学び、それを使って構文木の骨組みを作るところまで進みます。 ## なぜ構造体が要るのか たとえばトークンを表すのに、種類・行番号・文字列という三つの情報を別々の変数で持つとどうなるでしょう。 ```c int token_kind; int token_line; char *token_text; ``` トークンが100個あれば、これらを100組ばらばらに管理することになります。「3番目のトークン」の三つの情報がどれとどれなのかを取り違えれば、すぐにバグです。**関連する値は、一つの箱にまとめて名前を付けたほうがよい**。それが構造体です。 ```c struct Token { int kind; // トークンの種類 int line; // 何行目にあったか char *text; // 元の文字列 }; ``` `struct Token { ... };` で「`Token` という名前の構造体型」を定義しています。中の `kind`、`line`、`text` を**メンバ（member）**と呼びます。これで「トークン1個分」を表す新しい型ができました。末尾のセミコロンを忘れやすいので注意してください。 ## 構造体の宣言と初期化とメンバアクセス 定義した構造体型は、ふつうの型と同じように変数を作れます。 ```c struct Token t; // Token 型の変数 t t.kind = 1; // メンバに代入（ドットでアクセス） t.line = 3; t.text = "let"; printf("種類=%d 行=%d 文字列=%s\n", t.kind, t.line, t.text); ``` メンバには `.`（ドット）でアクセスします。`t.kind` は「`t` の `kind` メンバ」という意味です。宣言と同時にまとめて初期化することもできます。 ```c struct Token t = { .kind = 1, .line = 3, .text = "let" }; ``` `.kind = 1` のように**メンバ名を指定する初期化**（指示付き初期化子）は、どのメンバに何を入れているかが一目でわかるのでおすすめです。指定しなかったメンバは `0`（ポインタなら `NULL`）で埋められます。 > [!TIP] > 構造体は、メモリ上ではメンバが順番に並んだ「一続きの領域」です。ただしCPUが効率よく読めるよう、メンバの間に**詰め物（パディング）**と呼ばれる隙間が入ることがあります。そのため `sizeof(struct Token)` は、各メンバのサイズの単純な合計より大きくなることがあります。メモリを節約したい言語処理系では、メンバの並べ方でサイズが変わることを知っておくと役に立ちます[](#cite:seacord2020)。 ## typedefと組み合わせて短く書く ここまで見てきたように、`struct Token` のように毎回 `struct` を書くのは少し冗長です。`typedef` キーワード（詳しくは後の章（[](typedef.md)）で扱います）を使うと、すっきりします。 ```c typedef struct Token { int kind; int line; char *text; } Token; // これで「Token」だけで使える Token t; // struct Token t; と書かなくてよい ``` `typedef struct Token { ... } Token;` は、構造体の定義と別名付けを同時に行う書き方です。以後は `Token` と書くだけで済みます。本書では、これ以降この書き方を標準とします。多くの実際の言語処理系も、この `typedef struct` のスタイルを採用しています[](#cite:nystrom2021)。 ## ポインタ経由でメンバを取り出すアロー演算子 構造体は大きくなりがちなので、関数に渡すときは前章で学んだとおり**ポインタで渡す**のが定石です。コピーを避けられますし、関数から中身を書き換えることもできます。 ポインタ経由でメンバにアクセスするときは、専用の**アロー演算子 `->`** を使います。 ```c void print_token(const Token *t) { // (*t).kind と書く代わりに t->kind と書ける printf("種類=%d 行=%d\n", t->kind, t->line); } int main(void) { Token t = { .kind = 1, .line = 3, .text = "let" }; print_token(&t); // 番地を渡す return 0; } ``` `t->kind` は `(*t).kind`、すなわち「`t` が指す構造体の `kind` メンバ」と同じ意味です。ポインタをたどってからメンバを取り出す操作はあまりに頻出するので、`->` という短い記法が用意されているのです。構造体を扱うコードでは、`.` よりむしろ `->` を見かけることのほうが多いでしょう。 > [!NOTE] > `t.kind`（ドット）は構造体そのものに対して、`t->kind`（アロー）は構造体へのポインタに対して使います。どちらを使うべきかは「手元にあるのが構造体本体か、ポインタか」で決まります。コンパイラはこの取り違えを警告してくれるので、迷ったら一度間違えてみて、エラーメッセージから学ぶのも手です。 ## 自分自身を指す構造体で木をつくる 構造体の真価は、**メンバに「自分と同じ型へのポインタ」を持てる**ことで発揮されます。これにより、木やリストのような再帰的なデータ構造が作れます。言語処理系の核心である構文木（AST）を、いよいよ表現してみましょう。 二項演算（`左 演算子 右`）のノードを考えます。たとえば `1 + 2` なら、`+` のノードが左に `1`、右に `2` をぶら下げます。「左」と「右」もまたノードなので、メンバの型は「ノードへのポインタ」になります。 ```c typedef struct Node { int op; // 演算子の種類（'+' '-' など。今は文字コードで表す） int value; // 葉（数値）のときの値 struct Node *left; // 左の子ノードへのポインタ struct Node *right; // 右の子ノードへのポインタ } Node; ``` ここで `left` と `right` の型が `struct Node *`、つまり「`Node` を指すポインタ」になっている点が肝心です。**構造体の中で、まだ定義の途中である自分自身を「ポインタ」としてなら参照できる**のです（本体をそのまま入れることはできません。大きさが無限になってしまうからです）。`typedef` 後の `Node` ではなく `struct Node` と書いているのも、定義の途中だからです。 数値の葉ノードと、演算ノードを作る関数を用意します。 ```c #include // 数値（葉）ノードを作る Node *new_number(int value) { Node *n = malloc(sizeof(Node)); // ノード1個分のメモリを確保 n->op = 0; // 0 は「葉」を表すことにする n->value = value; n->left = NULL; n->right = NULL; return n; } // 二項演算ノードを作る Node *new_binary(int op, Node *left, Node *right) { Node *n = malloc(sizeof(Node)); n->op = op; n->value = 0; n->left = left; n->right = right; return n; } ``` `malloc`（メモリ確保）という新顔が出てきました。これはプログラムの実行中に必要なだけメモリを借りる関数で、専用の章（[](memory.md)）で詳しく扱います。いまは「ノード1個分の場所を借りて、その番地を返してくれる」とだけ理解すれば十分です。`sizeof(Node)` で必要なバイト数を渡しています。 これらを使えば `1 + 2 * 3` の構文木が組み立てられます。 ```c // 1 + (2 * 3) を表す木を作る Node *tree = new_binary('+', new_number(1), new_binary('*', new_number(2), new_number(3))); ``` 関数の呼び出しが入れ子になっているのが、そのまま木の形に対応しています。`+` ノードの右の子が `*` ノードになっている様子が、コードからも読み取れます。 ## 木をたどって計算する 構文木ができたら、それを根からたどって計算できます。木のような再帰的データは、**再帰関数**（自分自身を呼び出す関数）で処理するのが自然です。 ```c int eval(const Node *n) { if (n->op == 0) { // 葉なら、その値を返す return n->value; } int l = eval(n->left); // 左の子を計算（再帰） int r = eval(n->right); // 右の子を計算（再帰） switch (n->op) { case '+': return l + r; case '-': return l - r; case '*': return l * r; case '/': return l / r; } return 0; // ここには来ない想定 } ``` `eval` は「ノードを受け取り、その部分木を計算した値を返す」関数です。葉（`op == 0`）ならその値をそのまま返し、そうでなければ左右の子をそれぞれ `eval` で計算してから、演算子に応じて組み合わせます。`switch` 文は、`n->op` の値ごとに処理を振り分ける制御構造で、たくさんの `if` を並べるより読みやすくなります。各 `case` の後の値が一致したところが実行されます。 `eval(tree)` を呼べば、さきほど作った `1 + 2 * 3` の木から `7` が得られます。これがインタプリタの中核、すなわち「**木をたどって意味を計算する**」処理（**木構造インタプリタ / tree-walking interpreter**）の最小形です[](#cite:nystrom2021)。構造体とポインタと再帰だけで、もう小さなインタプリタの心臓ができてしまいました。 > [!IMPORTANT] > `malloc` で借りたメモリは、使い終わったら返す（解放する）必要があります。上の例では木を作りっぱなしで解放していません。小さなプログラムでは問題になりませんが、長く動く言語処理系では「借りたまま返さない」ことが積み重なってメモリを食いつぶします。これを**メモリリーク**と呼び、[](memory.md)で対処法を扱います。 ## この章のまとめ - 構造体は、関連する複数の値（メンバ）を一つの型にまとめる。 - メンバには `.`（本体）または `->`（ポインタ経由）でアクセスする。 - `typedef struct` で `struct` を省ける書き方が定番。 - メンバに「自分自身へのポインタ」を持たせると、木やリストが作れる。 - 構文木は構造体で表し、再帰関数でたどって計算できる。これが木構造インタプリタの核。 次章では、ノードの種類によって持つべき情報が違う、という問題をきれいに解く**共用体**を学びます。 # 同じ場所を使い分ける共用体 前章の構文木ノードには、少しもったいない点がありました。数値の葉ノードは `value` しか使わず `left`／`right` は無駄になり、演算ノードは逆に `value` を使いません。種類によって必要なメンバが違うこの状況を、きれいに表すのが**共用体（union）**です。共用体は言語処理系で「値」や「ノード」を表現するときの定番道具で、この章はその使いこなしを扱います。 ## メンバが場所を共有する共用体 構造体は、すべてのメンバがそれぞれ別の場所を占めました。**共用体は、すべてのメンバが同じ場所を共有します**。 ```c union Number { int as_int; // 整数として見たときの値 double as_double; // 小数として見たときの値 }; ``` 見た目は構造体（`struct`）とそっくりで、`struct` を `union` に変えただけです。しかし意味はまったく違います。`union Number` のサイズは、`as_int`（4バイト）と `as_double`（8バイト）の合計ではなく、いちばん大きいメンバに合わせた8バイトです。`as_int` と `as_double` は、その同じ8バイトを重ねて使います。 ```mermaid graph TD subgraph struct["struct（別々の場所）"] S1["as_int
4バイト"] S2["as_double
8バイト"] end subgraph union["union（同じ場所を共有）"] U1["as_int / as_double
同じ8バイト"] end ``` これは[](types.md)で述べた「型とはビットの解釈の仕方」という話と直結します。共用体は、**同じビット列を、どのメンバの型として解釈するかを選べる**仕組みなのです。 ```c union Number n; n.as_int = 65; printf("%d\n", n.as_int); // 65 ``` ## 書いたのと違うメンバを読むと 共用体には、知らずに使うと痛い目を見る性質があります。**あるメンバに書き込んだあと、別のメンバから読むと、結果は意味をなしません**。 ```c union Number n; n.as_double = 3.14; printf("%d\n", n.as_int); // 3 ではなく、ビットを int と誤解した謎の値 ``` `as_double` として書いた `3.14` のビット列を、`as_int` として読み解いてしまうので、出てくるのはでたらめな整数です。共用体は「いま、どのメンバとして使っているか」を自分で覚えておかなければならないのです。共用体自身はそれを記録してくれません。 > [!CAUTION] > 「最後にどのメンバに書いたか」を取り違えて読むのは、共用体にまつわる典型的なバグです。Cの規格上も、別メンバとして読む動作の多くは安全が保証されていません[](#cite:iso2018)。この問題への答えが、次に説明する「タグ付き共用体」です。共用体は単独で使うより、常に「種類を覚えるための印」とセットで使う、と心得てください。 ## 種類の印を添えるタグ付き共用体 解決策はシンプルです。共用体と一緒に、「いまどの種類か」を表す**タグ（tag）**を構造体に同居させます。これを**タグ付き共用体（tagged union）**と呼びます。言語処理系で「いろいろな種類の値」を一つの型で表すときの、ほぼ標準的なやり方です。 実行時の値が「整数」か「小数」か「真偽値」のいずれかを取る言語を考えましょう。 ```c typedef enum { VAL_INT, VAL_DOUBLE, VAL_BOOL, } ValueType; typedef struct { ValueType type; // タグ：いまどの種類か union { int64_t as_int; // type == VAL_INT のとき有効 double as_double; // type == VAL_DOUBLE のとき有効 int as_bool; // type == VAL_BOOL のとき有効 } u; // 種類ごとの中身（場所を共有） } Value; ``` 新顔の `enum`（**列挙型 / enumeration**）は、名前付きの整数定数をまとめて定義する仕組みです。ここでは `VAL_INT` が `0`、`VAL_DOUBLE` が `1`、`VAL_BOOL` が `2` という整数に自動で割り当てられます。数字を直接書くより、`VAL_INT` という名前で書いたほうが意図が明確で、間違いも減ります。これがタグの正体です。 構造体 `Value` は、タグ `type` と、種類ごとの中身を入れる共用体 `u` の二つを持ちます。「`type` を見れば、`u` のどのメンバが有効かがわかる」という約束で運用します。`int64_t` は[](types.md)で学んだ固定幅整数型です。 ## タグ付き共用体を安全に使う タグ付き共用体は、「作るときにタグも一緒に立てる」「使うときはタグを見てから対応するメンバを読む」という二つの規律で安全に使えます。値を作る関数を用意しましょう。 ```c Value make_int(int64_t x) { Value v; v.type = VAL_INT; // タグを立て、 v.u.as_int = x; // 対応するメンバに書く return v; } Value make_double(double x) { Value v; v.type = VAL_DOUBLE; v.u.as_double = x; return v; } Value make_bool(int b) { Value v; v.type = VAL_BOOL; v.u.as_bool = b; return v; } ``` タグの設定とメンバへの書き込みを必ずセットで行うのがコツです。これらの関数を窓口にすれば、「タグだけ立てて中身を入れ忘れる」事故を防げます。 使う側では、タグで分岐してから読みます。値を画面に表示する関数を書いてみます。 ```c #include #include // bool 型を使うため void print_value(Value v) { switch (v.type) { case VAL_INT: printf("%lld\n", (long long)v.u.as_int); break; case VAL_DOUBLE: printf("%g\n", v.u.as_double); break; case VAL_BOOL: printf("%s\n", v.u.as_bool ? "true" : "false"); break; } } ``` `switch (v.type)` でタグを調べ、その種類に対応するメンバだけを読んでいます。`VAL_INT` の枝では `as_int` しか触りません。こうすれば「書いたのと違うメンバを読む」事故は起きません。各 `case` の末尾の `break` は「ここで `switch` を抜ける」という意味で、これを忘れると次の `case` まで実行が流れ落ちてしまうので注意してください。 > [!TIP] > `switch` で `enum` を分岐するとき、`default:` をあえて書かずに全種類を `case` で並べると、後で種類を増やしたときにコンパイラが「`VAL_NIL` の場合が抜けているよ」と警告してくれることがあります（`-Wswitch` 系の警告）。本書の方針どおり警告を活用するなら、これは種類の数え漏れを見つける良い仕掛けになります。 ## なぜタグ付き共用体が言語処理系に効くのか タグ付き共用体は、言語処理系のあらゆる場所に現れます。代表的なのは次の二つです。 ひとつは、いま見た**実行時の値（runtime value）**の表現です。動的に型が決まる言語では、変数に入る値が整数か文字列かオブジェクトか、実行してみないとわかりません。一つの `Value` 型でそれらすべてを表すために、タグ付き共用体がうってつけなのです[](#cite:nystrom2021)。 もうひとつは、**構文木ノードの表現**です。前章の `Node` は数値ノードと演算ノードを同じ構造体で表し、未使用のメンバが無駄になっていました。タグ付き共用体を使えば、ノードの種類ごとに必要なメンバだけを持たせ、メモリの無駄をなくせます。 ```c typedef enum { ND_NUM, ND_BINARY } NodeKind; typedef struct Node { NodeKind kind; union { int64_t value; // ND_NUM のとき struct { // ND_BINARY のとき int op; struct Node *left; struct Node *right; } binary; } u; } Node; ``` 数値ノードは `u.value` だけを、演算ノードは `u.binary` 一式だけを使います。共用体のおかげで、両者は同じ場所を共有し、ノード1個のサイズは「いちばん大きい種類」に抑えられます。コンパイラの教科書でも、構文木をこの形（種類タグ＋共用体）で表す例が数多く紹介されています[](#cite:appel1998)。 ## 値を使ってインタプリタを育てる 前章のインタプリタは整数しか返せませんでした。`Value` を返すようにすれば、整数と小数が混ざった計算もできます。考え方の要点だけ示します。 ```c Value eval(const Node *n) { if (n->kind == ND_NUM) { return make_int(n->u.value); } Value l = eval(n->u.binary.left); Value r = eval(n->u.binary.right); // ここで l と r のタグを見て、整数同士なら整数演算、 // 片方でも小数なら小数演算、と振り分ける（前章 basics.md の型変換の話が効いてくる） if (l.type == VAL_INT && r.type == VAL_INT) { switch (n->u.binary.op) { case '+': return make_int(l.u.as_int + r.u.as_int); /* 他の演算子も同様 */ } } /* 小数が絡む場合の処理は省略 */ return make_int(0); } ``` 左右の子の**タグを見て**、整数同士か、小数が絡むかを判断し、適切な演算を選びます。これはまさに、動的型付き言語のインタプリタが実行時に行っている判断そのものです。「タグを見て分岐する」というこのパターンが、処理系のあちこちで繰り返されることになります。 > [!NOTE] > このタグ分岐は柔軟な反面、実行のたびにコストがかかります。あらゆる演算の前に「これは何型か？」を確かめるからです。このコストをどう減らすかは、性能を追い求めるインタプリタの中心的な課題で、[](optimization-advanced.md)で再び取り上げます。 ## この章のまとめ - 共用体はすべてのメンバが同じメモリを共有し、サイズは最大メンバに合わせる。 - 「書いたのと違うメンバを読む」と結果は無意味。共用体は単独では危険。 - タグ（多くは `enum`）を添えた**タグ付き共用体**にすれば安全に使い分けられる。 - 作るときにタグを立て、使うときはタグで分岐してから読む、という規律を守る。 - 実行時の値と構文木ノードの表現は、どちらもタグ付き共用体の代表的な使いどころ。 次章では、関数そのものをデータとして扱う**関数ポインタ**に進みます。タグで分岐するかわりに「関数の表」を引く、という別の設計が見えてきます。 # 処理を値として持ち運ぶ関数ポインタ これまで、ポインタは「データのありか」を指していました。実は、ポインタは関数のありかも指せます。それが**関数ポインタ（function pointer）**です。関数を値として変数に入れたり、引数で渡したり、表に並べたりできるようになります。言語処理系では、この道具が「組み込み関数の登録」や「命令ディスパッチ」といった場面で働きます。 ## 関数もメモリ上にある [](pointers.md)で「変数はメモリ上のどこかに置かれ、番地を持つ」と学びました。実は関数も同じです。コンパイルされた関数の機械語は、メモリ上のどこかに置かれ、先頭の番地を持っています。**関数ポインタとは、その「関数の先頭番地」を持つポインタ**です。番地さえあれば、そこにジャンプして実行できます。これが関数を値として扱える理由です。 まず、ポインタに入れたい関数たちを用意します。どれも「`int` を二つ受け取り `int` を返す」同じ形にそろえておきます。 ```c int add(int a, int b) { return a + b; } int sub(int a, int b) { return a - b; } int mul(int a, int b) { return a * b; } ``` ## 関数ポインタの宣言の読み方 関数ポインタの宣言は、Cの文法の中でもとっつきにくい部類です。落ち着いて読み解きましょう。 ```c int (*fp)(int, int); ``` これは「`fp` は、`int` を二つ受け取り `int` を返す関数を指すポインタである」という宣言です。内側から読むのがコツです。`(*fp)` で「`fp` はポインタ」、その後ろの `(int, int)` で「指す先は2引数の関数」、先頭の `int` で「その関数は `int` を返す」となります。`(*fp)` の括弧は必須で、外すと意味が変わってしまいます（`int *fp(int, int)` は「`int *` を返す関数の宣言」になってしまう）。 この長い型は、`typedef`（詳しくは[](typedef.md)）で別名を付けると一気に読みやすくなります。 ```c // 「int を二つ受け取り int を返す関数」へのポインタ型に BinOp という名前を付ける typedef int (*BinOp)(int, int); BinOp op = add; // 関数 add の番地を入れる（& は省略できる） int r = op(3, 4); // op を通して add を呼ぶ → 7 ``` 関数名 `add` は、それ自体が「関数の番地」として振る舞います（配列名が先頭要素の番地になったのと同じ感覚です）。だから `op = add;` で番地を代入でき、`op(3, 4)` と書けば、`op` が指す関数（いまは `add`）が呼ばれます。`typedef` のおかげで、関数ポインタが普通の変数のように扱えています。 > [!NOTE] > 関数ポインタを使うときは、**指す先の関数の形（引数と返り値の型）が一致している**必要があります。`BinOp` には「`int` を二つ受け取り `int` を返す」関数しか入れられません。形の違う関数を無理に入れると、コンパイラが警告を出すか、実行時に壊れます。`const`（[](const.md)）と同じく、型は約束事として働きます。 ## 表を引いて処理を選ぶディスパッチテーブル 関数ポインタの代表的な使い道が、**ディスパッチテーブル（dispatch table）**です。「種類」と「処理」を表（配列）で対応づけておき、種類で表を引いて対応する関数を呼ぶ、という手法です。 前章までのインタプリタでは、演算子ごとの処理を `switch` で振り分けていました。これを関数ポインタの表に置き換えてみましょう。まず、演算子の文字を `0`〜`3` の番号に対応させ、その番号で表を引きます。 ```c typedef int (*BinOp)(int, int); // 番号 → 処理 の対応表 BinOp op_table[4] = { add, // 0 番: 加算 sub, // 1 番: 減算 mul, // 2 番: 乗算 div_, // 3 番: 除算（div は標準ライブラリと名前が衝突するので別名に） }; int apply(int op_index, int a, int b) { return op_table[op_index](a, b); // 表を引いて、得た関数を呼ぶ } ``` `op_table[op_index]` で関数ポインタを取り出し、その直後に `(a, b)` を付けて呼び出しています。`switch` のように分岐を書き並べる必要がなく、表に一行足すだけで演算子を増やせます。種類が増えても表に追記するだけでよく、この拡張のしやすさが、ディスパッチテーブルの利点です。インタプリタの命令実行ループをこの方式で組むのは、古くから知られた効率化の定番でもあります[](#cite:bell1973)。 `switch` 方式とディスパッチテーブル方式は、どちらが絶対に優れるというものではありません。 | 観点 | `switch` 方式 | ディスパッチテーブル方式 | |------|--------------|------------------------| | 読みやすさ | 処理がその場に並ぶので追いやすい | 表と関数本体が離れる | | 拡張のしやすさ | `case` を足す | 表に1行＋関数を足す | | 種類が動的に増える場合 | 不向き（再コンパイルが要る） | 向く（実行中に表を書き換えられる） | 最後の行が要点です。次に見る「組み込み関数の登録」のように実行中に処理を足したい場面では、`switch` では手が出ません。関数ポインタの表なら、実行中に中身を差し替えられます。 ## 組み込み関数を登録する 多くの言語には、`print` や `len` のような**組み込み関数（built-in function）**が用意されています。言語処理系の中では、これらを「名前」と「実体（C言語の関数）」の対応として持っておき、ユーザーのプログラムがその名前を呼んだら対応するC関数を実行します。この対応づけに、関数ポインタが使えます。 ```c #include #include typedef Value (*Builtin)(Value arg); // 組み込み関数の形（Value は union.md の型） typedef struct { const char *name; // 言語側から見た名前 Builtin fn; // 対応する C 関数 } BuiltinEntry; // 実体となる C 関数たち Value builtin_print(Value arg) { print_value(arg); // union.md で作った表示関数を使う return make_int(0); } Value builtin_abs(Value arg) { int64_t x = arg.u.as_int; return make_int(x < 0 ? -x : x); } // 名前 → 関数 の登録表 BuiltinEntry builtins[] = { { "print", builtin_print }, { "abs", builtin_abs }, }; // 名前で表を引いて呼び出す Value call_builtin(const char *name, Value arg) { for (int i = 0; i < 2; i++) { if (strcmp(builtins[i].name, name) == 0) { return builtins[i].fn(arg); // 見つけた関数を呼ぶ } } printf("未定義の関数: %s\n", name); return make_int(0); } ``` `BuiltinEntry` は「名前」と「関数ポインタ」を組にした構造体です（[](struct.md)の応用です）。その配列 `builtins[]` が登録表になります。`call_builtin` は、与えられた名前を `strcmp`（文字列の比較。等しければ `0` を返す）で表と突き合わせ、一致した行の `fn` を呼び出します。 この設計の良いところは、**組み込み関数を足す作業が「表に一行加える」だけ**で済むことです。新しい関数 `builtin_sqrt` を書いて `{ "sqrt", builtin_sqrt }` を表に並べれば、もう言語の中から `sqrt` が呼べます。インタプリタの本体には一切手を入れません。関数ポインタが「処理を値として持ち運べる」からこそ、こうした拡張可能な設計が書けます[](#cite:nystrom2021)。 > [!TIP] > 構造体（[](struct.md)）のメンバに関数ポインタを持たせると、データと「そのデータに対する操作」を一つにまとめられます。これはオブジェクト指向言語の「メソッド」を、Cで手作りするときの基本テクニックです。言語処理系で「オブジェクトの型ごとにふるまいを変える」とき（**仮想テーブル / vtable** と呼ばれる仕組み）も、根っこはこの関数ポインタの表です。 ## 標準ライブラリでの関数ポインタ 関数ポインタは、特殊な道具ではありません。C標準ライブラリにも、関数ポインタを受け取る関数があります。代表が `qsort` です。 ```c #include int compare_int(const void *a, const void *b) { int x = *(const int *)a; int y = *(const int *)b; return (x > y) - (x < y); // x>y なら正、x [!TIP] > `typedef` は新しい型を作るわけではありません。あくまで既存の型の**あだ名**です。`typedef int Meters; typedef int Seconds;` としても、`Meters` と `Seconds` は中身が同じ `int` なので、取り違えてもコンパイラは怒りません。型による厳密な区別がほしい場合は、構造体で包む手があります。 ## この章のまとめ - `typedef` は既存の型に別名を付け、意図を伝え、後からの差し替えを容易にする。 - 構造体・共用体・関数ポインタのような複雑な型に短い名前を付けるのに特に有効。 - 別名を作るだけで新しい型ではないため、コンパイラは型の取り違えを検出しない。 次章では、これまで何度か顔を出してきた `const`（「書き換えない」という約束）を扱います。 # constという書き換えないための約束 これまでの章で、`const char *p` のような書き方が何度か登場しました。`const`（コンスト、「定数の」の意）は「この値は書き換えない」とコンパイラに宣言するキーワードです。一見すると地味ですが、`const` を使いこなすと、バグを未然に防ぎ、コードの意図を明確にし、ときには最適化の助けにもなります。言語処理系のように大きく長持ちするプログラムでは、この「約束」が効いてきます。 ## コンパイラに守らせる「約束」としてのconst C言語では、変数は基本的にいつでも書き換えられます。`const` を付けると、その変数は**初期化のあと書き換えられなくなります**。 ```c const int MAX_DEPTH = 1000; // 再帰の最大の深さ MAX_DEPTH = 2000; // ← コンパイルエラー：const を書き換えようとした ``` `MAX_DEPTH` を書き換えようとすると、コンパイラがエラーで止めてくれます。これは単なる制限ではなく、**安全装置**です。「この値は途中で変わらないはずだ」という設計者の意図を、コンパイラが機械的にチェックしてくれるのです。人間の注意力に頼るより、はるかに確実です[](#cite:seacord2020)。 `const` は、プログラムのあちこちに散らばる「変えてはいけない値」に意図を込めるのに向いています。マクロ（`#define`）でも定数は作れますが、`const` は型を持つぶん、型チェックの恩恵を受けられます。 ## ポインタのどこが定数なのか `const` がいちばん混乱を呼ぶのは、ポインタと組み合わさったときです。ポインタには「指す先」と「ポインタ自身」という二つの書き換え対象があり、`const` がどちらに掛かるかで意味が変わります。 ```c int a = 1, b = 2; const int *p = &a; // (1) 指す先が const：*p は書き換え不可、p は変更可 int *const q = &a; // (2) ポインタ自身が const：*q は書き換え可、q は変更不可 const int *const r = &a; // (3) 両方 const ``` それぞれ何ができて何ができないかを表にします。 | 宣言 | `*x = ...`（指す先を書く） | `x = ...`（別の番地を指す） | |------|:---:|:---:| | `const int *p` | ✗ できない | ✓ できる | | `int *const q` | ✓ できる | ✗ できない | | `const int *const r` | ✗ できない | ✗ できない | 見分け方のコツは、「`const` のすぐ右にあるものが守られる」と読むことです。`const int *p` は `const` の右が `int`（指す先）なので指す先が守られ、`int *const q` は `const` の右が `*`（ポインタ自身）なのでポインタが守られます。言語処理系でいちばんよく使うのは (1) の `const int *`、すなわち「指す先は読むだけ」のパターンです。 > [!NOTE] > 「ポインタを内側から外側へ読む」というコツは、関数ポインタ（[](function-pointers.md)）の宣言を読むときと同じ要領です。Cの宣言は、記号の位置で意味が決まります。慣れるまでは表を見返しながらで構いません。 ## 壊さないという宣言としての関数引数のconst `const` がもっとも役立つのは、**関数の引数**です。前の章で何度か `const Node *` や `const char *` を引数に使ってきました。これは関数の利用者への約束です。すなわち「この関数は、渡されたデータを読むだけで、書き換えません」という宣言です。 ```c // この関数はトークンを表示するだけで、中身を変えない void print_token(const Token *t) { printf("種類=%d 行=%d\n", t->kind, t->line); // t->kind = 0; ← もし書こうとすればコンパイルエラーになる } ``` `const Token *t` と書いておくと、うっかり関数の中で `t->kind` を書き換えるコードを書いても、コンパイラが止めてくれます。これには三つの利点があります。 第一に、バグを防ぐこと。「表示するだけのつもりが、誤って書き換えていた」という事故を、コンパイル時に発見できます。第二に、意図が伝わること。関数の宣言を見ただけで、「ああ、これは読むだけの関数だ」と利用者にわかります。ドキュメントを読まなくても、型が語ってくれるのです。第三に、後で述べる最適化の助けになることがあります。 言語処理系のように関数が何百個もあるプログラムでは、「この関数はデータを壊すのか、壊さないのか」が型から読み取れることの価値は計り知れません。`const` を付けられる引数には積極的に付けるのが、規模の大きなCプログラムでの良い習慣です[](#cite:kernighan1988)。 > [!TIP] > 迷ったら「読むだけの引数には `const` を付ける」を基本姿勢にしましょう。あとから「やっぱり書き換えたい」となったときは外せばよく、害はありません。逆に、最初は付けずにいて後から付けようとすると、その関数が呼ぶ別の関数にも `const` を波及させる必要が出て、手間が増えがちです（これを **const 汚染** と呼ぶこともあります。先に付けておくほうが楽です）。 ## constの伝播と、無理に外すごまかし `const` には「伝わっていく」性質があります。`const Node *` を受け取った関数が、その `left` メンバ（これも `Node *`）を別の関数に渡すなら、その関数も `const` を尊重しなければ筋が通りません。だから `const` 対応の関数は、芋づる式に他の関数へ `const` を要求します。最初は面倒に感じますが、これは「読むだけの処理」と「書き換える処理」が型のうえできれいに分かれていく、健全な圧力です。 一方で、`const` を無理やり外す**キャスト**（[](types.md)で学んだ型変換）も書けてしまいます。 ```c const int *p = &a; int *q = (int *)p; // const を外す。書けるが、原則やってはいけない *q = 99; // 未定義動作になりうる危険な操作 ``` これは「約束を破る」行為です。元が本当に書き換え可能な変数を指していればたまたま動くこともありますが、本物の定数（書き換え不可能なメモリに置かれた値）を指していた場合、何が起きるか保証されません（**未定義動作**）。`const` を外すキャストは、よほどの理由がない限り避けてください。`const` は破るためでなく、守るためにあります。 > [!CAUTION] > 「コンパイルを通すために `const` を外す」のは、たいてい設計が間違っているサインです。本来は、その関数が値を書き換える必要があるなら最初から `const` を付けない、読むだけなら呼ぶ先の関数も `const` 対応にする、というのが正しい直し方です。キャストで黙らせるのは問題を先送りにするだけです。 ## constとリテラル文字列 `const` が関わる身近な落とし穴に、**文字列リテラル**があります。`"hello"` のようにソースに直接書いた文字列は、書き換えできない領域に置かれることがあります。 ```c char *s = "hello"; s[0] = 'H'; // 危険：未定義動作。クラッシュすることもある const char *t = "hello"; // こう書けば、書き換えようとした時点でコンパイルエラー ``` 文字列リテラルを指すポインタは `const char *` で受けるのが安全です。こうしておけば、誤って書き換えようとしたときにコンパイラが教えてくれます。[](pointers.md)の `skip_spaces` で引数を `const char *` にしていたのも、まさにこの理由からです。「ソースコードの文字列は読むだけ」という意図を表していたのです。言語処理系では入力ソースを大量に読みますが、入力を書き換えることはまずないので、`const char *` が基本になります。 ## この章のまとめ - `const` は「この値は書き換えない」という約束をコンパイラに守らせる安全装置。 - ポインタでは「指す先が `const`」か「ポインタ自身が `const`」かで意味が変わる。`const` のすぐ右が守られる。 - 読むだけの関数引数には `const` を付けると、バグを防ぎ、意図が伝わり、最適化の助けにもなる。 - `const` は伝播する。キャストで無理に外すのは未定義動作を招くので避ける。 - 文字列リテラルは `const char *` で受けるのが安全。入力ソースの扱いに直結する。 ここまでで、データを安全に表現する道具がそろいました。次章では、それらのデータを置く場所（実行中に確保するメモリの管理）を扱います。 # 動的メモリ管理 言語処理系は、実行してみるまで「どれだけのデータを扱うか」がわかりません。ソースコードが10行か10万行か、構文木のノードが100個か100万個か、コンパイル時には決められません。こうした「実行時に必要量が決まるメモリ」を扱うのが**動的メモリ管理（dynamic memory management）**です。[](struct.md)で `malloc` をちらりと使いましたが、この章でその正体と作法をきちんと学びます。 ## スタックとヒープ Cのプログラムが使うメモリには、性質の違う二つの領域があります。**スタック（stack）**と**ヒープ（heap）**です。 **スタック**は、関数の呼び出しに伴って自動で管理される領域です。関数の中で `int x;` や `Token t;` のように宣言した普通の変数（**局所変数 / ローカル変数**）は、ここに置かれます。関数が呼ばれると領域が確保され、関数を抜けると自動で解放されます。何も意識しなくてよいかわりに、寿命は関数の中だけ、大きさもコンパイル時に決まっている必要があります。（正確に言うと、C の規格が決めているのは「寿命」の規則だけで、スタックという置き場所は典型的な実装の姿です。最適化によって局所変数がレジスタに置かれたり、メモリ上に現れないこともあります。でも、考え方のモデルとしてはスタックで十分です。） **ヒープ**は、プログラマが明示的に「借りて」「返す」領域です。実行時に好きな大きさを確保でき、確保したメモリは**自分で返すまで生き続けます**。関数を抜けても消えません。構文木のように「関数を抜けたあとも使い続けたいデータ」「実行時までサイズが決まらないデータ」は、ヒープに置きます。 ```mermaid graph TD subgraph stack["スタック（自動管理）"] S["局所変数
関数を抜けると消える"] end subgraph heap["ヒープ（手動管理）"] H["malloc で確保
free するまで残る"] end ``` [](struct.md)で構文木のノードを `malloc` で作ったのは、まさにこの理由です。ノードを作る関数 `new_number` を抜けたあともノードは生き続けてほしいので、スタックではなくヒープに置く必要があったのです。もし局所変数として `Node n;` を作って `&n` を返したら、関数を抜けた瞬間にその領域は無効になり、壊れたポインタ（**ダングリングポインタ / dangling pointer**）が残ってしまいます。 > [!CAUTION] > 「局所変数の番地を関数の外へ返す」のは、Cの代表的な間違いです。`Node *make(void) { Node n; return &n; }` は、抜けた瞬間に無効になる場所を指すポインタを返してしまいます。たまたま動いて見えることもありますが、いつ壊れてもおかしくありません。関数より長生きさせたいデータは、必ずヒープ（`malloc`）に置きましょう。 ## mallocとfreeによる借用と返却 ヒープを使う基本の道具が、`` の `malloc` と `free` です。 ```c #include int *p = malloc(sizeof(int) * 100); // int 100 個分のメモリを借りる if (p == NULL) { // 借りられたか必ず確認する /* メモリ不足。ここでエラー処理 */ } p[0] = 42; // 配列のように使える /* ... 使う ... */ free(p); // 使い終わったら返す p = NULL; // 返したあとは NULL を入れておくと安全 ``` `malloc(バイト数)` は、指定したバイト数のメモリを確保し、その先頭の番地を返します。必要なバイト数は `sizeof(型) * 個数` で計算するのが定石です。確保に失敗すると（メモリが足りないなど）`NULL` が返るので、使う前に必ず確認します。 `free(p)` は、借りていたメモリを返します。返したあとの `p` は無効な番地を指したままなので、`p = NULL;` を入れておくと、間違って使ったときに早く気づけます。 > [!IMPORTANT] > `malloc` と `free` は**1対1で対応**させるのが鉄則です。借りたら必ず一度だけ返す。これを守れないと、次に述べる二大トラブル（メモリリークと二重解放）を招きます。「どこで確保したメモリを、どこで誰が返すのか」を設計の段階で決めておくことが、Cで大きなプログラムを書くコツです[](#cite:seacord2020)。 ## 三つの定番トラブル 動的メモリ管理には、よく知られた落とし穴があります。言語処理系のように `malloc`／`free` を多用するプログラムでは、これらが現実の悩みになります。 **メモリリーク（memory leak）**は、借りたメモリを返し忘れ、使われないメモリが溜まっていく問題です。1回や2回なら害はありませんが、インタプリタのように長時間動き続けるプログラムでは、少しずつメモリを食いつぶし、やがて動かなくなります。[](struct.md)で「木を作りっぱなしにしている」と注意したのは、このリークのことでした。 **ダングリングポインタ（dangling pointer）**は、`free` 済みの、あるいはすでに無効になったメモリを指し続けるポインタです。これを使うと、別の用途に再利用されたメモリを読み書きしてしまい、原因の追いにくいバグになります。 **二重解放（double free）**は、同じメモリを2回 `free` してしまう間違いです。ヒープの管理情報が壊れ、プログラムが異常終了したり、深刻な脆弱性になったりします。 ```c char *p = malloc(10); free(p); free(p); // ← 二重解放。p を NULL にしておけば free(NULL) は安全なので防げる ``` `free(NULL)` は「何もしない」と決められているので、`free` のあとに `p = NULL;` を入れておけば、うっかり二度 `free` しても安全です。小さな習慣ですが、効果は大きいです。 > [!TIP] > これらのトラブルは、目で追うだけでは見つけにくいものです。ツールに頼りましょう。AddressSanitizer（`cc -fsanitize=address` でコンパイル）や Valgrind といったツールは、リーク・ダングリング・二重解放を実行時に検出して、どこが原因かを教えてくれます。本書の方針どおり警告やエラーを潰していくなら、これらのツールは強力な味方です。 ## 構文木をきちんと解放する [](struct.md)で作りっぱなしにしていた構文木を、最後まで面倒を見て解放してみましょう。木は再帰的なデータなので、解放もまた再帰で書くのが自然です。**子を先に解放してから、自分を解放する**のがポイントです。 ```c void free_node(Node *n) { if (n == NULL) { return; } if (n->kind == ND_BINARY) { // 演算ノードなら、まず子を解放 free_node(n->u.binary.left); free_node(n->u.binary.right); } free(n); // 最後に自分を解放 } ``` 順序が大切です。先に `free(n)` してしまうと、`n->u.binary.left` を読むときには `n` がもう無効で、ダングリングポインタの間接参照になってしまいます。だから「子を片付けてから自分を片付ける」。木全体は、根に対して `free_node(tree)` を一度呼べば、再帰的にすべてのノードが解放されます。`malloc` で組み立てた木を、`free` で対称的にたたむわけです。 ## なぜ言語処理系はメモリ管理が難しいのか ここまでは「借りたら返す」という素朴なやり方でした。しかし、本格的な言語処理系では、これだけでは済まなくなります。理由は、**値の寿命が複雑に絡み合う**からです。 たとえば、ある変数に入れた配列を、別の変数にも代入し、関数にも渡したとします。この配列は、いくつの場所から参照されているのでしょうか。どこからも参照されなくなった瞬間はいつでしょうか。手作業で `free` のタイミングを正しく決めるのは、現実のプログラムでは非常に難しいのです。 そこで、多くの言語は**ガベージコレクション（garbage collection, GC）**（「もう誰からも参照されていないメモリを自動で見つけて回収する仕組み」）を備えています。GC は言語処理系自身が提供する機能で、ユーザーは `free` を書かなくてよくなります。RubyもPythonもJavaScriptも、内部にGCを持っています。GC の作り方そのものは本書の範囲を超えますが、「なぜ多くの言語が `malloc`／`free` をユーザーから隠し、GCを採用したのか」は、ここまで学んだ手動メモリ管理の難しさから実感できるはずです。GCの設計に踏み込みたい場合は、コンパイラの教科書[](#cite:appel1998)や[Crafting Interpreters](#cite:nystrom2021)の後半が良い入り口になります。 > [!NOTE] > 簡単な言語処理系を作る最初の一歩としては、**あえて `free` を書かない**という割り切りも有効です。短時間で終わるプログラムなら、リークしてもOSが終了時にまとめて回収してくれます。まず動くものを作り、メモリ管理は後から足す、というのは現実的な戦略です。最適化と同じく、ここでも「まず動かし、必要になってから手を入れる」が効きます（[](optimization-basics.md)）。 ## アリーナ 手動管理とGCの中間にある、実装が簡単で言語処理系と相性の良い手法を一つ紹介します。**アリーナ（arena、領域確保）**です。 アイデアは単純です。ノードを1個ずつ `malloc` するのではなく、大きなメモリを一度にどんと借りておき、そこから少しずつ切り出して使う。そして、もう全部いらなくなったら、**大きなメモリごと一度に返す**。個々のノードを `free` する必要がなくなります。 ```c typedef struct { char *buffer; // 大きく確保した領域 size_t capacity; // その大きさ size_t used; // どこまで使ったか } Arena; void *arena_alloc(Arena *a, size_t size) { void *p = a->buffer + a->used; // 次の空き位置 a->used += size; // 使った分だけ進める return p; // （実際には容量チェックや整列が要る） } ``` 構文木のように「作っている間はぜんぶ必要だが、処理が終わればまとめて捨てる」データは、アリーナと非常に相性が良いのです。1個ずつ `free` する手間も、解放順序を間違える危険もなくなり、しかも `malloc` を何度も呼ぶより速くなります。多くの実用的なコンパイラが、構文木やその場限りのデータにアリーナを使っています[](#cite:muchnick1997)。「いつ解放するか」を個々のノードではなく「フェーズ全体」の単位で考える、という発想の転換が鍵です。 ## この章のまとめ - メモリにはスタック（自動管理・関数の寿命）とヒープ（手動管理・自分で返すまで残る）がある。 - 関数より長生きさせたいデータはヒープへ。局所変数の番地を外へ返してはいけない。 - `malloc` で借り、`free` で返す。1対1で対応させ、`free` 後は `NULL` を入れる。 - メモリリーク・ダングリングポインタ・二重解放に注意。サニタイザで検出する。 - 構文木は再帰で「子→自分」の順に解放する。 - 寿命管理が難しくなるとGCが要る。簡単な処理系ではアリーナや「あえて解放しない」も有効。 ここまでで、データを表現し、置き、片付ける道具がそろいました。次の部では、こうして組んだ処理系を**速くする**話に進みます。 # 第III部　速くする 言語処理系は「正しく動く」だけでは不十分なことがあります。インタプリタが遅ければ、その上で動くプログラムも遅くなります。この部では、プログラムを速くするための考え方を二段階に分けて学びます。 まず最適化の基礎として、計測の大切さ、コンパイラがやってくれる最適化、そしてプログラマが気をつけるべき点を扱います。続いて発展編として、言語処理系に特有の速くする技法（ディスパッチの工夫や静的解析）に踏み込みます。「推測するな、計測せよ」を合言葉に進みましょう。 # 最適化の基礎 ここまでで、小さな言語処理系を組み立てる道具がそろいました。動くものができたら、次に気になるのが「速さ」です。インタプリタが遅ければ、その上で動くすべてのプログラムが遅くなります。しかし最適化は、やみくもに手を出すと、コードを複雑にするばかりで速くもなりません。罠が多い分野です。この章では、最適化に向き合う前の心構えと、土台となる基礎を学びます。 ## 早すぎる最適化は諸悪の根源 最適化の話は、ある有名な戒めから始めるのが筋です。ドナルド・クヌースは1974年の論文で、こう書きました。「**早すぎる最適化は諸悪の根源である（premature optimization is the root of all evil）**」[](#cite:knuth1974)。 これは「最適化するな」という意味ではありません。クヌースが言いたかったのは、プログラムのどこが本当に遅いのかを確かめないまま、勘で細かい高速化に走るな、ということです。経験則として、プログラムの実行時間の大半は、コード全体のごく一部に集中します。残りの大部分をいくら磨いても、全体の速度はほとんど変わりません。それどころか、読みにくく直しにくいコードが残るだけです。 だから最適化の第一歩は、コードを書き換えることではありません。どこが遅いのかを知ることです。 > [!IMPORTANT] > 最適化に取りかかる前に、自問してください。「ここは本当に遅いのか？　それを何で確かめたのか？」。確かめずに「ここが遅そうだ」という勘だけで手を入れるのが、クヌースの戒める「早すぎる最適化」です。まず正しく動くものを作り、それから計測しましょう。この順番が大切です。 ## プロファイラとタイマー 「どこが遅いか」を客観的に知る道具が**プロファイラ（profiler）**です。プロファイラは、プログラムを実行しながら「どの関数に、どれだけの時間が使われたか」を記録してくれます。Linuxなら `perf`、GCC/Clang と組み合わせる `gprof` などがあります。 ```bash # gprof を使う例：プロファイル情報付きでコンパイルして実行 cc -pg -O2 interp.c -o interp ./interp program.txt # 実行すると gmon.out が作られる gprof interp gmon.out # 結果を表示。どの関数が重いかがわかる ``` `perf` はコンパイルオプションを追加しなくてもサンプリングできる、Linuxカーネル付属のプロファイラです。 ```bash # perf を使う例（Linux のみ）：コンパイル時の変更が不要で手軽に計測できる cc -O2 -g interp.c -o interp # -g でシンボル名を付けると結果が読みやすい perf record ./interp program.txt # 実行しながらプロファイルデータを記録する（perf.data が作られる） perf report # 結果を表示。どの関数が重いかがわかる ``` プロファイラを使うと、たいてい予想が裏切られます。「ここが重いはずだ」と思っていた関数が実は誤差で、まったくノーマークだった関数が時間の大半を食っていた、というのはよくある話です。だからこそ「**推測するな、計測せよ**」なのです。 もっと手軽に、特定の処理にかかった時間を測るだけなら、`` のタイマーで十分なこともあります。 ```c #include #include clock_t start = clock(); // 開始時刻 run_interpreter(program); // 測りたい処理 clock_t end = clock(); // 終了時刻 double sec = (double)(end - start) / CLOCKS_PER_SEC; printf("実行時間: %.3f 秒\n", sec); ``` `clock()` はプログラムが使ったCPU時間を返します。前後の差を `CLOCKS_PER_SEC` で割れば秒に直せます。改善の前後でこの数字を比べれば、「手を入れて本当に速くなったか」を確かめられます。最適化したつもりで遅くなっていた、という事態を防ぐためにも、計測は欠かせません。なお、計測値は実行のたびに揺れます（他のプログラムや CPU の状態の影響を受けるため）。一回の計測で判断せず、何回か実行して傾向を見ること、そして比べたい差が揺れより大きいことを確かめるのが、計測の基本作法です。 > [!TIP] > 計測するときは、**現実に近い入力**を使いましょう。小さすぎる入力では、本番で問題になる箇所が見えません。言語処理系なら、実際に動かしたいプログラムに近い規模のソースコードで測るのが理想です。また、計測は何度か繰り返し、ばらつきを見るようにします。 ## コンパイラの最適化フラグ 自分でコードを書き換える前に、まず使うべき強力な味方がいます。**コンパイラ自身の最適化機能**です。GCCやClangは、`-O`（オーは「Optimize」の頭文字）というフラグを付けると、生成する機械語を自動で速くしてくれます。 | フラグ | 意味 | |--------|------| | `-O0` | 最適化なし（既定）。コンパイルが速く、デバッグしやすい | | `-O1` | 軽い最適化 | | `-O2` | しっかり最適化。実用的な定番 | | `-O3` | さらに積極的な最適化 | | `-Os` | 実行ファイルのサイズを小さくする最適化 | `-O2` を付けるだけで、同じソースコードが何倍も速くなることがあります。コンパイラは、人間がやると間違えやすい細かな高速化を、正しさを保ったまま大量に適用してくれるからです。**自分でコードをいじって高速化する前に、まず `-O2` を付けて計測する**。これが最適化の正しい出発点です。 ```bash cc -O2 interp.c -o interp # まずはこれで計測する ``` コンパイラが具体的に何をしているのかは、次章[](optimization-advanced.md)で代表的な変換を紹介します。原理を体系的に学びたいなら、コンパイラ最適化の専門書[](#cite:muchnick1997)が定番です。 > [!WARNING] > `-O2` 以上を付けると、`-O0` では表に出なかったバグが顕在化することがあります。とくに、[](memory.md)で触れた未定義動作（初期化していない変数、範囲外アクセスなど）を含むコードは、最適化の有無で挙動が変わりがちです。これは偶然ではありません。コンパイラは「**未定義動作は起きない**」という前提でコードを変形してよい、と決められているからです。未定義動作を含むコードはその前提を裏切っているので、最適化が進むほど予想外の壊れ方をします。「最適化したら動かなくなった」ときは、コンパイラのせいにする前に、自分のコードに未定義動作がないかを `-Wall -fsanitize=address` などで疑いましょう。 ## アルゴリズムとデータ構造がいちばん効く 細かなコードの書き換えより、はるかに大きな差を生むのが、**アルゴリズムとデータ構造の選択**です。 例で考えましょう。言語処理系では「変数名から、その変数の情報を引く」操作（シンボルテーブルの検索）が頻繁に起こります。これを、変数を配列に並べて毎回先頭から探す方式（**線形探索**）で実装したとします。変数が `n` 個あれば、1回の検索に平均 `n/2` 回の比較が要ります。変数が増えるほど、検索は比例して遅くなります。 これを**ハッシュテーブル（hash table）**（名前から「だいたいの置き場所」を一発で計算できるデータ構造）に変えると、変数が何個あっても1回の検索がほぼ一定時間で済みます。変数が1万個あるプログラムでは、この違いは劇的です。どんなに `-O3` を付けて線形探索を磨いても、ハッシュテーブルに変えたときの差には遠く及びません。 ```mermaid xychart title "検索回数とデータ量の関係（イメージ）" x-axis ["10", "100", "1000", "10000"] y-axis "1回あたりの比較回数" 0 --> 5000 line [5, 50, 500, 5000] line [1, 1, 1, 1] ``` 上の線が線形探索（データ量に比例して増える）、下のほぼ平らな線がハッシュテーブル（データ量によらずほぼ一定）のイメージです。最適化で最初に見直すべきは、細かいコードではなく、使っているアルゴリズムとデータ構造なのです。この「処理量がデータ量とともにどう増えるか」という見方は**計算量（computational complexity）**と呼ばれ、最適化を考えるうえでの共通言語になります。 ## くり返しの内側を軽くする [](basics.md)で「インタプリタの本体は巨大なくり返しだ」と述べました。最適化の効果は、何度も実行される場所ほど大きいという原則があります。1回しか走らない初期化処理を10倍速くしても全体は変わりませんが、100万回回るループの内側を2倍速くすれば、全体が見違えます。 たとえば[](union.md)で見た `eval` のような評価ループは、プログラムの実行中ずっと回り続けます。ここで毎回、無駄な計算をしていないか（たとえば、ループの中で変わらない値を毎回計算し直していないか）を見直す価値は高いのです。次の二つを比べてみましょう。 ```c // 改善前：ループの中で毎回 strlen(name) を計算している for (int i = 0; i < count; i++) { if (strncmp(table[i], name, strlen(name)) == 0) { /* ... */ } } // 改善後：変わらない長さを外に出す（ループ不変式の移動） size_t len = strlen(name); for (int i = 0; i < count; i++) { if (strncmp(table[i], name, len) == 0) { /* ... */ } } ``` `name` の長さはループ中で変わらないのに、改善前は毎回 `strlen` で測り直しています。これをループの外に出すだけで、回る回数だけ無駄が減ります。このように「ループの中で値が変わらない計算を外に出す」変換を**ループ不変式の移動（loop-invariant code motion）**と呼びます。実は、これは `-O2` のコンパイラがしばしば自動でやってくれる変換でもあります。だからこそ「まずコンパイラに任せる」が効くのです。次章で、こうしたコンパイラの自動変換を体系的に見ていきます。 > [!NOTE] > 「速くする」と「読みやすさ」は、しばしば綱引きになります。クヌースの戒めが示すように、本当に効く一部分だけを最適化し、それ以外は読みやすさを優先するのが賢いバランスです。最適化した箇所には「なぜこう書いたか」をコメントで残すと、後で読む人（未来の自分を含む）が助かります。 ## この章のまとめ - 「早すぎる最適化は諸悪の根源」。勘ではなく計測に基づいて最適化する。 - プロファイラやタイマーで「どこが本当に遅いか」を確かめてから手を入れる。 - 自分でいじる前に、まずコンパイラの `-O2` を試して計測する。 - 細かいコードより、アルゴリズムとデータ構造の選択（計算量）がはるかに効く。 - 効果は「何度も実行される場所」ほど大きい。インタプリタの内側ループに注目する。 次章では、コンパイラが内部で行っている代表的な最適化と、言語処理系を速くするための一歩進んだ技法に踏み込みます。 # コンパイラの中身と処理系を速くする技法 前章では「まず計測、それからコンパイラに任せる」という心構えを学びました。この章では一歩進んで、コンパイラが内部で何をやっているのかを代表的な変換を通してのぞき、さらに言語処理系そのものを速くするための技法に踏み込みます。前章の基礎を踏まえたうえで読んでください。 ## コンパイラが行う代表的な最適化 `-O2` を付けたとき、コンパイラはソースコードの「意味」を変えずに、機械語を速くする変換を多数適用します。代表的なものをいくつか、具体例で見ていきます。これらを知っておくと、「自分で書くべきこと」と「コンパイラに任せてよいこと」の線引きができるようになります。 **定数畳み込み（constant folding）**は、コンパイル時に計算できる式を、あらかじめ計算してしまう変換です。 ```c int x = 60 * 60 * 24; // 書いた人は意味（1日の秒数）を明示したい // コンパイラは 86400 を直接埋め込む。実行時の掛け算は消える ``` `60 * 60 * 24` は実行するまでもなく `86400` だとわかります。コンパイラはこれを計算済みの値に置き換えるので、わざわざ自分で `86400` と書いて意味をわかりにくくする必要はありません。**意味の伝わる書き方をして、計算はコンパイラに任せる**。これが定数畳み込みの教訓です。 **共通部分式の除去（common subexpression elimination）**は、同じ計算が何度も現れるとき、一度だけ計算して使い回す変換です。 ```c // 書いたコード int a = (x + y) * 2; int b = (x + y) * 3; // コンパイラは (x + y) を一度だけ計算し、両方で使い回す ``` **関数のインライン展開（inlining）**は、小さな関数の呼び出しを、その中身で置き換える変換です。関数呼び出しには、引数を渡したり戻り先を覚えたりする手間（オーバーヘッド）がかかります。中身が数行の関数なら、呼び出すより本体を直接埋め込んだほうが速いことがあります。`eval` から呼ばれる小さなヘルパ関数などは、コンパイラがインライン展開してくれることが多いのです。 ここに挙げたのは一部にすぎず、前章で触れたループ不変式の移動や、ループの展開、レジスタ割り当てなど、コンパイラは何十種類もの最適化を組み合わせます。その全体像はコンパイラの専門書[](#cite:muchnick1997)やドラゴンブック[](#cite:aho2006)で体系的に学べます。**これらの大半は人間が手で書く必要がありません**。コンパイラに任せ、人間は読みやすさとアルゴリズムに集中する。これが賢い分業です。 > [!NOTE] > 自分のコードがどう最適化されたか気になるなら、コンパイラが吐くアセンブリを見られます（`cc -O2 -S interp.c` で `interp.s` が生成されます）。あるいは [Compiler Explorer](https://godbolt.org/) というウェブツールを使うと、ソースと生成コードを並べて見られます。「この書き方とあの書き方で、生成コードは同じだった」とわかれば、見やすいほうを安心して選べます。 ## インタプリタのディスパッチを速くする ここからは、言語処理系に特有の最適化です。前章で「インタプリタの内側ループが速度を決める」と述べました。その内側ループの中心にあるのが、**ディスパッチ（dispatch）**、すなわち「次に実行すべき命令を選んで、その処理に飛ぶ」操作です。バイトコードインタプリタ（構文木ではなく、命令の列を順に実行する方式）を例に考えます。 もっとも素直な書き方は、大きな `switch` 文でループを回すものです。 ```c // 命令の列 code を先頭から実行する（簡略版） for (;;) { uint8_t op = *ip++; // 次の命令を取り出し、ポインタを進める switch (op) { case OP_ADD: /* 加算の処理 */ break; case OP_SUB: /* 減算の処理 */ break; case OP_PUSH: /* 値を積む処理 */ break; /* ... 命令の数だけ case が並ぶ ... */ } } ``` これは正しく動きますし、出発点として申し分ありません。しかし命令を1個実行するたびに、ループの先頭へ戻り、`switch` の分岐判定をやり直します。この「ループ末尾から先頭への戻り」と「`switch` の分岐」が、CPUにとっては予測しづらく、性能の足かせになることが知られています。CPUは次に進む先を先読み（**分岐予測 / branch prediction**）して高速に動きますが、`switch` ディスパッチはこの先読みを外しやすいのです。 これを改善する古典的な技法が、[](function-pointers.md)で触れた**スレッデッドコード（threaded code）**です[](#cite:bell1973)。アイデアは、「各命令の処理の末尾で、`switch` に戻らず、**次の命令の処理へ直接ジャンプする**」というものです。 ```c // computed goto を使ったスレッデッドコード（GCC/Clang の拡張機能） static void *table[] = { &&do_add, &&do_sub, &&do_push, /* ... */ }; #define DISPATCH() goto *table[*ip++] // 次の命令へ直接飛ぶ DISPATCH(); // 最初の命令へ do_add: /* 加算の処理 */ DISPATCH(); // 処理の最後で、次の命令へ直接ジャンプ do_sub: /* 減算の処理 */ DISPATCH(); do_push: /* 値を積む処理 */ DISPATCH(); ``` 各命令の処理の末尾にディスパッチを置くことで、命令ごとに別々のジャンプ地点ができ、CPUの分岐予測が当たりやすくなります。Ertlらの研究[](#cite:ertl2003)は、こうした技法がインタプリタの性能をどれだけ左右するかを詳しく分析しており、ディスパッチの設計がインタプリタ速度の中心的な要因であることを示しています。`goto *` という見慣れない記法はGCC/Clangの拡張機能で標準Cではありませんが、高速なインタプリタの実装では広く使われています[](#cite:nystrom2021)。 > [!IMPORTANT] > ここでも前章の原則が効きます。スレッデッドコードはコードを複雑にします。まず素直な `switch` 版を作って正しく動かし、プロファイラでディスパッチが本当にボトルネックだと**確認してから**、この技法を導入すべきです。確認せずに最初からこう書くのは、まさにクヌースの戒める「早すぎる最適化」[](#cite:knuth1974)です。 ## 静的解析で実行前に手を打つ もう一つの発展的な方向が、**静的解析（static analysis）**、すなわちプログラムを実行する前に、その性質を調べて最適化に活かす技法です。前章で見たコンパイラの最適化も、その多くは静的解析に支えられています。 たとえば「この変数の値は、ここから先で二度と使われない」とわかれば、その変数を保持するためのメモリやレジスタを別の用途に回せます（**生存解析 / liveness analysis**）。あるいは「この計算結果は、どこに行っても必ず正の数だ」とわかれば、負数のチェックを省けます。こうした「実行しなくてもわかる事実」を集めて、無駄を削るわけです。 静的解析の理論的な土台として有名なのが、**抽象解釈（abstract interpretation）**です。これは、プログラムを「実際の値」ではなく「値の性質（符号、範囲、型など）」のレベルで「実行」してみることで、起こりうる挙動を安全に見積もる枠組みです。1977年にクザンらが定式化しました[](#cite:cousot1977)。たとえば「変数 `x` は常に 0 以上 100 以下だ」とわかれば、配列の範囲チェックを省ける、といった最適化につながります。 ```mermaid graph LR A[ソースプログラム] --> B[静的解析
実行せずに性質を調べる] B --> C{わかった事実} C --> D["この変数はもう使われない
→ 領域を再利用"] C --> E["この値は常に正
→ チェックを省略"] C --> F["この計算は定数
→ 事前に計算"] ``` 言語処理系を作る側にとって、静的解析は「自分の処理系を賢くする」ための道具です。最初は何もせず素直に実行する処理系で十分ですが、性能を追い求める段階になると、こうした解析が効いてきます。理論はやや高度ですが、ドラゴンブック[](#cite:aho2006)やコンパイラ実装の教科書[](#cite:appel1998)が橋渡しをしてくれます。 > [!TIP] > 静的解析は最適化のためだけのものではありません。「使われていない変数」「ヌルになりうるポインタの間接参照」「`free` 済みメモリの使用」といった**バグの検出**にも使われます。コンパイラの `-Wall -Wextra` 警告や、`clang --analyze` のような静的解析ツールは、まさにこの技術の応用です。本書が一貫して勧めてきた「警告を消す」習慣は、静的解析の恩恵を受け取る行為でもあったのです。 ## 最適化をどこで止めるか 最適化には終わりがありません。やろうと思えばいくらでも手を入れられます。だからこそ、**どこで止めるか**を決めることが大切です。 判断の基準は二つあります。ひとつは**目標**です。「このプログラムが1秒以内に終わればよい」という目標があるなら、それを達成した時点で最適化は終わりです。目標がないまま「もっと速く」を追うと、労力に見合わない細かな改善に延々と時間を溶かすことになります。 もうひとつは**費用対効果**です。最適化はたいていコードを複雑にし、読みにくく、直しにくくします。得られる速度向上が、その複雑さに見合うかを天秤にかけます。前章で見たように、効果は「何度も実行される場所」に集中するので、**ホットスポット**（実行時間の大半を占めるごく一部）だけを最適化し、残りは読みやすさを優先するのが王道です。これはクヌースの論文[](#cite:knuth1974)が半世紀前に説いたことそのものであり、いまも変わらない最適化の知恵です。 > [!CAUTION] > 最適化のためにコードを書き換えたら、**必ず前後で計測し、結果が変わっていないことも確認**してください。速くなったつもりが遅くなっていた、あるいは速くなったが計算結果が壊れていた。どちらも起こりえます。速度の計測（前章のタイマー）と、正しさの確認（テスト）は、最適化と必ずセットにします。 ## この章のまとめ - コンパイラは定数畳み込み、共通部分式の除去、インライン展開など多くの最適化を自動で行う。人間はその大半を手書きしなくてよい。 - インタプリタの速度はディスパッチが左右する。`switch` 方式をスレッデッドコードに変える古典的技法がある。 - 静的解析（抽象解釈など）は、実行前にプログラムの性質を調べ、最適化やバグ検出に活かす。 - 最適化には目標と費用対効果という止めどきがある。ホットスポットに集中し、計測と正しさの確認を必ずセットにする。 これで本書の本編は終わりです。型からポインタ、構造体や共用体や関数ポインタ、メモリ管理、そして最適化まで、簡単な言語処理系を作るのに必要なC言語の道具がそろいました。巻末の用語集（[](glossary.md)）と文献案内（[](further-reading.md)）も活用し、ぜひ自分の手で処理系を育ててみてください。 # 用語集 本書に登場した主な用語を、五十音順ではなく「学ぶ順序」に近い形でまとめます。 知らない言葉に出会ったら、ここに戻ってきてください。 各語の詳しい説明は、本文の対応する章にあります。 ## C言語の基礎にまつわる用語 **コンパイラ（compiler）** : 人間が読めるソースコードを、CPUが実行できる機械語などへ翻訳する道具。GCCやClangが代表例。詳しくは[](basics.md)。 **機械語（machine code）** : CPUが直接理解できる、0と1で表された命令の列。ソースコードはコンパイルされてこの形になる。 **プリプロセス（preprocess）** : コンパイルの前段階で、`#include` や `#define` といった `#` で始まる命令を処理すること。 **マクロ（macro）** : `#define` で定義する、コンパイル前のテキスト置き換えの仕組み。 **規格（standard）** : 「正しいCプログラムとは何か」を定めた取り決め。C99・C11・C17などの版がある[](#cite:iso2018)。 **式（expression）** : 計算して値を生み出すコードの断片。`1 + 2` など。 **制御構造（control flow）** : `if`・`for`・`while` など、処理の流れを分岐させたりくり返したりする仕組み。 **関数（function）** : ひとまとまりの処理に名前を付け、引数を受け取って値を返す部品。詳しくは[](basics.md)。 ## 型にまつわる用語 **型（type）** : ビット列をどう解釈し、どれだけの幅を占め、何ができるかを決める情報。詳しくは[](types.md)。 **固定幅整数型（fixed-width integer type）** : `int32_t` や `uint8_t` のように、どの環境でも幅が一定の整数型。`` で使える。 **符号付き／符号なし（signed / unsigned）** : 負の数を表せるのが符号付き、0以上だけを表すかわりに正の範囲が広いのが符号なし。 **移植性（portability）** : 別の環境（CPUやOS）に移しても正しく動く性質。`int` の幅が環境依存なことなどが関わる。 **キャスト（cast）** : `(double)x` のように、値の型を明示的に変換する操作。 **typedef** : 既存の型に別名を付ける機能。意図を伝え、後からの型差し替えを容易にする。詳しくは[](types.md)。 **列挙型（enum / enumeration）** : 名前付きの整数定数をまとめて定義する仕組み。タグ付き共用体のタグによく使う。 ## ポインタとメモリにまつわる用語 **メモリ（memory）／番地（address）** : データを置く、番地（通し番号）の付いた領域。詳しくは[](pointers.md)。 **ポインタ（pointer）** : 値そのものではなく、値のある「番地」を持つ変数。 **間接参照（dereference）** : `*p` のように、ポインタが指す先の値を読み書きすること。 **ヌルポインタ（null pointer）** : どこも指していないことを表すポインタ。`NULL` と書く。たどると異常終了する。 **配列（array）／添字（index）** : 同じ型の値をメモリ上に連続して並べたものと、その何番目かを指す番号（0から数える）。 **ポインタ演算（pointer arithmetic）** : `p + 1` のように、番地を型の幅ぶんずらす計算。配列アクセスの正体。 **バッファオーバーフロー（buffer overflow）** : 配列の範囲外を読み書きしてしまう不具合。深刻なバグや脆弱性の原因。 **スタック（stack）／ヒープ（heap）** : 関数の寿命で自動管理される領域がスタック、自分で借りて返す領域がヒープ。詳しくは[](memory.md)。 **malloc / free** : ヒープからメモリを借りる関数と、返す関数。1対1で対応させる。 **メモリリーク（memory leak）** : 借りたメモリを返し忘れ、使われないメモリが溜まっていく不具合。 **ダングリングポインタ（dangling pointer）** : すでに無効になった（解放済みなどの）メモリを指し続けるポインタ。 **二重解放（double free）** : 同じメモリを2回 `free` してしまう間違い。ヒープを壊す。 **ガベージコレクション（garbage collection, GC）** : もう誰からも参照されないメモリを自動で回収する仕組み。多くの言語が内蔵する。 **アリーナ（arena）** : 大きなメモリを一度に確保してそこから切り出し、最後にまとめて返す手法。構文木と相性が良い。 ## データ構造とふるまいにまつわる用語 **構造体（struct）／メンバ（member）** : 関連する複数の値を一つにまとめた型と、その中の各値。詳しくは[](struct.md)。 **共用体（union）** : すべてのメンバが同じメモリを共有する型。サイズは最大メンバに合わせる。詳しくは[](union.md)。 **タグ付き共用体（tagged union）** : 「いまどの種類か」を表すタグと共用体を組にしたもの。値や構文木の表現の定番。 **関数ポインタ（function pointer）** : 関数の番地を持つポインタ。関数を値として持ち運べる。詳しくは[](function-pointers.md)。 **ディスパッチテーブル（dispatch table）** : 「種類→処理」を表（配列）で対応づけ、種類で引いて関数を呼ぶ手法。 **コールバック（callback）** : 処理の一部を関数ポインタで外から渡す手法。`qsort` の比較関数などが例。 **const** : 「この値は書き換えない」という約束をコンパイラに守らせるキーワード。詳しくは[](const.md)。 **未定義動作（undefined behavior）** : 規格が結果を保証しない操作。`const` を破る、範囲外アクセスなどが該当し、何が起きてもおかしくない。 ## 言語処理系と最適化にまつわる用語 **言語処理系（language processor）** : ソースコードを実行・変換するソフトウェアの総称。インタプリタとコンパイラがある。詳しくは[](introduction.md)。 **字句解析（lexical analysis）／構文解析（parsing）** : 文字列を意味のある単位（トークン）に区切る処理と、その並びから文法構造を組み立てる処理。 **抽象構文木（abstract syntax tree, AST）** : 構文解析の結果を木構造で表したもの。本書では構造体とポインタで表現した。 **木構造インタプリタ（tree-walking interpreter）** : 構文木を根からたどって意味を計算する方式のインタプリタ。詳しくは[](struct.md)。 **プロファイラ（profiler）** : プログラムのどこに時間が使われたかを計測する道具。最適化の出発点。詳しくは[](optimization-basics.md)。 **計算量（computational complexity）** : 処理量がデータ量とともにどう増えるかを表す尺度。アルゴリズム選択の指標。 **ディスパッチ（dispatch）** : 次に実行する命令を選んでその処理へ飛ぶ操作。インタプリタ速度の中心。詳しくは[](optimization-advanced.md)。 **スレッデッドコード（threaded code）** : 各命令の処理の末尾から次の命令へ直接ジャンプし、ディスパッチを速くする技法[](#cite:bell1973)。 **静的解析（static analysis）／抽象解釈（abstract interpretation）** : 実行前にプログラムの性質を調べる技法と、その理論的土台の一つ[](#cite:cousot1977)。 # さらに学ぶために 本書は「簡単な言語処理系を作るのに必要なC言語の知識」を速習することに絞りました。ここから先へ進むための道案内として、信頼できる文献を分野別に紹介します。どれも本書の各章で引用したもので、次の一歩にふさわしい定番です。 ## C言語そのものを深める C言語をきちんと学び直したいなら、まず原典です。**カーニハンとリッチーの『The C Programming Language』第2版**[](#cite:kernighan1988)は、C言語の設計者自身による古典で、簡潔ながら本質を突いています。本書で駆け足に扱った文法や標準ライブラリを、腰を据えて学べます。 より現代的で実務的な入門としては、シーコードの『Effective C』[](#cite:seacord2020)が優れています。未定義動作の避け方、安全なメモリ管理、文字列の扱いなど、本書で「注意」として触れた落とし穴を、最新の規格に沿って丁寧に解説しています。本書を読んで「Cの危うさ」が気になった人に特におすすめです。 言語仕様の厳密な根拠が必要になったら、C言語の国際標準規格そのもの[](#cite:iso2018)にあたります。読み物ではありませんが、「この動作は本当に保証されているのか」を確かめる最終的なよりどころです。 ## 言語処理系の作り方を学ぶ 本書の題材だった言語処理系づくりを本格的に学ぶなら、**ニストロムの『Crafting Interpreters』**[](#cite:nystrom2021)が最良の出発点です。木構造インタプリタとバイトコードインタプリタの両方を、実際に動くコードを書きながら一冊で作り上げます。後半はまさにCで書かれており、本書で学んだ構造体、共用体、関数ポインタ、メモリ管理、スレッデッドコードが、生きた文脈で次々に登場します。Web版が無料で公開されているのも魅力です。 理論的な土台までしっかり押さえたいなら、定番の教科書へ進みます。アホらの『Compilers: Principles, Techniques, and Tools』[](#cite:aho2006)（通称「ドラゴンブック」）は、字句解析、構文解析、意味解析、最適化を体系的に網羅した、この分野の金字塔です。アペルの『Modern Compiler Implementation in C』[](#cite:appel1998)は、その名のとおりC言語での実装に重きを置いており、本書からの橋渡しとして読みやすいでしょう。 ## 最適化を深める 最適化の理論と実装を専門的に学ぶなら、マクニックの『Advanced Compiler Design and Implementation』[](#cite:muchnick1997)が定番です。本書の発展編で名前だけ挙げた数々の最適化（共通部分式の除去、生存解析、レジスタ割り当てなど）が、アルゴリズムのレベルで詳しく解説されています。 最適化に取り組む際の心構えとしては、**クヌースの古典的論文「Structured Programming with go to Statements」**[](#cite:knuth1974)を一度読む価値があります。「早すぎる最適化は諸悪の根源」という有名な一節の、本来の文脈を知ることができます。半世紀前の論文ですが、その知恵はいまも色あせていません。 インタプリタの高速化という、本書がもっとも力を入れた話題をさらに追うなら、二つの文献が役立ちます。ベルの「Threaded code」[](#cite:bell1973)は、スレッデッドコードの原典です。そしてエルトルとグレッグの「The structure and performance of efficient interpreters」[](#cite:ertl2003)は、ディスパッチの設計がインタプリタ性能をどれだけ左右するかを、現代的な計測で明らかにした重要な論文です。本書の発展編で述べたことの実証的な裏づけが得られます。 ## 静的解析の理論へ 最適化やバグ検出の土台にある静的解析を理論から学びたいなら、**クザンらの「Abstract interpretation」**[](#cite:cousot1977)が出発点です。抽象解釈という枠組みを最初に定式化した論文で、やや高度ですが、現代の多くの解析ツールの根っこにある考え方を知ることができます。いきなり原典が難しければ、まずドラゴンブック[](#cite:aho2006)のデータフロー解析の章で素地を作ってから挑むとよいでしょう。 ## 学びを進めるための姿勢 最後に、本書が一貫して勧めてきた姿勢をもう一度。**手を動かすこと**、そして**警告とエラーから学ぶこと**です。文献を読むのと並行して、小さな電卓言語のインタプリタを実際に書き、壊し、直してみてください。本書で学んだ道具が、紙の上の知識から「自分の手になじんだ道具」へ変わるのは、その瞬間です。あなたの最初の言語処理系が、ここから始まります。