自己原來(lái)做過(guò)一個(gè)編譯相關(guān)的項(xiàng)目（全局優(yōu)化問(wèn)題變量相關(guān)性分組軟件的實(shí)現(xiàn)），用的是字節(jié)碼解釋器，沒(méi)有用AST解釋器。當(dāng)時(shí)基于的考慮是實(shí)現(xiàn)起來(lái)簡(jiǎn)單清晰，好調(diào)試，不像AST那么復(fù)雜，自己心中也是一直有個(gè)疑問(wèn)，到底哪種方法更好？今天總結(jié)一下。
字節(jié)碼結(jié)構(gòu)更緊湊，內(nèi)存局部性好，解釋執(zhí)行性能高。
從工程上說(shuō)，字節(jié)碼解釋器也有利于把代碼組織得更清晰，把關(guān)注點(diǎn)清晰的分離開(kāi)來(lái)。
AST解釋器有一些額外的開(kāi)銷，而字節(jié)碼解釋器可以節(jié)省這些開(kāi)銷。
AST解釋器開(kāi)銷在于：
- AST上有些沒(méi)有執(zhí)行語(yǔ)義的節(jié)點(diǎn)，但解釋器在執(zhí)行時(shí)不得不訪問(wèn)它們，增加了解釋開(kāi)銷。SquirrelFish文中用語(yǔ)句塊（block）的舉例，這個(gè)不錯(cuò)：一個(gè)block僅用于把一堆語(yǔ)句聚合在一起，自身并沒(méi)有“有效的”執(zhí)行語(yǔ)義，但解釋器為了訪問(wèn)到這個(gè)block的子節(jié)點(diǎn)卻不得不訪問(wèn)這個(gè)block。AST的節(jié)點(diǎn)種類相對(duì)于解析樹(shù)（parse tree）通常要精簡(jiǎn)許多（括號(hào)、分號(hào)之類的token通常都扔掉了），但用于解釋執(zhí)行還是不夠精簡(jiǎn)。
- AST通常使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)（父節(jié)點(diǎn)用指針指向子節(jié)點(diǎn)），解釋執(zhí)行需要遍歷AST，就得跟隨這些指針不斷做間接訪問(wèn)。外加AST常會(huì)攜帶一些跟解釋執(zhí)行沒(méi)直接關(guān)系的額外信息，這使得AST節(jié)點(diǎn)比較“肥”，占用更多內(nèi)存，而對(duì)解釋執(zhí)行有用的信息在內(nèi)存里分隔得更開(kāi)，不緊湊。
- AST中每種節(jié)點(diǎn)的結(jié)構(gòu)未必相同，有多少個(gè)子節(jié)點(diǎn)、哪些子節(jié)點(diǎn)有用、要按什么順序去訪問(wèn)那些子節(jié)點(diǎn)，都需要針對(duì)每種節(jié)點(diǎn)專門(mén)實(shí)現(xiàn)；換句話說(shuō)，必須確定了節(jié)點(diǎn)種類才能確定遍歷順序，這也不利于解釋器實(shí)現(xiàn)得緊湊。
- AST解釋器的核心遍歷邏輯最自然的實(shí)現(xiàn)方式是遞歸；當(dāng)然，執(zhí)行狀態(tài)得順著遞歸通過(guò)參數(shù)傳遞。（SquirrelFish文中還提到AST解釋器要在節(jié)點(diǎn)間傳遞狀態(tài)帶來(lái)額外開(kāi)銷。這主要是以前的JavaScriptCore的實(shí)現(xiàn)太紗布了，不能怪AST解釋器本身的概念不好?）
什么是語(yǔ)法制導(dǎo)翻譯？
解釋器邊做語(yǔ)法分析邊執(zhí)行相應(yīng)位置的語(yǔ)義動(dòng)作（semantic action）而不構(gòu)建AST（例如計(jì)算器，針對(duì)語(yǔ)義，直接執(zhí)行相應(yīng)的操作），于是在完成語(yǔ)法分析的時(shí)候也就完成了解釋執(zhí)行。假如不直接做解釋執(zhí)行，這些語(yǔ)義動(dòng)作也可以用來(lái)生成代碼（例如字節(jié)碼），邊做語(yǔ)法分析邊完成了代碼生成，中間也不需要AST。理解語(yǔ)法制導(dǎo)翻譯的最重要的一點(diǎn)就是：那些嵌在語(yǔ)法里的語(yǔ)義動(dòng)作，都可以看作epsilon匹配——匹配空字符串，也就是總是可以匹配——匹配到它們的時(shí)候就執(zhí)行里面的代碼。這樣就很好理解這些代碼是什么時(shí)候執(zhí)行的，而它能訪問(wèn)到的上下文都是怎樣的。
