在任何談論到編譯原理的書或文件當中,都會提到:程式碼不過就是一連串符號之組成,必須經由剖析器構造抽象語法樹,程式碼只是文字,語法樹才是真正可運算的資料結構……

好吧!知道這些,到底有什麼用呢?難不成要用語法樹來寫程式?

是啊!實際爬一下Python的語法樹,就是這麼一回事!

抽象語法樹

實作一門語言確實是有其難處,閱讀相關文件更是枯燥乏味,即便已經有實作ToyLang經驗的我,打開討論編譯原理的《Modern Compiler Implementation in C》,讀著其中充滿抽象化、形式化的內容,也是令人昏昏欲睡。這本書一開始,就討論著剖析器的詞法分析、語法分析,若不試著在先前的實作經驗找出可能的對照,書中內容就算再精華,看來也只像是天上的浮雲。

從程式碼到語法樹,的確是個不易跨越的關卡,因為剖析器的設計有其難處,在實作ToyLang的過程中,我體會到:剖析器生成語法樹之後,後續還有更多,像是賦予語意等更重要的工作要進行,所以,我僅將剖析器實作到堪用的程度,接著,就將重點放在語法樹等後續的構造上。

先前專欄〈用抽象語法樹寫程式〉就是此體會下的心得,我認為,想要理解語言實作,剖析器的洗禮不是絕對必要的一環,開發者可以在看到一段程式碼時,假想自己是剖析器,試著構造它的語法樹,嘗試給予執行時的語意,《深入理解運算原理》一開始也是直接談語法樹,剖析器的部份僅提示概念,以及可用之程式庫等資源。

日前,在〈對Parser的誤解〉(https://goo.gl/DbBxtF)看到:「在Kent Dybvig這樣編譯器大師的課程上,學生直接跳過parser的構造,開始學習最精華的語意和優化技術。」此時,不免產生一種踏實感,因為「用抽象語法樹寫程式」並非只有我在突發奇想。

曾有實作語言的經驗,在看語言相關文件書籍時,思考的角度確實會受到影響。過去我在撰寫語言相關文件,談及一些底層原理時,多半只能將其他文件書籍之內容,轉化為自己的描述方式,現在,則可以憑藉著實作語言的經驗,更為精確地描述若干語言原理,而這些原理多半與語法樹的實現有關。

ast模組

然而,僅僅於此嗎?這類經驗只能作為瞭解語言,不能直接對撰寫程式上發揮實務上的作用嗎?想要多直接呢?若能摸到語法樹,甚至修改語法樹,應該就夠直接了吧!

Python的ast模組,就可以達到這個目的。例如,我們可以在import ast之後,執行node = ast.parse('n = 10'),node就是n = 10的語法樹節點,此時,如果想看一下節點描述,可以執行ast.dump(node)取得字串描述:

Module(body=[Assign(targets=[Name(id='n', ctx=Store())], value=Num(n=10))])

Python的原始碼檔案就是一個模組,這裡使用了Module來代表;[]表示模組中可以有一連串的陳述,而目前只有指定陳述;Assign是個指定陳述,Name代表變數名稱,Num代表數字節點。對照一下〈用抽象語法樹寫程式〉中談到的語法樹入門介紹,就可以輕易地看懂這個字串描述。ast模組可以作為語法樹的觀摩對象,想知道底下的函式定義與呼叫長什麼樣嗎?

def add(n1, n2):
return n1 + n2
print(add(1, 2))

那就寫個讀取原始碼的簡單I/O程式,假設code代表讀取後的原始碼內容,在執行完node = ast.parse(code)之後,使用exec(compile(node, '<string>', 'exec'))就可以執行node這棵語法樹了,有興趣的話,可以ast.dump(node)一下,看看語法樹的字串描述,這會看到FunctionDef、BinOp、Return等節點。當然,函式定義與函式呼叫相對來說,已經是比較複雜的語法樹了,從簡單的運算式或陳述句觀察,會是比較好的開始。

走訪、修改語法樹

可以觀察語法樹,似乎也沒太大作用,而ast模組也提供了走訪語法樹中各節點的方式,最簡單的是透過ast.walk(node),傳回的產生器會以node作為起點進行迭代,因此,可以搭配for in語法,若只對特定節點有興趣,例如函式定義節點,我們可以使用isinstance(node, ast.FunctionDef)方式,來進行相關的判斷。

更方便的方式,是有個類別繼承ast.NodeVisitor,並定義visit_XXX方法來走訪節點,XXX是感興趣的節點名稱,例如visit_FunctionDef,將定義的類別實例化之後,使用visit()方法,接著,我們就可以逐一造訪函式定義節點了,那麼,造訪節點有什麼實際作用嗎?

Python 3.5之後加入了型態提示,在這之前,有些工具可以提取DocStrings中撰寫的型態提示,進行型態檢查,如果對造訪節點已有心得,可以試著透過ast模組,來實作這類的功能(可參考https://goo.gl/1gErCq的簡單實作)。

除了單純走訪語法節點,進一步地,我們還可以修改語法節點。

如果想要達到這樣的目的,我們可以繼承ast.NodeTransformer,由於它是ast.NodeVisitor的子類別,同樣透過定義visit_XXX,就可以造訪特定節點,例如visit_BinOp(self, node),在取得node之後,若它代表加法運算子,node.op = ast.Mult()就可以將之修改為乘法運算子。

在語法節點全數造訪完畢之後,會傳回修改後的整棵語法樹,之後,試著執行它,會發現程式的行為,也跟著改變了(可參考https://goo.gl/jZwwJL的簡單實作)。

這算是meta-programming嗎?畢竟,它在執行時期是有改變程式碼的行為!

在先前專欄〈從實作看語言特性〉中談過,meta-programming提供的機制,多半就是在暴露底層機制,而ast模組直接給了整棵語法樹,由於meta-programming本身並沒有嚴謹的定義,若將之作為meta-programming看待,也是無妨,只不過更為直接(而且危險)。

語法樹的實務應用

相對於Python中的其他模組而言,ast模組在使用上並不複雜,模組文件內容相對來說,也簡短許多,只要稍具語法抽象樹的概念,就可以掌握ast模組來完成許多魔法。

而就好的一面來看,它可以用來實作型態提示、安全沙箱、測試框架等(可參考https://goo.gl/JTHu44)。

除了透過Python的ast模組,進行簡單入門語言實作之外,對於其他語言來說,我們可以試著尋找AST相關工具或程式庫。若以JavaScript而言,在〈AST in Modern JavaScript〉(https://goo.gl/ZPnAMV),就提到了不少的資源。

如果曾經覺得語言實作,對你來說遙不可及,試著從語法樹入門吧!非但有助於對語言本身的熟悉,藉由一些工具或程式庫,在實務應用上,也有可能發揮莫大的助益。

作者簡介


Advertisement

更多 iThome相關內容