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

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

文法用來產生字串

在先前專欄〈打造玩具語言〉中談到,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)的範疇,若想打造一門具實用性的語言,要知道的名詞還會更多。

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

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

作者簡介


Advertisement

更多 iThome相關內容