---
title: シンボルテーブルとスコープ
url: https://doc.liz6.com/ja/compilers/03-semantic-analysis/01-symbol-tables-and-scopes
locale: ja
area: compilers
tags:
- コンパイラ
- シンボルテーブル
- スコープ
- 名前解決
- レキシカルスコープ
- シャドーイング
- モジュール
- 名前空間
- 可視性
- クロージャ
- オーバーロード
- 単一化
- compilers
- semantic-analysis
date: 2026-06-30
modified: 2026-07-19
description: 'コンパイラの「連絡先」: 各識別子をその定義に関連付ける。レキシカルスコープのスタック参照からクロージャのキャプチャマーキング、モジュールインポートからジェネリクスの単一化まで、すべての意味解析はこのテーブルから始まります。'
---

# シンボルテーブルとスコープ

> コンパイラの「連絡先」: 各識別子をその定義に関連付ける。レキシカルスコープのスタック参照からクロージャのキャプチャマーキング、モジュールインポートからジェネリクスの単一化まで、すべての意味解析はこのテーブルから始まります。

## 概要

意味解析の最初のステップは型チェックではなく、**名前解決 (name resolution)** です。これはソースコード内の各識別子（変数名、関数名、型名）をその定義に関連付ける処理です。これを実現するためのデータ構造が**シンボルテーブル (symbol table)** です。これは単純に見えます（名前→情報のマッピングを格納するだけ）が、スコープルールが加わると、シンボルテーブルの設計はコンパイラの正しさと効率性に直接影響を与えます。クロージャのキャプチャ、モジュールのインポート、ジェネリクスの特殊化、オーバーロード解決など、それぞれの要素がシンボルテーブルに対して異なる操作要件を課します。

## シンボルテーブルの基本操作

シンボルテーブルは、以下の2つのコア操作を効率的にサポートする必要があります。

| 操作 | 意味 |
|------|------|
| `insert(name, info)` | 現在のスコープに名前を登録する |
| `lookup(name)` | 現在のスコープから外側に向かってその名前の定義を検索する |

これらに加えて、以下のような操作もあります。
- `enter_scope()` / `exit_scope()`: レキシカルスコープへの入り出し
- `lookup_current(name)`: 現在のスコープのみを検索する（重複定義の検出用）

計算量が極めて重要です。`insert` と `lookup` はコンパイラの名前解決フェーズで膨大な回数呼び出されるため、O(1) またはそれに近い性能である必要があります。

## スタック型シンボルテーブル: レキシカルスコープのネイティブなマッピング

ソースコードのスコープは本質的にネストされています（波括弧の入れ子）。これを**スタック型シンボルテーブル**で直接表現できます。

```
struct Scope {
    symbols: HashMap<String, SymbolInfo>,   ← 現在のスコープの名前
    parent: u32,                            ← 外側のスコープのインデックス
}

symbol_table: Vec<Scope>   ← スタック、現在のスコープはスタックのトップ

enter_scope():  新規 Scope {parent: 現在のスタックトップインデックス} をプッシュ
exit_scope():   ポップ

lookup(name):
    scope = スタックトップ
    while scope != nil:
        if name in scope.symbols:
            return scope.symbols[name]
        scope = scope.parent              ← parent チェーンを辿って外側を検索
    return NOT_FOUND
```

- `insert`: 現在のスコープ（スタックトップ）にのみ書き込みます。
- `lookup`: スタックトップから `parent` チェーンを辿って外側へ検索し、最初に一致したものが最も内側の定義となります（「内側が外側を隠蔽する」というレキシカルスコープのルールに合致します）。
- 計算量: `insert` は O(1)、`lookup` は O(depth) です。depth は通常一定値です（ネストが深くなりすぎることはありません）。

これが大多数のコンパイラの実装方式です。Clang、Rust の一部のパス、C/C++ コンパイラなどがこのパターンを使用しています。

### なぜ単一のグローバルハッシュテーブルを使わないのか

単一のハッシュテーブル `HashMap<String, Vec<SymbolInfo>>` でも可能ですが、`exit_scope()` の際に、そのスコープで挿入されたすべての要素を走査して削除する必要があります。これは、スタック型のように Scope をそのままポップするよりもクリーンではありません。

## モジュールと名前空間: 二段階の検索

言語にモジュールや名前空間がある場合（「別のファイルの名前を参照する」場合）、シンボルテーブルは「現在のファイル → 現在のモジュール → インポートされたモジュール」という跨界検索を行う必要があります。

```
lookup(name, current_module):
    result = lookup_local(name)                   ← 1. 現在のスコープチェーン
    if result: return result
    result = lookup_imported(name, current_module) ← 2. インポートされた他モジュールの公開シンボル
    if result: return result
    return lookup_global(name)                    ← 3. グローバル（組み込み型/関数など）
```

モジュールシステムはシンボルテーブルに**可視性 (visibility)** を導入します。
- `public`: インポートする側からその名前が見える
- `private`: 現在のモジュール内でのみ見える

シンボルテーブルはモジュールのインポート処理において、インポートされるモジュールの `public` シンボルのみを現在のスコープチェーンに挿入します（または「インポートされたシンボル」リストを別途管理します）。Rust コンパイラは `resolve` フェーズで、`use` 文によるインポートシンボルをシンボルテーブルに展開します。

## クロージャのキャプチャ: スコープチェーンから「エスケープ」する名前へ

言語にクロージャ (closure) がある場合、クロージャ本体は**外側のスコープ**の変数を参照する可能性があります。これらの変数は、外側のスコープで `exit_scope()` が呼ばれた後もアクセスされ続ける必要があります。

```
fn outer():
    x = 10
    return fn inner():       ← inner は x をキャプチャする
        return x + 1         ← x は outer のスコープ内にあるが、inner が戻り値としてエスケープする
```

シンボルテーブルがクロージャのキャプチャを処理する手順は以下の通りです。
1. `inner` のスコープに入った際、`lookup("x")` がスコープチェーンを辿って `outer` 内の `x` を見つけます。
2. `x` を「クロージャによってキャプチャされた」とマーキングします。これは重要な意味論的マーキングであり、後続のコード生成時に `x` をスタック上に割り当てることができません（`outer` が返った後にスタックが解放されてしまうため）。代わりに**ヒープ割り当てまたは upvalue メカニズム**を使用する必要があります。
3. クロージャのシンボル情報にキャプチャリストを記録します。`[(x, by_ref_or_by_value)]`

Rust コンパイラはシンボル解析フェーズで、`Fn`/`FnMut`/`FnOnce` のキャプチャ方式（共有参照/ミュータブル参照/所有権の移動）を区別します。これらの判断はすべてシンボルテーブルのキャプチャ分析に由来します。

## オーバーロード解決: `lookup` は単一の値を返さない

関数オーバーロードを持つ言語（C++、Java など）では、同じ名前が1つのスコープ内に**複数の定義**を持つ可能性があります（引数の型が異なる）。この場合、`lookup` は単一のシンボルではなく、オーバーロードセットを返します。

```
lookup("foo") → [
    foo(int, int) → int,
    foo(float, float) → float,
    foo(string, string) → string,
]
```

どの関数を選ぶかは、呼び出し時の引数の型に依存します。これはすでに型チェックの範疇です（[型システム](/compilers/03-semantic-analysis/02-type-systems.md) で解説）。シンボルテーブルの役割は**オーバーロードセットを維持すること**であり、選択を行うことではありません。

## ジェネリクスと単一化: 名前が持つ複数の「姿」

ジェネリック関数 `fn identity<T>(x: T) -> T` は、Rust/C++ では**単一化 (monomorphization)** されます。つまり、型引数 T の実際の値（例: `i32`、`String`）ごとに独立した機械語が生成されます。これはシンボルテーブルにとって以下の意味を持ちます。

- ジェネリック定義自体は、型引数リストを伴う1つのシンボルです。
- 各インスタンス化（`identity::<i32>`）ごとに、新しいシンボルテーブルエントリが生成されます。ただし、その参照情報（キャプチャ、依存関係）はジェネリックテンプレートからコピーされます。
- シンボルテーブルは「テンプレートのインスタンス化」をサポートする必要があります。つまり、ジェネリック定義のシンボル情報をコピーし、其中的な型引数を実際の型に置き換えます。

Rust コンパイラは MIR レベルで単一化を行います（AST レベルではありません）。そのため、シンボルテーブルは AST→HIR→MIR の異なる段階で異なる粒度の情報を担います。

## トレードオフと失敗パターン

- **単層のグローバルテーブル**: スコープを区別しない → 内側の変数が外側の変数を隠蔽できず、`lookup` は常に最初に挿入された同名シンボルを返す → スタック型にする必要がある。
- **`lookup` がチェーン全体を辿らない**: 性能のために `parent` チェーンをスキップし、グローバルキャッシュを直接参照する実装がある → スコープのシャドーイングが機能しなくなる。
- **クロージャのキャプチャマーキングの漏れ**: シンボルテーブルがキャプチャを検出してもマーキングしない → コード生成でキャプチャ変数にスタック領域を割り当てる → クロージャ呼び出し時に use-after-free が発生する。
- **循環するモジュールインポート**: A が B をインポートし、B が A をインポート → シンボルテーブルの解析中に無限ループが発生する → 解析フェーズでは「解析中のモジュール」のセットを維持し、循環を検出してエラーにする必要がある。
- **同名だが異なる型**: 関数と変数が同じ名前を持つことができる言語がある（異なる名前空間、例: C の `struct foo` と `foo` 変数） → シンボルテーブルは名前空間ごとに分ける必要がある（tag namespace、object namespace、label namespace など）。各名前空間で独立してスタック検索を行う。

## 参考文献

- **Dragon Book**: 第2章（シンボルテーブル）および第6章（シンボルテーブルを用いた型チェック）
- **Cooper/Torczon**: 「Engineering a Compiler」、第4章（シンボルテーブルとスコーピング）
- **Rust コンパイラのソースコード**: `compiler/rustc_resolve/src/` — モジュール/クロージャのキャプチャ/マクロ展開を含む、名前解決の産業レベルの実装

*Keywords: シンボルテーブル, スタック型シンボルテーブル, スコープ, 名前解決, レキシカルスコープ, シャドーイング, モジュール, 名前空間, 可視性, public/private, クロージャのキャプチャ, upvalue, オーバーロードセット, オーバーロード解決, 単一化, ジェネリックインスタンス化, 循環インポート, 名前空間*