歡迎來到「上下文無關語言」(Context-Free Languages) 的世界！

在你的計算理論 (Theory of Computation) 學習旅程中，你已經認識了正則語言 (Regular Languages)（即我們用正則表達式和有限狀態機來描述的語言）。它們對於簡單任務非常實用，例如檢查密碼是否包含數字。

不過，正則語言有一個弱點：它們只有「短期記憶」。它們無法進行計算，也無法處理深度嵌套的結構。這就是上下文無關語言派上用場的時候了！在本章中，我們將學習如何使用巴科斯範式 (Backus-Naur Form, BNF) 和語法圖 (Syntax Diagrams) 來描述這些功能更強大的語言。

快速回顧：請記住，語言不過是一組字串的集合。如果一個語言過於複雜，無法用正則表達式來描述，那麼它很可能就是一種上下文無關語言。

如果初次接觸覺得有點抽象，請不要擔心！把它想像成從基礎算術進階到代數——我們只是在為這項工作添置更好的工具而已。

1. 為什麼我們需要上下文無關語言？

課程大綱提到，你需要解釋為什麼我們使用 BNF 而不是正則表達式。

試想一下，如果你想檢查一個數學表達式是否具有對稱的括號，例如 \( ( ( ) ) \)。有限狀態機無法做到這一點，因為它需要無限數量的狀態來「計算」開啟了多少個括號，以便知道需要關閉多少個。

上下文無關語言可以處理：

  • 嵌套 (Nesting)：結構內的結構（例如括號內的括號）。
  • 遞迴 (Recursion)：引用自身的規則。
  • 匹配對 (Matching pairs)：例如語言 \( \{0^n1^n | n \ge 1\} \)，其中 0 的數量必須與 1 的數量完全相等。

你知道嗎？大多數程式語言（如 Python 或 Java）都是上下文無關的。這就是為什麼當你忘記關閉大括號時，編譯器能夠偵測出來的原因！

重點總結：正則表達式無法描述需要「計算」或「平衡」的語言（如 \( 0^n1^n \)）。上下文無關語言功能更強大，並使用 BNF 來描述。

2. 巴科斯範式 (BNF)

BNF 是一種用於描述語言語法（規則）的表示法。它使用一組產生規則 (production rules) 來展示語言中的合法字串是如何構建的。

BNF 的符號

要閱讀 BNF，你只需要知道三個主要符號：

  1. < >：這些角括號包圍的是非終結符 (non-terminal)。你可以把它想像成一個「變數」或「類別」，可以進一步細分。
  2. ::=：這意味著「定義為」。
  3. |：這意味著「或」(OR)。它允許不同的選擇。
任何不在角括號內的項目都是終結符 (terminal)。這些是最終出現在字串中的實際字元或符號（例如 "a"、"1" 或 "+"）。

一個簡單的例子

讓我們定義一個數字 (digit)：
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

現在，讓我們使用遞迴來定義一個整數：
<number> ::= <digit> | <digit><number>

等等，剛剛發生了什麼？第二條規則說明一個數字要麼是單個數字，要麼是一個數字後跟隨另一個數字。這讓我們能夠組成任意長度的數值（例如 5、52 或 521）！

記憶小撇步：將非終結符 (< >) 想像成「樂高說明書」，而將終結符想像成實際的「樂高積木」。你根據說明書來決定如何組合這些積木。

重點總結：BNF 使用遞迴和產生規則來定義複雜結構如何由簡單結構構建而成。

3. 語法圖 (Syntax Diagrams)

語法圖（有時被稱為鐵路圖，Railroad Diagram）只是表現 BNF 規則的一種視覺化方式。它就像火車路線圖——你跟隨箭頭從左到右，看看一個字串是否合法。

如何閱讀它們：

  • 矩形：代表非終結符（在其他地方定義的規則）。
  • 圓形或橢圓形：代表終結符（實際的字元）。
  • 箭頭：顯示你必須走的路線。
  • 迴圈：代表重複（遞迴）。

比喻：想像一條火車軌道。如果你能通過路徑上的符號從起點走到終點，那麼你的字串就是「語法正確的」。

常見錯誤：學生經常忘記你必須遵循箭頭的方向。除非有專用的返回迴圈，否則你不能向後走！

重點總結：語法圖是 BNF 的視覺化替代方案。矩形是「子規則」，而橢圓形/圓形是「最終字元」。

4. 制定產生規則

你可能會被要求編寫自己的 BNF 規則。讓我們看一個針對必須以 '1' 開頭的簡單二進制字串 (Binary String) 的逐步範例。

第 1 步：定義基本組成部分。
<bit> ::= 0 | 1

第 2 步：定義重複部分。
我們需要一種方法來表示多個位元 (bits)。
<bits> ::= <bit> | <bit><bits>

第 3 步：合併它們以得出最終規則。
字串必須以 1 開頭。
<binary_string> ::= 1 | 1<bits>

快速複習盒：
- 終結符：路徑的「終點」（例如 'a', 'b', '1'）。
- 非終結符：可以進一步展開（例如 <word>）。
- 遞迴規則：引用自身的規則（例如 <list> ::= <item> | <item><list>）。

重點總結：要創建 BNF 規則，請從最小的部分開始，並使用遞迴來允許重複模式。

上下文無關語言總結

1. 為什麼？正則表達式無法處理嵌套或類似 \( 0^n1^n \) 的「匹配」模式。
2. BNF：一種基於文字的方法，使用 <非終結符>、::=（定義）和 |（或）來定義規則。
3. 語法圖：一種使用路徑、矩形和圓形來展示相同規則的視覺化方法。
4. 遞迴：這是允許 BNF 描述無限長或嵌套字串的「秘密武器」。

做得好！你已經涵蓋了 AQA A Level 電腦科學中關於上下文無關語言的要點。繼續練習這些 BNF 規則吧——一旦你掌握了竅門，它們就像拼圖一樣有趣！