← 回入口

形式文法 (Formal Grammar)

描述語言語法的數學工具

什麼是形式文法？

形式文法是描述語言語法的數學工具，定義了如何產生合法的字串。形式文法是編譯器理論的基礎，用於精確地描述程式語言的語法結構，是語法分析的理論依據。形式文法的研究始於 1950 年代，諾姆·喬姆斯基（Noam Chomsky）在語言學研究中首次提出了形式文法的概念，產生了著名的 Chomsky 階層。

形式定義

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

G = (N, Σ, P, S)

N  - 非終結符集合 (Non-terminals)
     表示語法類別，如「句子」、「名詞片語」等

Σ  - 終結符集合 (Terminals)
     表示語言中的基本符號，如關鍵字、運算子等

P  - 產生式規則集合 (Productions)
     定義如何從非終結符產生字串的規則

S  - 起始符號 (Start Symbol)
     開始推導的頂層非終結符，S ∈ N

產生式規則的形式為 α → β，表示「左邊可以推導出右邊」。

Chomsky 階層

類型名稱產生式規則對應自動機
Type 0無限制文法α → β（任意字串）圖靈機
Type 1上下文敏感文法αAβ → αγβ線性有界自動機
Type 2上下文無關文法A → γ下推自動機
Type 3正規文法A → aB 或 A → a有限狀態機

喬姆斯基發現，形式文法的類型與識別語言的自動機類型之間存在一一對應關係，這為編譯器的自動生成提供了理論基礎。

上下文無關文法範例

算術表達式可以用 CFG 描述：

E → T               # 表達式 → 項
E → E + T           # 表達式 → 表達式 + 項
T → F               # 項 → 因子
T → T * F           # 項 → 項 * 因子
F → ( E )           # 因子 → ( 表達式 )
F → id              # 因子 → 識別符

導出 "id + id * id" 的過程：

E → E + T → T + T → F + T → id + T
  → id + T * F → id + F * F → id + id * F → id + id * id

分析樹直觀地展示了語法結構，是語法分析的基礎：

        E
       /|\
      / | \
     E  +  T
     |     /|\
     T    / | \
     |   T  *  F
     F   |     |
     |   F     id
    id  id

正規文法

正規文法是最簡單的文法類型，其產生式規則非常受限，只能產生正則語言。正規文法與有限狀態機、正則表達式等價。範例：識別以 01 結尾的二進位字串：

S → 0A
S → 1S
A → 1B
B → 0B | 1B | ε

本課程範例

相關連結