現代開發者熟悉高階語言,撰寫程式碼面對的部分,是數值、運算子、運算式、變數、陳述句、函式等名詞,所寫出來的程式碼,包含了空白、分號等人類可閱讀的形式。

然而,對於語言實際的執行來說,空白、分號等細節,並不重要,只要給它一棵抽象語法樹,就可以了!

抽象語法樹的觀點

對高階程式語言來說,它包含了一組語法規則,用來描述哪些符號的組合是合法程式碼。例如,a = 10中包含了五個符號,因為除了a、=與10之外,還有兩個空白,類似地,b = a + 1包含了九個符號。

而且,語法規則只在乎符號組合是否合法,不在乎程式碼執行是否有實際意義。例如,y = x + 1合乎語法規則,然而,執行上沒有意義,因為x未定義。

高階語言的語法貼近人類使用之語言,因而易於撰寫,然而與實際的程式階層有段距離,若捨棄人類可讀的形式,可以對程式建立的階層架構(或說是順序)有更多的認識。因為,語法樹是獨立的,人類可讀形式實際所採用的格式或符號,在這兩者之間,並無直接的關係。

建立語法樹並不如想像中困難,而且是構造語言的起點,直接拿來撰寫程式也是可行的。

例如,語言中最基本的元素就是數值,可以定義Num代表,而加、乘是個具有左值與右值的二元結構。若定義Add、Mult做為代表,那麼,new Mult(new Num(3), new Add(new Num(1), new Num(2))),就是個合法的程式架構,這裡的階層關係如下:

Mult -
|- Num(3)
|- Add -
|- Num(1)
|- Num(2)

這就是一棵抽象語法樹了,等同於人類可讀形式中3 * (1 + 2),雖然抽象語法樹不包含空白、括號等額外資訊,然而,階層關係本身就具有運算順序的規則,就此例來說,就是運算子的優先權。我們可以建立語法樹,只是這代表著樹的階層關係合法,卻不代表程式的語意正確。

例如,單就new Add(new Var('x'), new Num(1))來看,它建立了合法階層,這就相當於寫下x + 1,在給予語意並嘗試進一步運行時會出錯,因為變數x並沒有定義。

陳述句與運算式?

如果想在方才提到的語法樹,增加變數值的指定(Assign),例如,希望x = 10,之後y = x + 1的話,而且使用語法樹的方式來撰寫,就會是new Assign(new Var('x'), new Num(2))與new Assign(new Var('y'), new Add(new Var('x'), new Num(1)),然而,這樣的作法建立了兩棵獨立的語法樹,無法直接組合在一起,那麼,兩棵樹之間的階層關係是什麼?

比較簡單的處理方式之一,是建立一個Stmts,其內部有個有序的清單結構,可以用來聚合多棵子樹,而每一棵子樹於清單中的順序,就是子樹之間的階層順序;而另一個方式,是有個StmtSequence,僅包含第一棵與第二棵子樹,例如,new StmtSequence(new Assign(new Var('x'), new Num(2)), new Assign(new Var('y'), new Var('x'))),而StmtSequence本身,也可以作為StmtSequence建構之用,形成遞迴結構。

在語法樹當中,像是Assign這類的節點,沒有辦法直接進行組合,必須依賴Stmts,或StmtSequence來組合,而這就是陳述句(Statement);至於Mult、Add,這類可以組合在一起的節點,就是運算式(Expression)。

陳述句構成的語法樹無法直接組合,原因在於,在執行時,它會造成環境物件的狀態變化,例如,指定陳述會在環境物件上增加一個變數,或者是更改變數的對應值,因而必須有Stmts或StmtSequence之類的角色,來傳遞環境物件的狀態變化。

至於運算式,在執行時會從葉節點的值開始,依每個運算節點的語意得到新值,一路運算至父節點的過程中,都不會造成執行環境的狀態變化,只要單純地組合出階層就可以了。

函式定義、函式呼叫

循著相同的思路,我們可以定義出各種陳述句,以及運算式節點,然後,以抽象語法樹的方式來撰寫程式。

例如,new StmtSequence(new Assign(new Var('x'), new Num(2)), new Print(new Var('x'))),就代表著 x = 2之後print x,能夠創造出節點,實際上,這就是在設計語言,而組合為「樹」就是在撰寫程式。

那麼,函式呢?可以將函式名稱看成是變數名稱,函式定義視為是一串陳述句組成的樹,只不過參數的值尚未指定,例如,有個foo函式具有參數x,本體為print x的話,我們可以建立的語法樹為:new Assign(new Variable('foo'), new Func([new Var('x')] , new Print(new Var('x'))))。

別忘了,語法樹不涉及語意,因此,方才的函式語法樹中,雖然x未定義,仍是合法的樹階層,在進行函式呼叫時,再指定函式名稱與實際的引數值,例如,foo(2)可以建立new FunCall(new Variable('foo'), [new Num(2)])來表示,也就是說,函式定義與函式呼叫,在語法樹中,是兩個不同的節點。

那麼,函式呼叫本身,該算是個陳述句,還是個運算式呢?

如果函式本身沒有傳回值,呼叫函式會對執行環境物件造成狀態變化,那函式呼叫就是個陳述句。如果函式有傳回值,可以與運算式結合為子樹,那就可以看成是運算式。

不過,這種同時具備陳述句及運算式特性的節點,並不利於建立語法樹。因此,解決的方式之一,是將函式呼叫看成是運算式,而在將函式呼叫當成是陳述句的場合時,套上一個FunCallWrapper,令其成為陳述句節點。

例如,若foo2(10)會傳回20,然而想當成陳述句看待,可建立new FunCallWrapper(new FunCall(new Variable('foo2'), [new Num(10)]))來表示。

為語法樹加上語意

語法樹在建立時,完全不涉及程式實際運行時該有的意義,因此,建立語法樹的過程中,不會有估值或化簡等動作,當然,既然用語法樹撰寫了程式,總是想要執行看看這程式是否正確,這時,就必須為語法樹加上語意。

所以,在建立簡單的語法樹時,我們就可以試著加上語意。例如,Num實例能夠以value來代表內含值,有個evaluate方法傳回this,因此,num.evaluate(ctx).value就是結果;進一步地,new Add(new Num(1), new Num(2))的evaluate,在呼叫時,會傳回new Num(left.evaluate(ctx).value + right.evaluate(ctx).value),其中的left與right,分別表示Add的左樹與右樹。

一旦可以用語法樹來撰寫程式,也可以依照採用的語意來執行出正確的結果,而這就等同於完成一門語言了。接下來,就是看看,要採用哪些對人類友善的符號與格式,以及評估是否採用現成的剖析器(Parser)程式庫,來建立可用的剖析器,或者是自行打造專用的剖析器了(後者可參考toy_lang(https://goo.gl/WWzyNh)這門語言的實作)。

作者簡介


Advertisement

更多 iThome相關內容