4.1 符號表與型別系統#

語意分析的角色#

語法分析只回答「句子結構合不合文法」，但 x = y + 1 在 y 未宣告、或 y 是字串時依然合法地通過 Parser。這類「依賴上下文」的規則屬於 Type 1（上下文有關），無法用 CFG 表達，因此編譯器在剖析樹／AST 上進行第三道檢查：語意分析。其兩大工具是符號表與型別系統。

符號表#

符號表（symbol table）記錄每個識別字的屬性：名稱、種類（變數/函式/型別）、型別、可見範圍、儲存位址等。操作只有三個：

insert(name, attrs)：宣告時插入
lookup(name)：使用時查詢，回傳最內層可見者
begin_scope() / end_scope()：進出可見範圍

雜湊表是主流實作；範圍處理有兩法：

鏈結串列串：每個桶是一條按「內→外」排序的鏈，插入插頭端，end_scope 依時間戳回退（經典 Knuth/1970s 風格）。
堆疊式範圍表：每個範圍一張表，lookup 從頂往下找。實作簡單，但常被雜湊慢路徑拖累。

現代編譯器（如 LLVM 的 StringMap、Clang 的 IdentifierTable）以字串駐留＋開放定址雜湊為主，配合範圍堆疊。

範例（Pascal 風格的巢狀範圍）：

program P;           scope 0: x:int
  var x : integer;
  procedure Q;       scope 1: x:real  (遮蔽外層)
    var x : real;
    begin ... x ...  // 此處 x 是 real
  end;
begin ... x ...      // 此處 x 是 integer
end.

「內層遮蔽外層」正是 lookup 由內向外的順序保證的。

型別系統#

型別系統是一套為程式元素指派型別並檢查運算合法性的規則系統，通常以型別推論規則（typing judgement）形式呈現：

\[ \frac{\Gamma \vdash e_1 : \text{int} \quad \Gamma \vdash e_2 : \text{int}}{\Gamma \vdash e_1 + e_2 : \text{int}} \;(\text{T-Add}) \]

其中 \(\Gamma\) 是型別環境（本質上就是符號表）。橫線上為前提、下為結論——這是自然演繹風格，源自 Martin-Löf 型別理論（1970s）。

歷史脈絡：

1958 ALGOL 58 / 1960 ALGOL 60：引入型別宣告的雛形。
1970s Milner 為 LCF 與 ML 發明 Hindley–Milner 型別推論（W 演算法），使「不需宣告也能安全」成真；1980s Cardelli 與 Wegner 的《On Understanding Types, Data Abstraction, and Polymorphism》成為經典綜述。
1990s–2000s 泛型（C++ 模板、Java generics）、依存型別（Coq、Agda）逐漸進入語言。

型別檢查的實作#

以 AST 遞迴下降的型別檢查器：

check(expr, env) -> Type:
  case Var(x):     return lookup(env, x)
  case Num(n):     return int
  case Add(a, b):
    ta = check(a, env); tb = check(b, env)
    if ta == int and tb == int: return int
    if ta == float or tb == float: return float   // 隱式提升
    error("type mismatch in '+'")
  case Assign(x, e):
    tx = lookup(env, x); te = check(e, env)
    if not assignable(tx, te): error(...)
    return tx
  case Call(f, args):
    tf = lookup(env, f)
    檢查參數個數與型別（考慮預設參數、變長參數）
    return tf.return_type

雙重派遣/型別提升（int → float → double）需要「共同型別」計算；C 的 usual arithmetic conversions 是經典規則表。

型別等價、名義與結構#

名義型別（nominal）：型別名即身分（C、Java）。struct A{int x} 與 struct B{int x} 不同型。
結構型別（structural）：看內容（Go、TypeScript、ML 家族）。上例相同。
子型別：需決定協變/逆變。Java 陣列協變（帶來執行期 ArrayStoreException）；函式參數逆變、回傳協變是安全的標準答案（Scala、C#、TypeScript 遵循）。

語意錯誤清單#

實務語意檢查不止型別：

未宣告使用、重複宣告
呼叫非函式、參數數量不符
break/continue/return 位於非法位置
const 賦值、唯讀參數修改
型別轉換是否允許、是否需顯式

與其他階段的互動#

Parser 可向符號表插入宣告（若語言宣告先行），或需要語意回饋（C++ 的 x * y 需查 x 是否為型別）。
型別資訊會進入中間碼（決定 add 是整數加法還是浮點加法）。
執行期記憶體配置（4.3）依賴型別大小計算偏移。

小結#

語意分析以符號表管理上下文、以型別系統檢查合法性，對應形式語言的 Type 1 層。
巢狀範圍、遮蔽、型別推論規則是其數學骨架；HM 推論（1978）讓無宣告語言可行。
名義 vs. 結構、協變 vs. 逆變是設計型別系統時最重要的兩個取捨。