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

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

概要

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

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

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

これらに加えて、以下のような操作もあります。

• 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,
]

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

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

ジェネリック関数 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, オーバーロードセット, オーバーロード解決, 単一化, ジェネリックインスタンス化, 循環インポート, 名前空間