語言文法淺淺談

想要自造一門語言，我們必須先定義該門語言的文法，這看來很難，特別是被一堆專有名詞卡住，而相關的文件解釋往往又抽象，有如天上浮雲。

實際上，開發者若曾自訂數學公式、撰寫過規則表示式，可能早就定義過一門語言了。

文法用來產生字串

在先前專欄〈打造玩具語言〉中談到，Brainfuck的實現是認識自造語言不錯的起點，不過，能簡單地實現Brainfuck，原因就在於：Brainfuck的文法已經告訴開發者了，開發者只要根據文法規則實現剖析、求值。

如果開發者想自行定義語言的文法規則呢？雖然不理會文法定義，以土炮、有洞就補洞的方式，也有可能實現一門玩具語言。然而，若想打造一門具實用性的語言，文法會是最難的部份。

文法到底是什麼呢？

語言說穿了就是字串，文法就是產生字串的規則。讓我們來思考一個特例：使用某隨機演算公式來產生的隨機數字有沒有意義呢？雖然乍看毫無意義可言，實際上，隨機演算公式就是隨機數字的文法，只是隨機演算公式試圖讓人們無法解讀其文法規則罷了。

若從這個角度來看，文法是個數學公式，隨機演算公式產生的隨機數字，就是一門語言。

更進一步地來思考，數學公式也是一門語言。例如，一條(4+5)*3這類四則運算，可以從個位數四則運算的文法來產生。對於學習過四則運算的人而言，即使從未正式地寫出四則運算的文法規則，由於心中都曉得四則運算的規則，當他們看到一條四則運算公式時，也就能依規則來剖析與計算。

開發者可以試著寫出個位數四則運算的文法，然而，這對初次嘗試的人來說，並不容易。一方面，可能是因為太熟悉四則運算（人們常因過於熟悉而不知道是怎麼辦到的），另一方面，是因為四則運算的文法，是屬於上下文無關文法（Context-free Grammar），而關於這類文法構成的語言，可以形成巢狀，相對來說，文法規則其實比較複雜。

規則表示式與文法

開發者多半接觸過規則表示式，也知道它實際上是門語言，一個規則表示式可以由字面字元、詮讀字元、量詞等文法產生。

例如，^09\d{8}$是套用^、\d等文法規則而產生的規則表示式，如果是熟悉規則表示式文法的開發者，他們的腦海中可以剖析^09\d{8}$，然後知道這個規則表示式的意義。

那麼，若使用^09\d{8}$，我們可以比對出哪些字串呢？像是：0970399398、0918332423……，也就是，比對09開頭後接八個整數後結尾的所有字串。然而，從另一個角度來看，我們也可以說：^09\d{8}$有能力產生0970399398等字串。既然這樣的文法能用來產生字串，能以^09\d{8}$來產生0970399398這類的字串，那麼，^09\d{8}$是這類字串的文法嗎？

是的！如果將「09開頭後接八個整數後結尾的所有字串」看成是語言，^09\d{8}$就是這門語言的文法，因此，「一條規則表示式就是一門語言的文法」。

類似地，我們如果把電子郵件位址看成是一門語言，此時，想定義出一條規則表示式來比對電子郵件位址，其實，這就是在定義電子郵件位址這門語言的文法。

同時，一門語言的文法不用是唯一的，例如，對於使用^09\d{8}$而能夠涵蓋的語言，我們也可以使用^09[0-9]{8}$等其他寫法來產生字串。

然而，在定義文法時，若要以字串對應回文法之際，不能有兩種以上的對應方式，若發生這種情況，定義的文法就成了曖昧文法（Ambiguous Grammar）。

例如，對於ab字串來說，規則表示式(ab)*(a|b)*可以對應至(ab)*，也可以對應至(a|b)*，這時，就會有個疑問：到底是哪個比對出來的呢？就語言來說，就是一句話會有多種解讀方式。

一般而言，可以透過規則表示式來描述的語言，是正規語言（Regular language）。簡單來說，正規語言是可以被有限狀態機，或者是不需使用到記憶體的自動機辨識的語言，因此，語言不能有階層、巢狀之類的關係，同時，任意數量的對稱括號，無法使用規則表示式描述。

像是四則運算式中會出現任意數量的括號，因此，它就不是正規語言，我們無法使用規則表示式來描述，至於圖靈等價語言、HTML等，也都不是規則語言。

所以，規則表示式只用來處理循序的文字，無法用於剖析一份程式碼，或是HTML網頁，原因就在於，像是程式碼或HTML網頁這類語言，其實，是屬於上下文無關文法（Context-free Grammar）描述的範疇。

所謂的「上下文無關」，是指文法規則中，左邊都只有一個符號，因此，我們可以隨意套用文法規則中的任一條，來產生一個符合文法的字串，不會有上下文關係。

例如，面對個位數四則運算的文法，我們如果以BNF（Backus-Naur Form）的形式來書寫，其內容 敘述會是：

<expr> ::= <expr> <op> <expr>
<expr> ::= "(" <expr> ")"
<expr> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<op> ::= "+" | "-" | "×" | "÷"

上述的<expr>可以衍生出<expr> <op> <expr>，接著衍生出2 <op> <expr>，然後2 + <expr>，最後是2 + 3，這種衍生過程都是先消除最左邊符號的方式，稱作左衍生（leftmost derivation）。

相對地，衍生過程若是先消除最右邊的符號，則稱為右衍生，如果試著將衍生過程畫出來，會是個樹狀結構。從這點來看，文法也是個資料結構，描述了語言的結構關係。

不過，以上的四則運算文法是曖昧的，因為沒有定義優先權和結合律的規則。對於1+2×3+4來說，衍生過程形成的樹狀結構不會是唯一，結果就是在缺乏優先權和結合性的規則下，這個算式的運算結果會有不同的解讀方式。

如果你想要進一步知道四則運算式的優先權和結合律規則，此時，可以參考〈Language〉。

名詞是溝通經驗的橋樑

正規語言、曖昧文法、上下文無關文法、左衍生、右衍生……，一定要有這麼多名詞嗎？是的，而且，這些都是屬於形式語言（Formal language）的範疇，若想打造一門具實用性的語言，要知道的名詞還會更多。

務實地面對這些名詞會是必要的，因為這些名詞背後代表的，是前人的經驗，某些程度上，這些名詞也有點像是設計模式的概念，可用來作為溝通經驗的橋樑。

然而，釐清名詞不會是個簡單的任務，特別是這些名詞使用了正式的數學定義來描述，更常令人感到抽象難解。若是開發者曾經被這些名詞困擾過，不妨可以試著從規則表示式、四則運算著手，透過這類可能早以熟悉的運算來重新思考一下，或許會有不同的啟發。