🎉 第 3.13.4 章：巴科斯範式 (BNF) 與語法圖

各位未來的電腦科學家，大家好！本章將介紹用於定義程式語言結構（即語法，Syntax）的強大工具。
你是否好奇電腦是如何判斷你的 Python 程式碼是否合法，或是如何檢查你輸入的電子郵件地址格式是否有誤？這些規則都是透過正式的文法系統（如巴科斯範式 BNF）和視覺化輔助工具（如語法圖）來規定的。

理解這些概念是深入學習計算理論 (Theory of Computation) 的關鍵，因為它們精確地規範了什麼才是一個「合法的程式」或「合法的資料」。現在，就讓我們一探電腦語言的「規則手冊」吧！

1. 定義語法：語言的文法

在接觸 BNF 之前，請記住任何語言（無論是 Python、英文，甚至是一個簡單的日期格式）都有關於元素如何組合的規則。

什麼是語法？

語法 (Syntax) 是指支配語言中句子或指令結構的規則。只要你遵循語法規則，你的句子或指令就是正確的，即使它在邏輯上可能不通。
範例：「這台電腦跑得很快」具有正確的中文語法。「電腦跑很快這台」則語法錯誤。

在程式設計中，我們需要一種精確且無歧義的方式來記錄這些規則，這就是 BNF 和語法圖派上用場的地方。

2. 巴科斯範式 (BNF)

巴科斯範式 (BNF) 是一種標準化的標記系統，用於表達程式語言或其他形式語言的產生規則（文法）。它允許我們將複雜的結構拆解成更簡單的組成部分來進行定義。

BNF 中的關鍵符號（字母表大雜燴）

別擔心這些正式名稱，重點在於理解這些符號代表的「意義」與「作用」。

  • 非終結符號 (Non-Terminal Symbols)： 代表尚需進一步定義的類別或組件。它們通常用角括號括起來。
    範例： <數字>, <變數名稱>
  • 終結符號 (Terminal Symbols)： 這些是語言中實際出現的字元或關鍵字，無法再進一步拆解。
    範例： a, 5, =, IF, ;
  • 定義符號 (::=)： 意思是「定義為」或「可替換為」。它將被定義的非終結符號與其定義內容隔開。
  • 選擇符號 (|)： 代表一種選擇，意思是「或 (OR)」。

💡 記憶小撇步： 把角括號 < > 想成是用來包裹一個「概念」，而純文字則是最終、具體的「字元」。

逐步拆解：建構簡單的產生規則

一條產生規則 (Production Rule)（或稱定義）指定了如何建構一個非終結符號。

讓我們來定義一個簡單的 <數字>：

<數字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

解釋： 一個 <數字> 定義為 (::=) 終結符號 0 或 (|) 終結符號 1 或...以此類推。

現在，讓我們定義一個 <二進位數字>：

一個二進位數字可以是一個單獨的 0 或 1，或是由 0 或 1 加上另一個二進位數字組成（這稱為遞迴，Recursion）。

<位元> ::= 0 | 1
<二進位數字> ::= <位元> | <位元> <二進位數字>

如果遞迴規則看起來有點難懂，別擔心！ 它只是意味著你可以重複使用該結構。運用這條規則，我們可以生成：

  • 1（使用第一個選擇）
  • 10（使用第二個選擇：<位元> (1) 後面接著 <二進位數字> (0)）
  • 1011（以此類推...）
使用 BNF 檢查語言語法

要檢查某個字串是否符合語言規範，我們嘗試將該字串回溯到初始的非終結符號。這過程稱為剖析 (Parsing)。

範例：檢查 '5F' 是否為合法的十六進位位數。

假設有以下規則：

<十六進位位數> ::= <數字> | <字母 A-F>
<字母 A-F> ::= A | B | C | D | E | F
<數字> ::= 0 | ... | 9

字串 '5F' 作為單個 <十六進位位數> 是不合法的，因為規則只允許一個數字「或」一個字母，不允許一個數字「並」一個字母。
如果我們想定義一個兩位數的十六進位編碼，我們需要一條新規則：

<兩位十六進位編碼> ::= <十六進位位數> <十六進位位數>

現在，'5F' 在 <兩位十六進位編碼> 的定義下就是合法的了。

🔑 重點總結：BNF

BNF 是一種基於文字的正式文法，使用非終結符號 (<>)、終結符號（字面文字）、定義 (::=) 和 選擇 (|) 來定義語言結構。

3. 語法圖（視覺化文法）

雖然 BNF 對電腦而言很精確，但語法圖 (Syntax Diagrams)（或稱鐵路圖）提供了一種視覺化呈現相同產生規則的方式，對人類來說通常更容易一目了然。

如何閱讀語法圖

把語法圖想像成一張地圖：

  1. 你從左側開始。
  2. 你沿著箭頭向右走。
  3. 你經過的任何圖形都是語法的一部分。
  4. 你必須抵達最右側才能完成。

圖形意義：

  • 橢圓形或圓形： 用於終結符號（字面字元或關鍵字）。你必須使用圖中顯示的確切符號。
  • 矩形： 用於非終結符號（在別處定義的概念，通常有自己的圖）。

想像一個定義簡單「指令」的圖：

一個指令可以定義為關鍵字 PRINT 後面接著 <字串>，或者關鍵字 INPUT 後面接著 <變數>。

如果你看到路徑折返，代表重複（類似程式設計中的迭代）。如果有分岔路徑，代表選擇（OR 運算子）。

使用語法圖檢查語法

要檢查語法，只需嘗試在圖中畫出一條連續的路徑，並將輸入字串與遇到的符號精確匹配。如果你能完整走完路徑，該輸入在語法上就是正確的。

快速回顧：BNF 與語法圖
  • BNF： 文字基礎，精確，適合機器（編譯器/剖析器）。
  • 語法圖： 視覺化，直觀，適合人類（程式設計師/學生）。
  • 兩者定義的都是完全相同的語言文法。

4. BNF 的威力（上下文無關語言）

這是一個進階概念，但對於課程大綱很重要，因為它解釋了為什麼我們使用 BNF 而不是正規表示式 (RE) 之類更簡單的方法來定義複雜的程式語言。

在計算理論中，語言根據複雜度進行分級。正規表示式定義了最簡單的語言類別，稱為正規語言 (Regular Languages)（可由有限狀態機 FSM 識別）。

然而，程式語言通常屬於上下文無關語言 (Context-Free Languages)。BNF 正是專門為處理這些更複雜的規則而設計的。

為什麼正規表示式無法代表所有事物

正規表示式的局限性在於它們沒有「記憶」或計算能力。它們只能檢查序列和簡單的重複。

BNF 透過遞迴（非終結符號引用自身），允許我們定義需要平衡或內部計算的結構。

需要 BNF 的語言（大綱必考）

課程大綱明確要求你知道 BNF 可以表示某些正規表示式無法表示的語言。這些語言通常依賴上下文或需要匹配對。

1. 回文 (Palindromes)

  • 回文是指正讀反讀都一樣的字串（例如 'madam', 'racecar'）。
  • 要檢查回文，必須確保第一個字元匹配最後一個，第二個匹配倒數第二個，依此類推。這需要一種正規表示式所缺乏的比較或記憶形式。
  • BNF 規則（針對簡單的 'a' 和 'b' 回文）：
    <P> ::= a | b | a <P> a | b <P> b | ε（其中 ε 代表「空字串」）

2. 包含特定字元數量相等的字串

  • 例如，'A' 的數量必須正好等於 'B' 的數量（例如 'AABB', 'ABAB'，而非 'AAAB'）。
  • 正規表示式無法計算或確保這種平衡，但 BNF 透過遞迴結構可以輕鬆處理。
你知道嗎？

「巴科斯範式」得名於 John Backus 和 Peter Naur。他們在 1950 年代末期利用該範式定義了最早的高階程式語言之一：Algol 60。這種正式定義對編譯器設計來說是革命性的！

🌟 為什麼 BNF/上下文無關重要？

幾乎所有現代程式語言（如 C++、Java、Python）的語法都是使用 BNF 或其擴充版本來定義的。這種能力至關重要，因為這些語言需要巢狀括號 ()、平衡的中括號 [] 以及匹配的 IF/END IF 區塊——所有這些都需要上下文無關文法提供的「記憶」功能。

5. 總結：必須掌握的核心概念

A. 檢查語法
  • 能閱讀 BNF 定義，並透過追蹤規則判斷範例字串是否合法。
  • 能閱讀語法圖（跟隨路徑），並判斷範例字串是否合法。
B. 建構簡單的 BNF 規則
  • 理解並使用 <非終結符號>、::=、| 和終結符號。
  • 能編寫包含選擇 (OR) 或簡單重複/遞迴的基本規則。
C. 正規表示式的侷限性
  • 知道正規表示式定義的是正規語言（較簡單）。
  • 知道 BNF 可以定義上下文無關語言（較複雜）。
  • 能說明 BNF 可以表示但正規表示式無法表示的特定語言例子：回文和需要特定字元數量相等的語言。

繼續練習追蹤那些規則吧！你已經成功跨越電腦科學的「語法警察」關卡了！