跳轉到

1.3 形式語言與喬姆斯基層級#

歷史背景：語言學與計算的交會#

1956 年，Noam Chomsky 在麻省理工學院發表《Three Models for the Description of Language》，試圖為自然語言建立數學模型。他提出了一套語法層級（後世稱為 喬姆斯基層級），並引入了 產生文法（generative grammar）的形式定義。這份工作原本與程式語言無關，卻在 1960 年代初被編譯器研究者全盤接收：John Backus 與 Peter Naur 將 ALGOL 60 語法以 Chomsky 的產生式寫法描述，成為 Backus–Naur Form（BNF），從此形式語言理論成為編譯器的骨架。

同一時期，Steve Kleene（1951/1956）已在研究神經網路模型時提出 正規事件（regular events），成為正規語言的理論基礎；Michael Rabin 與 Dana Scott（1959）證明確定性與非確定性有限自動機在辨識能力上等價，為正規表示式與有限狀態機的等效性奠定基礎。

文法的形式定義#

一個形式文法是四元組 \(G = (N, \Sigma, P, S)\) ：

  • \(N\) ：非終端符號（nonterminals）集合
  • \(\Sigma\) ：終端符號（terminals）集合，即語言的基本單位
  • \(P\) ：產生式（productions）集合，形如 \(\alpha \to \beta\) ，其中 \(\alpha \in (N \cup \Sigma)^+\) 且至少含一個非終端
  • \(S \in N\) ：起始符號

語言 \(L(G)\) 是所有可從 \(S\) 推導出來的終端字串集合。

四型文法（Type 0–3）#

層級 文法種類 認識機器 範例語言 編譯器中的角色
Type 0 無限制文法 圖靈機 遞迴可枚舉語言 無實用（判定不可停）
Type 1 上下文有關 線性受限自動機 \(a^n b^n c^n\) 語意（需上下文）
Type 2 上下文無關 下推自動機（PDA） 括號配對、巢狀結構 語法（Parser）
Type 3 正規 有限狀態機（FSA） 識別字、數字 詞法（Scanner）

包含關係為 \(L_3 \subset L_2 \subset L_1 \subset L_0\) 。

為什麼詞法是 Type 3、語法是 Type 2#

識別字 [a-z][a-z0-9]*、整數 [0-9]+ 這類詞素沒有「計數」或「巢狀」需求，有限狀態機即足夠，且極快（每字元 \(O(1)\) ）。而程式語言的結構本質是巢狀：{ { } }、( ( ) )、if ... then if ... then ...，這正是 \(a^n b^n\) 型語言的特徵——需要一個堆疊來記住「看到了幾個未配對的開括號」。因此語法分析採用下推自動機。

上下文無關的「無關」是什麼意思#

Type 2 文法的產生式左邊只有一個非終端： \(A \to \alpha\) 。右邊的改寫不依賴 \(A\) 出現的上下文。然而真實語言有大量「上下文有關」的規則，例如：變數必須先宣告後使用、型別必須匹配。這類規則在語法階段無法表達，因此被推遲到語意分析階段，以符號表（一種動態維護的上下文）處理。這解釋了為什麼編譯器需要兩層檢查：文法管結構、語意管上下文。

推導與語法樹#

從 \(S\) 開始反覆套用產生式直到只剩終端，即為推導（derivation）。例如文法：

\[ E \to E + T \mid T, \quad T \to T * F \mid F, \quad F \to (E) \mid id \]

字串 id + id * id 的一個左推導：

\[ E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow id + T \Rightarrow id + T * F \Rightarrow id + id * id \]

同一推導對應的剖析樹唯一地記錄了結構：* 的兩個運算元在樹中比 + 的更深，自動表達了優先序。歧義性（ambiguity）指同一字串有兩棵以上剖析樹，例如文法 \(E \to E + E \mid E * E \mid id\) 無法唯一決定 id + id * id 的結構。編譯器必須使用無歧義文法，或用優先序與結合性宣告消解歧義。

層級理論對編譯器設計的指導#

  1. 選對工具：不要用下推自動機（Parser）做詞法的事，也不要期待文法能表達型別規則。
  2. 複雜度階梯：Type 3 辨識 \(O(n)\) ，Type 2 一般 \(O(n^3)\) （Earley/CKY），但可限制子集達到線性：LL( \(k\) )、LR( \(k\) ) 皆為線性時間。
  3. 跨越層級的例外：C++ 的模板、Perl、Haskell 的版面結構使語法依賴詞法或語意，純理論模型需打補丁——例如 C++ 的 x * y; 既可能是宣告也可能是乘法語句，需符號表回饋給 Parser（「需要語意回饋的剖析」）。

小結#

  • 喬姆斯基 1956 年的層級理論，透過 BNF 與 ALGOL 60 直接塑造了編譯器的分工。
  • 詞法＝正規語言（FSA）、語法＝上下文無關（PDA）、語意＝上下文有關（符號表輔助）。
  • 推導、剖析樹、歧義性是語法分析的核心概念，第 2、3 章將分別以 FSA 與文法理論深入。