【正文】 其實隱式依賴于調用棧： eval(Node n)的遞歸調用關系是靠調用棧來維護的?？纯?Java 從左到右求值順序的例子： Java 代碼 publicclass EvalOrderDemo{publicstaticvoid main(String args){int arr=newint1]； int a=1； int b=2； arr[0]=a+b； }}由 javac 編譯，得到 arr[0]=a+b 對應的字節(jié)碼是： Java bytecode 代碼 //左子樹：數(shù)組下標 //a[0aload_1iconst_0//右子樹：加法 //aiload_2//biload_3//+iadd//根節(jié)點：賦值 iastore 從樹遍歷解釋器進化為基于棧的字節(jié)碼解釋器的前端如果你看到樹形結構與后序遍歷，并且知道后綴記法 (或者逆波蘭記法， reverse Polish notation)的話，那敏銳的你或許已經(jīng)察覺了：要解釋執(zhí)行 AST，可以先通過后序遍歷 AST生成對應的后綴記法的操作序列，然后再解釋執(zhí)行該操作序列。上面的例子中就先遍歷的 =的左側，求得 i的左值；再遍歷 =的右側，得到表達式的值 23；最后執(zhí)行=自身，完成對 i的賦值。在沒有副作用的環(huán)境中，給定優(yōu)先級與結合性，則無論求值順序是怎樣的都能得到同樣的結果；而在有副作用的環(huán)境中，求值順序會影響結果。這三個概念與運算的聯(lián)系都很緊密，但實際描述的 是不同的關系。所謂求值順序，就是在遍歷子節(jié)點時的順序。所謂結合性，就是當同類操作相鄰出現(xiàn)時，操作的先后順序同 AST 節(jié)點與根的距離的關系。優(yōu)先級高的操作會更遠離根，優(yōu)先級低的操作會更接近根。優(yōu)先級、結合性與求值順序這三個是不同的概念，卻經(jīng)常被混淆。因此左值也是需要計算的。例如數(shù)字 1，它自身有值就是 1，可以作為右值使用；但它沒有與可賦值的存儲單元相綁定，所以無法作為左值使用。在許多編程語言中，左值與右值在語法上沒有區(qū)別，它們實質的差異容易被忽視?？赡苄枰f明的：上圖中節(jié)點右下角的紅色標記都只依賴子節(jié)點來計算，顯然是綜合屬性。 (話說，上圖中節(jié)點左下角有藍色標記的說明那是節(jié)點的 內在屬性 。 樹遍歷解釋器圖解在演示基于棧與基于寄存器的 VM的例子前，先回頭看看更原始的解釋器形式。 VEE是 Virtual Execution Environment 的縮寫，是 ACM下 SIGPLAN 組織的一個會議，專門研討虛擬機的設計與實現(xiàn)的。一般認為基于寄存器的架構對 VM來說也是更快的，原因是：雖然零地址指令更緊湊，但完成操作需要更多的 load/store 指令，也意味著更多的指令分派 (instruction dispatch)次數(shù)與內存訪問次數(shù)；訪問內存是執(zhí)行速度的一個重要瓶頸，二地址或三地址指令雖然每條指令占的空間較多，但總體來說可以用更少的指令完成操作，指令分派與內存訪問次數(shù)都較少。回到主題，基于棧與基于寄存器的架構，誰更快 ?看看現(xiàn)在的實際處理器，大多都是基于寄存器的架構，從側面反映出它比基于棧的架構更優(yōu)秀。于是這樣的 VM可移植性就比較高。如果源架構中寄存器的數(shù)量跟實際機器的一樣，或者前者比后者更多，那源架構的寄存器就沒辦法都映射到實際機器的寄存器上；這樣 VM實現(xiàn)起來比較麻煩，與能 夠全部映射相比效率也會大打折扣。假如一個 VM 采用基于寄存器的架構 (它接受的指令集大概就是二地址或者三地址形式的 )，為了高效執(zhí)行，一般會希望能把源架構中的寄存器映射到實際機器上寄存器上。該 VM 是為某類資源非常匱乏的硬件而設計的這類硬件的存儲器可能很小，每一字節(jié)的資源都要節(jié)省。更新：回帖中 cscript 指出了這句不太準確，應該是針對基于棧架構的指 令集生成代碼的編譯器更容易實現(xiàn)，而不是 VM 更容易實現(xiàn)。為什么許多主流 HLL VM，諸如 JVM、 CLI、 CPython、 CRuby 等，都采用了基于棧的架構呢 ?我覺得這有三個主要原因： 基于棧與基于 寄存器架構的 VM，用哪個好 ?如果是要模擬現(xiàn)有的處理器，那沒什么可選的，原本處理器采用了什么架構就只能以它為源。于是最終生成出來的代碼看起來就不像是基于棧的代碼了。我覺得也不應該用 基于棧 或 基于寄存器 去描述它。這種解釋器里沒有所謂的求值棧，也沒有所謂的虛擬寄存器，所以不適合以 基于棧 或 基于寄存器 去描述。上面 Java 字節(jié)碼做的加法，如果用 x86指令兩條就能完成了： X86 asm 代碼 mov eax,1add eax,2(好吧我犯規(guī)了， istore_0 對應的保存我沒寫。因此在空間緊缺的環(huán)境中，零地址指令是種可取的設計。有些虛擬機把求值棧實現(xiàn)在系統(tǒng)調用棧上，但兩者概念上不是一個東西。請一定要注意，這個棧是指 求值棧 ，而不是與系統(tǒng)調用棧 (system call stack，或者就叫 system stack)。 istore_0 指令從求值棧頂彈出一個值，并將值保存到局部變量區(qū)的第一個位置 (slot 0)。上面的 iconst_ iconst_2 兩條指令，分別向一個叫 做 求值棧(evaluation stack，也叫做 operand stack操作數(shù)棧 或者 expression stack表達式棧 )的地方壓入整型常量 2。那 n 地址 的 n如果是 0的話呢 ?看這樣一段 Java 字節(jié)碼： Java bytecode 代碼 iconst_1iconst_2iaddistore_0 注意那個 iadd(表示整型加法 )指令并沒有任何參數(shù)。那么上面兩條指令用 C來寫就類 似： C 代碼 acc+=5； acc=3；只不過 acc是 隱藏 的目標。顯然，指令集可以是任意 n 地址 的， n屬于自然數(shù)。上面提到的三地址與二地址形式的指令集，一般就是通過 基于寄存器的架構 來實現(xiàn)的。上面的add a,b 在執(zhí)行過后，就會破壞 a原有的值，而 b 的值保持不變。 ARM 處理器的主要指令集就是三地址形式的。 基于棧與基于寄存器的指令集架構用 C 的語法來寫這么一個語句： C 代碼 a=b+c；如果把它變成這種形式： add a,b,c 那看起來就更像機器指令了，對吧 ?這種就是 所謂 三地址指令 (3address instruction)，一般形式為： op dest,src1,src2 許多操作都是二元運算 +賦值。國內有影印版也有中文版，我是讀了影印版，不太清楚中文版的翻譯質量如何。 Well…其實寫 Java 程序不也是這樣么 ?現(xiàn)在也確實還有很多人把 Java 稱為 解釋型語言 ，完全無視 Java 代碼通常是經(jīng)過顯式編譯步驟才得到 .class 文件，而有些 JVM 是采用純 JIT 編譯方式實現(xiàn)的，內部沒解釋器，例如 Jikes RVM。不過 AS3語言實現(xiàn)是完整的。很生動的體現(xiàn)出 編譯器 +虛擬機 的實現(xiàn)方式。例如說要編譯一個名為 的文件，用下列命令： Command prompt 代碼 javajar 就是用 ASC將 編譯，得到 。所以我一直 覺得 編譯型語言 跟 解釋型語言 的說法太模糊，不太好。等到 FlashPlayer 去執(zhí)行 SWF 文件，或者說等到 AVM2(ActionScript Virtual Machine 2)去執(zhí)行 ABC時，又有解釋器和 JIT 編譯器兩種實現(xiàn)。如果一種語言的主流實現(xiàn)是解釋器，其內部是編譯器 +虛擬機，而虛擬機又是采用解釋方式實現(xiàn)的，或者內部實現(xiàn)是編譯器 +樹遍歷解釋器，那它就是名副其實的 解釋型語言 。有些稍微先進一點的解釋器可能 會優(yōu)化輸入的源程序，把滿足某些模式的指令序列合并為 超級指令 ；這么做就是朝著編譯的方向推進。如果采用編譯方式， VM 會把輸 入的指令先轉換為某種能被底下的系統(tǒng)直接執(zhí)行的形式 (一般就是 native code)，然后再執(zhí)行之；如果采用解釋方式，則 VM 會把輸入的指令逐條直接執(zhí)行。如果認同這個觀點，那么把 DLR 看作一種 VM也就可以接受了