- Authors
- Name
- Youngju Kim
- @fjvbn20031
コンパイラの構造と動作原理
コンパイラはソースプログラム（source program）を入力として受け取り、目的プログラム（target program）に変換するプログラムです。この記事では、コンパイラの全体構造を構成する各段階を一つずつ見ていきます。
1. 言語処理系（Language Processor）の種類
プログラミング言語を処理するシステムにはいくつかの形態があります。
- コンパイラ（Compiler）: ソースコード全体を目的コードに翻訳した後、実行します。
- インタプリタ（Interpreter）: ソースコードを一文ずつ解釈しながら即座に実行します。
- ハイブリッド方式: Javaのように、まずバイトコードにコンパイルした後、JVMがインタプリトする方式です。
コンパイラとインタプリタの主要な違いを整理すると以下の通りです。
[コンパイラ]
ソースプログラム --> [コンパイラ] --> 目的プログラム --> [実行] --> 出力
[インタプリタ]
ソースプログラム + 入力 --> [インタプリタ] --> 出力
コンパイラは翻訳過程に時間がかかりますが、一度コンパイルされた目的コードは高速に実行されます。インタプリタは翻訳なしですぐに実行できますが、実行速度は相対的に遅くなります。
2. コンパイラの全体構造
コンパイラは大きく**分析（Analysis）部分と合成（Synthesis）**部分に分かれます。
ソースプログラム
|
v
+-------------------+
| 字句解析 | (Lexical Analysis)
+-------------------+
| トークンストリーム
v
+-------------------+
| 構文解析 | (Syntax Analysis)
+-------------------+
| 構文木
v
+-------------------+
| 意味解析 | (Semantic Analysis)
+-------------------+
| 注釈付き構文木
v
+-------------------+
| 中間コード生成 | (Intermediate Code Generation)
+-------------------+
| 中間表現
v
+-------------------+
| コード最適化 | (Code Optimization)
+-------------------+
| 最適化された中間表現
v
+-------------------+
| コード生成 | (Code Generation)
+-------------------+
|
v
目的プログラム
各段階は前の段階の出力を入力として処理します。分析部分（フロントエンド、front end）はソースプログラムの構造を把握し、合成部分（バックエンド、back end）は目的コードを生成します。
3. 字句解析（Lexical Analysis）
字句解析器（lexerまたはscanner）はソースコードの文字ストリームを読み取り、**トークン（token）**単位に分割します。
例えば、次のCコードを見てみましょう。
position = initial + rate * 60;
字句解析器はこのコードを次のようなトークンに分割します。
<id, "position"> <=> <id, "initial"> <+> <id, "rate"> <*> <num, 60> <;>
各トークンはトークン名と属性値のペアで表現されます。識別子はシンボルテーブルに登録され、以降の段階で参照されます。
字句解析器の追加的な役割
- 空白（whitespace）とコメント（comment）の除去
- ソースプログラムの行番号追跡（エラーメッセージ生成用）
- マクロ前処理（preprocessor）との連携
4. 構文解析（Syntax Analysis）
構文解析器（parser）はトークンストリームを入力として受け取り、**構文木（parse tree）または抽象構文木（AST）**を生成します。
上記の例 position = initial + rate * 60 に対するASTは次の通りです。
=
/ \
/ \
id: +
position / \
/ \
id: *
initial / \
/ \
id: num:
rate 60
構文解析器は**文脈自由文法（Context-Free Grammar, CFG）**に基づいて動作します。文法はプログラミング言語の構造を定義し、パーサは入力がこの文法に合致するか検証します。
構文解析の主な方式
| 方式 | 説明 | 例 |
|---|---|---|
| Top-Down | 開始記号から出発して入力を導出 | 再帰下降パーサ、LLパーサ |
| Bottom-Up | 入力から出発して開始記号に還元 | LRパーサ、LALRパーサ |
5. 意味解析（Semantic Analysis）
意味解析器は構文木を使用してソースプログラムの意味的一貫性を検査します。
主な役割は以下の通りです。
- 型検査（Type Checking）: 演算子とオペランドの型が互換性があるか確認します。
- 型変換（Type Coercion）: 必要な場合、自動型変換を挿入します。
- スコープ検査: 変数が宣言された範囲内で使用されているか確認します。
例えば、上記の例で rate が float で 60 が int の場合、意味解析器は 60 を float に変換するノードを挿入します。
=
/ \
/ \
id: +
position / \
/ \
id: *
initial / \
/ \
id: inttofloat
rate |
num: 60
6. 中間コード生成（Intermediate Code Generation）
コンパイラはソースプログラムを直接目的コードに変換するのではなく、まず**中間表現（Intermediate Representation, IR）**を生成します。
最も広く使用されるIR形式は**3番地コード（Three-Address Code）**です。
t1 = inttofloat(60)
t2 = rate * t1
t3 = initial + t2
position = t3
3番地コードの特徴は以下の通りです。
- 各命令には最大1つの演算子のみが含まれます。
- コンパイラが一時変数（
t1、t2、t3）を生成します。 - 複雑な式の演算順序が明示的に決定されます。
中間コードの利点
- 機械独立性: 特定のハードウェアに依存しない表現です。
- 移植性: 他のターゲットマシンへの再ターゲットが容易です。
- 最適化の容易さ: 機械独立的な最適化の適用に適しています。
7. コード最適化（Code Optimization）
コード最適化段階では中間コードを変換して、より効率的な目的コードを生成できるようにします。
// 最適化前
t1 = inttofloat(60)
t2 = rate * t1
t3 = initial + t2
position = t3
// 最適化後
t1 = rate * 60.0
position = initial + t1
上記の例で行われた最適化は以下の通りです。
- 定数畳み込み（Constant Folding）:
inttofloat(60)をコンパイル時に60.0として計算します。 - 不要な一時変数の除去:
t3を削除し、直接positionに代入します。
主要な最適化技法
- 共通部分式除去（Common Subexpression Elimination）
- デッドコード除去（Dead Code Elimination）
- ループ不変コード移動（Loop-Invariant Code Motion）
- 強度削減（Strength Reduction）: コストの高い演算をより安価な演算に置き換えます。
- インライン展開（Inlining）: 関数呼び出しを関数本体で置き換えます。
8. コード生成（Code Generation）
コード生成器は最適化された中間コードをターゲットマシンの命令に変換します。
// 中間コード
t1 = rate * 60.0
position = initial + t1
// x86風アセンブリコード
LDF R2, rate // rateをレジスタR2にロード
MULF R2, R2, #60.0 // R2 = R2 * 60.0
LDF R1, initial // initialをレジスタR1にロード
ADDF R1, R1, R2 // R1 = R1 + R2
STF position, R1 // R1の値をpositionに格納
コード生成段階の主要な課題は以下の通りです。
- レジスタ割り当て（Register Allocation）: 限られたレジスタに変数を効率的に配置します。
- 命令選択（Instruction Selection）: ターゲットマシンに適した最適な命令を選択します。
- 命令スケジューリング（Instruction Scheduling）: パイプライン効率を最大化します。
9. シンボルテーブル（Symbol Table）
シンボルテーブルはコンパイラの全段階で共有されるコアデータ構造です。
+--------+-------+--------+---------+
| 名前 | 型 | スコープ | メモリ |
+--------+-------+--------+---------+
| position| float | global | 0x1000 |
| initial | float | global | 0x1004 |
| rate | float | global | 0x1008 |
+--------+-------+--------+---------+
シンボルテーブルに格納される情報は以下の通りです。
- 変数名（identifier）
- 型情報:
int、float、配列など - スコープ情報: 変数が有効な範囲
- メモリ位置: 変数が割り当てられたアドレス
シンボルテーブルは通常ハッシュテーブルで実装され、高速な挿入と検索をサポートします。スコープを処理するためにスコープチェーンやスタックベースの構造を併用します。
10. コンパイル段階（Phase）とパス（Pass）
段階（Phase）
コンパイラの各論理的機能単位を段階と呼びます。字句解析、構文解析などがそれぞれ一つの段階です。段階は概念的な区分であり、実際の実装では複数の段階が統合されることがあります。
パス（Pass）
パスはソースプログラム（または中間表現）を最初から最後まで一度読む過程です。
[1-Passコンパイラ]
一回の走査で全段階を処理
例: 簡単なアセンブラ、初期のPascalコンパイラ
[Multi-Passコンパイラ]
複数回の走査で各段階を処理
例: 現代の最適化コンパイラ（GCC、LLVMなど）
1-Passコンパイラは高速ですが最適化が制限的で、Multi-Passコンパイラはより多くの最適化を実行できますがコンパイル時間が長くなります。
現代のコンパイラの実際の構造
現代のコンパイラ（例: LLVM）は次のようなモジュール構造を持ちます。
[C/C++ Frontend] [Rust Frontend] [Swift Frontend]
\ | /
v v v
+-------------------------------+
| LLVM IR (中間表現) |
+-------------------------------+
| |
v v
[x86 Backend] [ARM Backend]
この構造のおかげで、M個の言語とN個のターゲットマシンをサポートするのにM+N個のモジュールだけで済みます（M x Nではなく）。
まとめ
| 段階 | 入力 | 出力 | 主要な役割 |
|---|---|---|---|
| 字句解析 | 文字ストリーム | トークンストリーム | トークン認識、空白/コメント除去 |
| 構文解析 | トークンストリーム | 構文木 | 文法検証、木構築 |
| 意味解析 | 構文木 | 注釈付き構文木 | 型検査、意味検証 |
| 中間コード生成 | 構文木 | 3番地コード | 機械独立IR生成 |
| コード最適化 | 中間コード | 最適化された中間コード | 性能向上変換 |
| コード生成 | 中間コード | 目的コード | 命令選択、レジスタ割り当て |
コンパイラは単なる翻訳機ではなく、プログラミング言語の意味を正確に理解し、効率的な機械語に変換する精巧なシステムです。次の記事では、プログラミング言語の基礎とコンパイラ技術の様々な応用分野を見ていきます。