11 分で読了 #compilers #semantic-analysis
このページの目次

記号表とスコープ

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

概要

意味解析の最初のステップは型チェックではなく、⁠名前解決（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 をそのままポップするほど清潔ではない。

モジュールと名前空間：2次検索

言語にモジュール／名前空間がある場合（「別のファイルからの名前を参照する」）、記号表は「現在ファイル→現在モジュール→インポートされたモジュール」を超えて検索を行う必要がある：

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: symbol table, stack-based symbol table, scope, name resolution, lexical scope, shadowing, module, namespace, visibility, public/private, closure capture, upvalue, overload set, overload resolution, monomorphization, generic instantiation, cyclic import, name space

関連ページ

© 2026 liz's doc