本文關鍵詞：實現(xiàn)模式，由筆耕文化傳播整理發(fā)布。

很久之前已經(jīng)把這本書看過一遍了，但是一直沒有實踐過!于是，拿出來再復習一遍，順便記錄筆記。關于這本書有幾點：

另外，你應該先知道編譯的過程大概分成哪幾步驟以及為什么這樣劃分！廢話少說，來看這本書的內(nèi)容。

解析輸入

詞法分析和語法分析很多地方都是相同的，解析器結(jié)構(gòu)如下：

在一個規(guī)則中包含很多子規(guī)則時，根據(jù)向前看符號來決定使用哪個，這個邏輯的代碼描述可以用if-else來做：

當然這里也可以用switch做，在規(guī)則上定義的一些常見操作有：

這些操作的代碼描述：

match// (T)* match}

能利用好這三個操作大部分的規(guī)則都可以搞定了！詞法分析相對語法分析了來說簡單很多，Lexer會提供nextToken()來供Parser使用來不斷地獲取TOKEN：

直觀上來看用switch進行預測，相當于構(gòu)造了一個狀態(tài)機吧，其中consume()方法自增下標并將下一個字符當做向前看字符（消費字符）。在僅使用一個向前看符來進行語法分析時，也就是LL(1)，對于下面語法：

elements element

生成的Paser如下：

match elements(); match} element(); match element

很簡單的語法用LL(1)是沒有問題的，對于稍微復雜一點的其預測能力差就暴露出來了，怎么辦？當然是多拿幾個進行預測！可以構(gòu)造環(huán)形緩沖區(qū)來存放用來預測的TOKEN，另外增加兩個方法：

LA：返回第k個向前看詞法單元的類型

LT：返回第k個詞法單元

那么文法：

對應的程序描述就變?yōu)椋?/p> match match match match list

但是LL(K)也不是萬能的，如果向前看k個解決不了問題，那么向前無限個總應該可以搞定了吧？回溯解析中使用遞歸嘗試不同的規(guī)則，在發(fā)現(xiàn)無法匹配時把消費掉的TOKEN吐出來：

mark release

回溯解析最大的缺陷就是性能低，而其中一個原因則是做了不少重復工作，對于語法：

在嘗試第一個子規(guī)則失敗時會去嘗試第二個，那么expr就會被匹配兩次！如果能把之前匹配過的結(jié)果記住就好了（參考記憶化搜索），此時僅需要做一些很小的修改：

memoize}} match elements(); match}

簡單說明下上面用到的幾個方法：

aleadyParsedRule：使用緩存的結(jié)果：成功返回TRUE、失敗拋異常、未處理過返回FALSE

memoize：回溯時將結(jié)果記錄到緩存

另外需要清楚一個細節(jié)：

推演時沒有通過的try-catch邏輯在非推演時更不可能走到！

最后，在遇到上下文相關的語法時使用謂詞是個不錯的選擇，用代碼描述就是增加條件：

alt }

到這里解析輸入的邏輯基本上就看完了，簡單來說：

Lexer產(chǎn)出Token流

Parser產(chǎn)出方法執(zhí)行流

接下來我們就需要在Parser產(chǎn)出的方法執(zhí)行流上面來進行分析。

分析輸入

將源碼結(jié)構(gòu)化時一般用到兩種方式：語法分析樹和抽象語法樹，從三個方面來看：

抽象語法樹都要更優(yōu)秀一些！程序?qū)崿F(xiàn)時，我們在Parser匹配的過程中向方法中插入一些代碼即可得到想要的樹形結(jié)構(gòu)：

// 原始的規(guī)則代碼 currentNode }

要比想象的簡單很多，因為在LL的解析中：

解析過程就可以看做是在語法分析樹上做DFS，任意當前樹節(jié)點的父親必然是前面遍歷過的某個節(jié)點！

不同實現(xiàn)節(jié)點的方式后續(xù)樹的遍歷等都是有影響的，有如下方式：

類型 含義

同型AST 只有一種節(jié)點類型AST，要依據(jù)TOKEN來區(qū)分不同類型

規(guī)范異型AST 從基類AST派生不同的節(jié)點類型，子節(jié)點列表統(tǒng)一

不規(guī)范異型AST 可以添加不同的子節(jié)點屬性，能夠讓代碼的可讀性更高

好不容易拿到樹形結(jié)構(gòu)了，遍歷它也不是一個輕松的活�；叵氪髮W用Java寫二叉樹遍歷的時候通常是這樣：

left right}}

把遍歷操作嵌入節(jié)點內(nèi)部最明顯的缺點是：邏輯散落在各節(jié)點中操作起來很麻煩，可以將遍歷操作統(tǒng)一放到一個地方：

在實現(xiàn)的時候在Visitor中將this傳遞就可以達到遍歷的目的了：

n n}}

提到外面代碼量并沒有減少，但是這種代碼很有規(guī)律，ANTLR可以大幅度地減少你的工作量！當然還有其他的方式來實現(xiàn)相同的目的，，這里就不Up嗦了。

遍歷語法樹的過程中要和兩個東西打交道：

操作

符號

操作很簡單，把子節(jié)點收集起來進行計算、處理就行了，但是符號就沒那么隨意，關鍵就是作用域：

嵌套的作用域更加容易理解，嵌套關系可以用樹形結(jié)構(gòu)來表示（這種作用域的特點是只有一個父節(jié)點），上面這段代碼生成的作用域如下：

在遍歷樹的時候用一個棧來保存能訪問到的作用域：

在這個過程中用到的操作有：

操作 作用

push 向棧中壓入作用域

pop 作用域結(jié)束后，要將當前的作用域彈出棧

def 在當前作用域中定義符號

resolve 解析符號

面向過程的變成語言很簡單，這些已經(jīng)夠了，但是在面向?qū)ο缶幊痰臅r候就不行了：

由于繼承關系的存在，在查找符號的時候不僅是要在當前類中找，而且要去父類中找，也就是說此時的父節(jié)點就不止一個了：

對于像a.x = 3這種訪問對象屬性的行為就不能按照上面套路來了，需要增加一個操作：

操作 作用

resolveMemeber 解析成員，只會根據(jù)superClass遞歸查找

到這里還沒完，Java中的Class的定義可以在使用之前，那么在上面的處理屬性引用時發(fā)現(xiàn)還沒定義！直觀的解決方法：

預先遍歷一次來定義類型。

這里要小心處理好符號和作用域的關系。有了作用域和符號表之后需要對其進行簡單的分析：

操作 含義

計算表達式類型 操作的返回結(jié)果

自動類型提升 根據(jù)操作的對象來決定是否需要對其中低等級的進行提升

靜態(tài)類型檢查 操作的對象類型是否合法

多態(tài)類型檢查 面向?qū)ο笾械母缸雨P系

簡單來說都是在遍歷AST的時候完成的，下面來看如何運行程序~~

解釋執(zhí)行

經(jīng)過上面這些步驟我們已經(jīng)知道了源碼所要表達的意思，那么就可以用代碼來實現(xiàn)其邏輯（也就是解釋執(zhí)行），根據(jù)實現(xiàn)方式區(qū)分有：

語法制導解釋器：不會生成AST，在解析源碼的過程中完成；

基于樹的解釋器：先構(gòu)建AST，在遍歷的過程中完成執(zhí)行；

這兩種方式很好理解，用1+2*3的例子玩一玩就可以了，感覺這部分講的有點Up嗦。用上面的方式執(zhí)行優(yōu)點簡單、粗暴，缺點是耦合太強了，為了化解便有了：

用中間指令（也可以理解為原子API）作為過渡，這樣以后再有其他的DSL來了，只需要將其翻譯為這種中間指令就可以了。

生成輸出

要讓自己定義的DSL可執(zhí)行最簡單的辦法就是將其翻譯為現(xiàn)有的一種語言，和各種CC干的差不多：

比如ANTLR就是講文法翻譯為Java代碼。

語法制導是最簡單的方案，讀入內(nèi)容在解析的過程中完成輸出，無法處理前向引用：

而基于規(guī)則則是專注于指定一條一條的規(guī)則，在匹配到某條規(guī)則的時候執(zhí)行（輸出）對應的操作：

工業(yè)界普遍流行的是模型驅(qū)動翻譯，先創(chuàng)建AST，然后在遍歷的過程中生成代碼：

對于簡單的DSL可以使用模板（比如Velocity）來簡化輸出，但是難點并不在這里。

總結(jié)

這本書對于想實現(xiàn)DSL的人來說還是挺有作用的：例子、代碼實現(xiàn)，但是想要學習理論的恐怕要失望了，因為這里幾乎是沒有的。

看到網(wǎng)上有人評價這本書能超過龍書，不知道是從哪里看出來的，類型差別這么大如何比較的？

轉(zhuǎn)載:編程語言實現(xiàn)模式

  本文關鍵詞：實現(xiàn)模式，由筆耕文化傳播整理發(fā)布。

本文編號：342666