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

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

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

解析輸入

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

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

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

這些操作的代碼描述：

match// (T)* match}

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

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

elements element

生成的Paser如下：

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

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

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

LT：返回第k個(gè)詞法單元

那么文法：

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

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

mark release

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

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

memoize}} match elements(); match}

簡(jiǎn)單說明下上面用到的幾個(gè)方法：

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

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

另外需要清楚一個(gè)細(xì)節(jié)：

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

最后，在遇到上下文相關(guān)的語法時(shí)使用謂詞是個(gè)不錯(cuò)的選擇，用代碼描述就是增加條件：

alt }

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

Lexer產(chǎn)出Token流

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

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

分析輸入

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

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

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

要比想象的簡(jiǎn)單很多，因?yàn)樵贚L的解析中：

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

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

類型 含義

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

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

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

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

left right}}

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

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

n n}}

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

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

操作

符號(hào)

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

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

在遍歷樹的時(shí)候用一個(gè)棧來保存能訪問到的作用域：

在這個(gè)過程中用到的操作有：

操作 作用

push 向棧中壓入作用域

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

def 在當(dāng)前作用域中定義符號(hào)

resolve 解析符號(hào)

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

由于繼承關(guān)系的存在，在查找符號(hào)的時(shí)候不僅是要在當(dāng)前類中找，而且要去父類中找，也就是說此時(shí)的父節(jié)點(diǎn)就不止一個(gè)了：

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

操作 作用

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

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

預(yù)先遍歷一次來定義類型。

這里要小心處理好符號(hào)和作用域的關(guān)系。有了作用域和符號(hào)表之后需要對(duì)其進(jìn)行簡(jiǎn)單的分析：

操作 含義

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

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

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

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

簡(jiǎn)單來說都是在遍歷AST的時(shí)候完成的，下面來看如何運(yùn)行程序~~

解釋執(zhí)行

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

語法制導(dǎo)解釋器：不會(huì)生成AST，在解析源碼的過程中完成；

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

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

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

生成輸出

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

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

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

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

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

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

總結(jié)

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

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

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

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

本文編號(hào)：342666