開發者在玩過許多程式語言之後,是否心中曾有過這樣的想法?哪天也能開發個程式語言就好了!乍看似乎瘋狂,然而,並非那麼遙不可及。

就如同各個領域的程式開發,在接觸、練習、熟悉之後,接下來,就是思考需要具有哪些功能的問題了,既然如此,何妨開發一門玩具語言,作為開始呢?

從Brainfuck開始

現代有許多語法精妙的程式語言,不少語言在功能上更是包山包海,若語言對於meta-programming的支援度強,在語言中自訂小型的特定領域語言,早也不是什麼新鮮事了。

這當然也是自制語言的一個方向,可以在既有語言之下擴充語法,也能夠持續運用既有語言的強大功能。

另一個方向,就是完全打造一門新語言了。別把這任務看得太過神聖,就如應用程式規模有大有小,語言打造也可以從簡單開始,例如,在之前專欄中,我已經談過幾次Brainfuck語言了,如果可以實現出一個可讀取、執行Brainfuck程式碼的程式,也算是完成一門語言的打造了。

Brainfuck的打造方式之一,是建立+-><[].對應的規則物件,由於程式碼像是線性地撰寫在紙帶上,一次讀取一個符號,不需要事先將程式碼分割為單詞(Token),因此,只要可以根據符號一對一地取得規則物件,規則物件之間就不需要有特定的節點關係,這是最簡單的實現之一。

再一種其他的打造方式是,一對一地將之轉換為另一門語言。

例如,在維基百科上的〈Brainfuck〉條目中,就列出了8個符號對應的C語言程式碼,像是>對應於++ptr、<對應於--ptr,而[與]就對應於while (*ptr) {與}等,在〈打造 Brainfuck 的 JIT compiler〉(https://goo.gl/asBXF4)就有段sed實作,可以實現這個轉換。

抽象語法樹

單就運算能力而言,Brainfuck等價於現代的程式語言,只不過難以撰寫與閱讀,或許你想要的程式語言,會像是能夠print 'Hello, World'、print (1 + 2)、print (1 + (2 + 3)),而且具備變數宣告、if、while等語法的語言。

要打造這類語言,與其一開始直接面對程式碼的剖析,不如先試著建立抽象語法樹(Abstract syntax tree)。

也就是,將每個運算式或語句,轉換為對應的節點物件,而這些節點物件的執行順序,會形成樹狀結構,例如,print (1 + 2)這個語句,最簡單的語法樹可能是let ast = new Print(new Add(1, 2))。

若ast.evaluate()會呼叫Print的evaluate方法,後者又會呼叫Add的evaluate方法,因此得到1 + 2的顯示結果。然而,若要進一步考慮print (1 + (2 + 3))對應的語法樹,數字就必須也是個節點物件,而建立起的語法樹會像是:

new Print(
new Add(
new Num(1),
new Add(new Num(2), new Num(3))
)
);

Num實例同樣具有evaluate方法,呼叫後傳回自身,所以,如果使用Add的evaluate,將會是new Num(this.left.evaluate().value + this.right.evaluate().value),至於Print的evaluate,則可以是console.log(this.expression.evaluate().value)。

因此就上面的語法樹來說,會先執行new Add(new Num(2), new Num(3))的evaluate,得到內含值為5的Num實例,接著相當於執行new Add(new Num(1), new Num(5))的evaluate,得到內含值為6的Num實例,然後相當於執行new Print(new Num(6)),最終顯示6的結果。

詞法與語法分析

程式碼對應的語法樹,代表著程式階層架構,至於每個節點,代表著程式運行時的某個執行階段,若執行時,檢視節點的狀態,就可以瞭解到整個程式的運行過程。

然而,應該要有個語言處理器,讀取原始的程式碼,並將之轉換為對應的語法樹。若要實作這種語言處理器,可概略分為兩個階段:詞法分析與語法分析。

關於詞法的分析,主要是將程式碼分割為一連串的單詞。

例如,若val x1 10代表著宣告變數x並指定值為10,詞法分析器就將之分割為"val"、"x1"與"10"三個單詞,識別單詞首先要考慮單詞定義,透過規則表示式(Regular expression)來定義單詞,會是比較簡單的方式,例如,可透過[a-zA-Z_]+[a-zA-Z_0-9]*來識別變數,[0-9]+來識別整數數字等。

在詞法的分析當中,主要是去除程式碼中非必要的訊息,像是多餘的空白、換行、縮排等,只留下真正有意義的單詞。而在能夠得到正確單詞清單之後,接著進行語法分析,也就是剖析、擷取或結合清單中各個單詞,建立起對應的節點物件,並組合為抽象語法樹。

同時,詞法分析器也常被稱為剖析器(Parser)。而實作剖析器會涉及許多細節,有些程式庫可以在提供剖析規則的情況下,自動產生剖析器,像是Ruby的Treetop?

若想要試著自行實現剖析器,我們可以從設計模式的Interpreter模式(https://goo.gl/iatqQJ)方向,來進行思考。而Interpreter模式類似個別擊破的方式,在剖析出父節點之後,剩餘的剖析任務,會交給子節點相對應的剖析器。

輪子是怎麼打造的?

有興趣看看如何建造玩具語言的話,我們可以參考〈simple_lang.js〉(https://goo.gl/RozewR),當中使用了ES6來進行詞法、語法分析,執行的方式,大致上,是《深入理解運算原理》第2章中提及之〈大步語意〉,程式會一次走遍整棵語法樹後,直接傳回結果,無需額外演算流程,來接續下個節點物件之執行。

該章亦介紹了〈小步語意〉,也就是,節點每一次的執行,都是在化簡(reduce)語法樹,因而易於觀察運算過程中每個階段的情況,直到化簡至最後執行結果。

Brainfuck的實作,就有點類似小步語意,8個符號對應的規則物件,其實就像是語法樹中每個節點物件,而執行每個規則物件,會得到新的執行階段,這就像是在化簡語法樹中的節點。

《深入理解運算原理》也談及了,如何讀入規則表示式(也是一種語言)、建立對應語法樹來進行字串比對等。若想知道語言這類輪子如何打造,會是個不錯的起點。因為,瞭解輪子如何打造,最直接的益處是協助理解語言運行機制。

另一方面,這也可以是一種特意練習。在試著打造一兩個玩具語言之後,構造語言本身就不再是個神祕主題。

或許將來有想法時,也能針對特定需求構造領域語言,萬一因緣際會下,被廣為使用了,那就是超級棒的一件事了!

 

作者簡介


Advertisement

更多 iThome相關內容